HashMap底层原理

• 数组作为key的集合
• 链表或红黑树作为下标对应值的集合
• put操作
  • 首先计算key的hashCode,然后计算hashCode模与桶.得到下标值
  • 再将key-value封装为Entry对象,存入对应的链表或红黑树
• 在jdk1.7中,全使用链表
• 在jdk1.8中,根据长度选择使用链表或者红黑树

HashMap1.7和1.8的扩容机制

JDK 1.7

1. 生成新数组,根据负载因子决定长度
2. 遍历老数组中每个位置上的链表上的每个元素
3. 取每个元素的key,并基于新数组长度,计算出每个元素在新数组中的下标
4. 将元素添加到新数组中去
5. 所有元素转移完了之后,将新数组赋值给HahsMap对象的table属性

JDK1.8

1. 生成新数组
2. 遍历老数组中每个位置上的链表或红黑树
3. 如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中区
4. 如果是红黑树,则先遍历红黑树,先计算出红黑树中每个元素对应在新数组中的下标位置
   1. 统计每个下标位置的元素个数
   2. 如果该位置下的元素超过8,则生成一个新的红黑树,并将根节点的添加到新数组的对应位置
   3. 如果该位置下的元素个数没有超过8,则生成一个链表,并将链表的头节点添加到新数组的对应位置
5. 所有元素转移完成后,将新数组赋值给HashMap对象的table属性