java面试——集合HashMap源码理解问题

HashMap

• 底层数据结构，1.7与1.8有何不同？
  • 1.7 数组+链表，1.8 数组+ （链表 | 红黑树）
• 为何要用红黑树，为何一上来不树化，树化阈值为何是8，何时会树化，何时会退化为链表?
  • 链表太长会影响性能
  • 链表短时，树化效率并不比链表高，占内存多
  • 红黑树用来避免DoS攻击，防止链表超长时性能下降，树化应当是偶然情况，正常情况下链表长度不会超过8。hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是0.00000006，选择8就是为了让树化几率足够小。
  • 条件1：链表长度是大于8，条件2：数组长度大于64。若条件1成立且数组长度小于64时会扩容
  • 情况1：扩容后拆分树，树节点小于等于6。情况2：退化情况2: remove树节点时，移除前判断，若root、root.left、root.right、root.left.left有一个为null ，也会退化为链表

扩容、树化：元素个数超过数组的3/4时，会进行扩容，树化阈值是8，条件1：链表长度是大于8，条件2：数组长度大于64。若数组长度小于64时会扩容，万不得已才树化。

• 索引如何计算? hashCode 都有了，为何还要提供 hash()方法?数组容量为何是2的n次幂?

  • 计算对象的hashCode()，再进行调用HashMap的 hash()方法进行二次哈希，最后&(capacity - 1)（或者取模数组长度）得到索引。
  • 为了使最终用来计算索引的hashcode值分布得更均匀，降低链表长度。
  • 计算索引时，如果是2的n次幂可以使用位与运算代替取模，效率更高;扩容时 hash & （按位与运算）oldCap==0的元素留在原来位置，否则新位置=旧位置+ oldCap

• 介绍一下put方法流程，1.7和1.8有何不同?

  • HashMap是懒惰创建数组的，在首次使用才创建数组
  • 计算索引
  • 如果索引还没被占用，创建Node占位返回
  • 如果索引已经被占用
    • 已经是TreeNode走红黑树的添加或更新逻辑
    • 是普通Node，走链表的添加或更新逻辑，如果超过树化阈值，走树化逻辑
  • 返回前检查容量是否超扩容阈值，如果超过就扩容。
  • 不同点
    • 链表插入节点时，1.7是头插法、1.8是尾插法
    • 1.7是大于等于阈值且插入时该位置已经被占用才扩容，而1.8是大于阈值就扩容
    • 1.8在扩容计算Node索引时，会优化

• 加载因子为何默认是0.75f

  • 在空间占用何查询时间之间取得较好的平衡
    • 大了，链表可能过长
    • 小了，经常扩容，浪费空间

• 多线程下会有什么问题？

  • 可能会丢失数据

  • 扩容死链（1.7）

  • 数据错乱（1.7、.18）

• key能否为null，作为key的对象有什么要求？

  • HashMap的key可以为null，但其他的Map就不一定了。
  • 作为key的对象，必须实现hashCode何equals，并且key的内容不能修改（不可变）。