经验总结

  1. 首页 > 生活 > >

Java集合精选常见面试题( 九 )

生活百科

  • 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap
    • 注意
    • 二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
    • 容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable
    put 与扩容put 流程
    1. HashMap 是懒惰创建数组的，首次使用才创建数组
    2. 计算索引（桶下标）
    3. 如果桶下标还没人占用，创建 Node 占位返回
    4. 如果桶下标已经有人占用
      1. 已经是 TreeNode 走红黑树的添加或更新逻辑
      2. 是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
    5. 返回前检查容量是否超过阈值，一旦超过进行扩容
    1.7 与 1.8 的区别
    1. 链表插入节点时，1.7 是头插法，1.8 是尾插法
    2. 1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容
    3. 1.8 在扩容计算 Node 索引时，会优化
    扩容（加载）因子为何默认是 0.75f
    1. 在空间占用与查询时间之间取得较好的权衡
    2. 大于这个值，空间节省了，但链表就会比较长影响性能
    3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多
    并发问题
    • 扩容死链（1.7 会存在）: 原因是1.7头插法会改变元素顺序
    • 数据错误（1.7和1.8）：并发环境下若多个待插入元素计算出来的索引下标相同则会产生覆盖问题
    key 的设计key 的设计要求
    1. HashMap 的 key 可以为 null，但 Map 的其他实现则不然
    2. 作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
    3. key 的 hashCode 应该有良好的散列性
    如果 key 可变，例如修改了 age 会导致再次查询时查询不到
    几种Map接口实现类的区别1. HashMap 和 Hashtable 的区别
    1. 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的，因为 Hashtable 内部的方法基本都经过synchronized 修饰 。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
    2. 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点 。另外，Hashtable 基本被淘汰，不要在代码中使用它；
    3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException 。
    4. 初始容量大小和每次扩充容量大小的不同 ：① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1 。HashMap 默认的初始化大小为 16 。之后每次扩充，容量变为原来的 2 倍 。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码） 。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方 。
    5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间 。Hashtable 没有这样的机制 。

      经验总结扩展阅读


    上一篇：2023年农历八月初一买鸡吉日 2023年9月15日买鸡好不好

    下一篇：2023年1月28日买牛好吗 2023年1月28日是买牛吉日吗