一. HashMap的数据结构

  1. 数据结构演示地址：
  2. https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1.1 jdk1.7数据结构

HashMap源码分析 - 图1

1.2 jdk1.8数据结构

HashMap源码分析 - 图2

1.3 负载因子为什么是0.75

  1. HashMap中注释给了解释
  3. 看了个例子：
  4. 如果是0.5 ， 那么每次达到容量的一半就进行扩容，默认容量是16， 达到8就扩容成32，达到16就扩容成64， 最终使用空间和未使用空间的差值会逐渐增加，空间利用率低下。  如果是1，那意味着每次空间使用完毕才扩容，在一定程度上会增加put时候的时间
  6. 可以参考这位大佬的解释
  7. https://www.jianshu.com/p/64f6de3ffcc1

HashMap源码分析 - 图3

二.HashMap操作

2.1 运算规则

  2. 1.位异或运算（^）
  3. 运算规则是：从高位开始比较，如果相同则为0，不相同则为1。
  4. 比如：8^11
  5. 8转为二进制是1000，11转为二进制是1011.从高位开始比较得到的是：0011.然后二进制转为十进制，就是Integer.parseInt("0011",2)=3;
  7. 2.位与运算符（&）
  8. 运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
  9. 比如：129&128
  10. 129转换成二进制就是10000001，128转换成二进制就是10000000。从高位开始比较得到，得到10000000，即128
  12. 3.位或运算符（|）
  13. 运算规则：两个数都转为二进制，然后从高位开始比较，两个数只要有一个为1则为1，否则就为0。
  14. 比如：129|128
  15. 129转换成二进制就是10000001，128转换成二进制就是10000000。从高位开始比较得到，得到10000001，即129
  17. 4.位非运算符（~）
  18. https://www.cnblogs.com/bibiafa/p/9389213.html

2.2 put流程

HashMap源码分析 - 图4

  1. 当我们调用put方法其内部会调用putVal方法，第一个参数需要对key求hash值，目的是为了减少hash碰撞
  1. public V put(K key, V value) {
  2.         return putVal(hash(key), key, value, false, true);//调用Map的putVal方法
  3. }
  1. hash(key)这个方法会生成hash，干扰（扰动）函数
  2. 为了防止一些实现比较差的 hashCode() 方法，减少碰撞，尽可能使元素更散列地存储
  3. 同时这个方法也说明了HashMap是支持key为空的，如果为空直接就会返回hash值为0
  1. static final int hash(Object key) {//干扰（扰动）函数；通过key计算hash值，仅仅是hash值，不是存储位置，目的：让hash更散列
  2.         int h;
  3.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//hash后对右16（空位补0）后进行异或，key为null，表示HashMap是支持Key为空的，
  4. }
  1. putVal方法
  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,//onlyIfAbsent:表示是否不覆盖已有的值；evict：false表示table为创建状态
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         if ((tab = table) == null || (n = tab.length) == 0)//数组是否null或者==0，第1次put为空
  5.             n = (tab = resize()).length;//初始化数组(or扩容)！！！！！！！！！！！！！
  6.         if ((p = tab[i = (n - 1) & hash]) == null)//寻址：(n - 1) & hash重要，16-1 按位与hash，为null表示没有值
  7.             tab[i] = newNode(hash, key, value, null);//等空，直接插入
  8.         else {
  9.             Node<K,V> e; K k;
  10.             if (p.hash == hash &&//判断key是否相等
  11.                 ((k = p.key) == key || (key != null && key.equals(k))))
  12.                 e = p;//将第一个元素赋值给e，用e来记录；跳到646Line
  13.             else if (p instanceof TreeNode)//判断是否红黑树！
  14.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  15.             else { //生成链表(操作链表),开始遍历链表
  16.                 for (int binCount = 0; ; ++binCount) {
  17.                     if ((e = p.next) == null) {//p.next为空表明处于链表的尾部，1、生成链表  2、已经是链表！！！！  存储位置相等
  18.                         p.next = newNode(hash, key, value, null);// 直接创建
  19.                         if (binCount >= TREEIFY_THRESHOLD - 1) //链表长度如果>8转红黑树（or 扩容），-1是因为binCount从0开始
  20.                             treeifyBin(tab, hash);//树化；还需要判断是否大于64，否则扩容
  21.                         break;
  22.                     }
  23.                     if (e.hash == hash &&
  24.                         ((k = e.key) == key || (key != null && key.equals(k))))//对链表节点中数据进行覆盖判断
  25.                         break;
  26.                     p = e;
  27.                 }
  28.             }
  29.             if (e != null) { // key已经存在
  30.                 V oldValue = e.value;
  31.                 if (!onlyIfAbsent || oldValue == null)
  32.                     e.value = value;// 用新的value值去覆盖老的value值
  33.                 afterNodeAccess(e);
  34.                 return oldValue;// 返回覆盖前的value值，put的返回值
  35.             }
  36.         }
  37.         ++modCount;//用来记录HashMap的修改次数
  38.         if (++size > threshold)//扩容
  39.             resize();//如果size大于threshold,就需要进行扩容
  40.         afterNodeInsertion(evict);
  41.         return null;
  42. }
  1. 问题：这里在寻址的时候为什么不用取模运算而是用位与运算
  3. 位与运算操作的是二进制效率要远快于取模运算
  4. 这里可以进行循环测试一下

HashMap源码分析 - 图5

2.3 resize（扩容流程）

  1. final Node<K,V>[] resize() {
  2.         Node<K,V>[] oldTab = table;
  3.         int oldCap = (oldTab == null) ? 0 : oldTab.length;//数组容量（旧）
  4.         int oldThr = threshold;//扩容临界点(旧)
  5.         int newCap, newThr = 0;//数组容量（新）、扩容临界点(新)
  6.         if (oldCap > 0) {
  7.             if (oldCap >= MAXIMUM_CAPACITY) {
  8.                 threshold = Integer.MAX_VALUE;
  9.                 return oldTab;
  10.             }
  11.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//扩容2倍:oldCap << 1，左移1位，相当于oldCap乘以2的1次方
  12.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  13.                 newThr = oldThr << 1; // 扩容2倍:将阈值threshold*2得到新的阈值
  14.         }
  15.         else if (oldThr > 0) // HashMap(int initialCapacity, float loadFactor)调用
  16.             newCap = oldThr;
  17.         else {               // zero initial threshold signifies using defaults
  18.             newCap = DEFAULT_INITIAL_CAPACITY;//第一次put！！！！！！！！！！！！！！！！！！
  19.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//扩充阈值
  20.         }
  21.         if (newThr == 0) {//如果新阈值为0，根据负载因子设置新阈值
  22.             float ft = (float)newCap * loadFactor;
  23.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  24.                       (int)ft : Integer.MAX_VALUE);
  25.         }
  26.         threshold = newThr;//最后赋值给全局变量
  27.         @SuppressWarnings({"rawtypes","unchecked"})
  28.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  29.         table = newTab;
  30.         if (oldTab != null) {
  31.             for (int j = 0; j < oldCap; ++j) {  //如果旧的数组中有数据，循环
  32.                 Node<K,V> e;
  33.                 if ((e = oldTab[j]) != null) {
  34.                     oldTab[j] = null;//gc处理
  35.                     if (e.next == null)
  36.                         newTab[e.hash & (newCap - 1)] = e;//只一个节点，赋值，返回
  37.                     else if (e instanceof TreeNode)//红黑结构
  38.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  39.                     else {
  40.                         Node<K,V> loHead = null, loTail = null;//低位链表（原位置i）
  41.                         Node<K,V> hiHead = null, hiTail = null;//高位链表（i+n位置）
  42.                         Node<K,V> next;
  43.                         do {
  44.                             next = e.next;
  45.                             if ((e.hash & oldCap) == 0) {// 如果为0，元素位置在扩容后数组中的位置没有发生改变（低位）
  46.                                 if (loTail == null)
  47.                                     loHead = e;// 头节点
  48.                                 else
  49.                                     loTail.next = e;
  50.                                 loTail = e;
  51.                             }
  52.                             else {//不为0，元素位置在扩容后数组中的位置发生了改变，新的下标位置是（原下标位置+原数组长）
  53.                                 if (hiTail == null)
  54.                                     hiHead = e;
  55.                                 else
  56.                                     hiTail.next = e;
  57.                                 hiTail = e;
  58.                             }
  59.                         } while ((e = next) != null);
  60.                         if (loTail != null) {
  61.                             loTail.next = null;
  62.                             newTab[j] = loHead;//下标：原位置
  63.                         }
  64.                         if (hiTail != null) {
  65.                             hiTail.next = null;
  66.                             newTab[j + oldCap] = hiHead;//下标：原位置+原数组长度
  67.                         }
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.         return newTab;//返回新数组
  73. }
  1. 在put的时候如果数组占得元素已经大于阈值了就会引起扩容
  2. if (++size > threshold)//扩容
  3. resize();
  5. 这里以图示举例(插入完k后 下标为1的链表扩容流程 没有变红黑树)

HashMap源码分析 - 图6

  1. Node<K,V> loHead = null, loTail = null;//低位链表（原位置i）
  2. Node<K,V> hiHead = null, hiTail = null;//高位链表（i+n位置）
  3. (e.hash & oldCap) == 0 //判断是否需要换位置
  4. hash ：通过扰动函数生成的hash
  5. oldCap：原来数组长度
  6. 假设ACD需要移动位置BEF不需要移动位置

扩容resize（）第一次流程A

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=A
  3. next=B
  4. Node<K,V> loHead = A, loTail = A;//低位链表（原位置i）
  5. Node<K,V> hiHead = null, hiTail = null;//高位链表（i+n位置）

第二次流程B

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=B
  3. next=C
  4. Node<K,V> loHead = A, loTail = A;//低位链表（原位置i）
  5. Node<K,V> hiHead = B, hiTail = B;//高位链表（i+n位置）

第三次流程C

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=C
  3. next=D
  4. Node<K,V> loHead = A, loTail = C;//低位链表（原位置i）
  5. Node<K,V> hiHead = B, hiTail = B;//高位链表（i+n位置）

第四次流程D

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=D
  3. next=E
  4. Node<K,V> loHead = A, loTail = D;//低位链表（原位置i）
  5. Node<K,V> hiHead = B, hiTail = B;//高位链表（i+n位置）

第五次流程E

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=E
  3. next=F
  4. Node<K,V> loHead = A, loTail = D;//低位链表（原位置i）
  5. Node<K,V> hiHead = B, hiTail = E;//高位链表（i+n位置）

第六次流程F

  1. 通过e.hash & oldCap算法判断是否为0 如果为0不移动位置，
  2. e=F
  3. next=null
  4. Node<K,V> loHead = A, loTail = D;//低位链表（原位置i）
  5. Node<K,V> hiHead = B, hiTail = F;//高位链表（i+n位置）
  1. //将lohead链放在新数组的原来位置 将hiHead 链在原来位置上+老数组长度
  2. newTab[j] = loHead;//下标：原位置
  3. newTab[j + oldCap] = hiHead;//下标：原位置+原数组长度

HashMap源码分析 - 图7