Java HashMap

HashMap的数据结构

HashMap是数组+链表+红黑树结构，这是在JDK1.8的时候设计的，为什么要这样设计呢？来分析下。
浅析HashMap原理 - 图1

HashMap红黑树分析

在jdk1.8就是引入了红黑树这一设计，当hash表的单一个链表长度超过了8个的时候，链表的结构就会变成红黑树结构。可以设计就是可以避免在很极端的情况下，链表的长度是很长很长的，结果在查询的时候就会变得很慢了。
红黑树查询： 它的性能跟折半查找差不多类似，时间复杂度O（logn）；
链表查询： 需要遍历全部元素，时间复杂度O（n）；
可以说红黑树是一种类似平衡的二叉查找树，优点就是平衡，就是左右子树它们的高度近乎是一致的，这样来防止退化成为链表。

红黑树的特征

（1）每个节点只能是红色或者黑色
（2）根节点必须是黑色
（3）红色的节点，它的叶节点只能是黑色
（4）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

重要方法之一：hash

hash这个方法的最主要目的，就是为了提高存储的数组的下标位置随机和分布均匀性，尽可能的不让出现hash冲突，看看源码。

  1. /**
  2. * 分析1：hash(key)
  3. * 作用：计算传入数据的哈希码（哈希值、Hash值）
  4. * 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
  5. * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
  6. * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
  7. */
  9. // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
  10. static final int hash(int h) {
  11.     h ^= k.hashCode(); 
  12.     h ^= (h >>> 20) ^ (h >>> 12);
  13.     return h ^ (h >>> 7) ^ (h >>> 4);
  14. }
  16. // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
  17. // 1. 取hashCode值：h = key.hashCode() 
  18. // 2. 高位参与低位的运算：h ^ (h >>> 16)  
  19. static final int hash(Object key) {
  20.     int h;
  21.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  22.     // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
  23.     // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
  24.     // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
  25. }
  27. /**
  28. * 计算存储位置的函数分析：indexFor(hash, table.length)
  29. * 注：该函数仅存在于JDK 1.7 ，JDK 1.8中实际上无该函数（直接用1条语句判断写出），但原理相同
  30. * 为了方便讲解，故提前到此讲解
  31. */
  32. static int indexFor(int h, int length) {  
  33.     return h & (length-1); 
  34.     // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
  35. }

那为什么不用hashcode来处理出来的哈希码来作为下标位置呢，原因就是会出现哈希码与数组的大小范围不匹配的这种情况，就无法匹配到存储的位置了。
那为什么采用哈希码与运算（数组长度-1）计算下标？
因为根据容量大小，按照需要取哈希码一定数量的地位作为数组的下标位置，来解决哈希码跟数组的大小范围不匹配的问题。

重要方法之二：put

先看put的流程图，再看源码
浅析HashMap原理 - 图2

  1. /**
  2. * 分析2：putVal(hash(key), key, value, false, true)
  3. */
  4. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  5.                boolean evict) {
  7.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  9.     // 1. 若哈希表的数组tab为空，则 通过resize() 创建
  10.     // 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建
  11.     // 关于resize（）的源码分析将在下面讲解扩容时详细分析，此处先跳过
  12.     if ((tab = table) == null || (n = tab.length) == 0)
  13.         n = (tab = resize()).length;
  15.     // 2. 计算插入存储的数组索引i：根据键值key计算的hash值 得到
  16.     // 此处的数组下标计算方式 = i = (n - 1) & hash，同JDK 1.7中的indexFor（），上面已详细描述
  18.     // 3. 插入时，需判断是否存在Hash冲突：
  19.     // 若不存在（即当前table[i] == null），则直接在该数组位置新建节点，插入完毕
  20.     // 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：a. 当前位置的key是否与需插入的key相同、b. 判断需插入的数据结构是否为红黑树 or 链表
  21.     if ((p = tab[i = (n - 1) & hash]) == null)
  22.         tab[i] = newNode(hash, key, value, null);  // newNode(hash, key, value, null)的源码 = new Node<>(hash, key, value, next)
  24.     else {
  25.         Node<K,V> e; K k;
  27.         // a. 判断 table[i]的元素的key是否与 需插入的key一样，若相同则 直接用新value 覆盖 旧value
  28.         // 判断原则：equals（）
  29.         if (p.hash == hash &&
  30.             ((k = p.key) == key || (key != null && key.equals(k))))
  31.             e = p;
  33.         // b. 继续判断：需插入的数据结构是否为红黑树 or 链表
  34.         // 若是红黑树，则直接在树中插入 or 更新键值对
  35.         else if (p instanceof TreeNode)
  36.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ->>分析3
  38.             // 若是链表,则在链表中插入 or 更新键值对
  39.             // i.  遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历节点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
  40.             // ii. 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
  41.             // 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
  43.             else {
  44.                 for (int binCount = 0; ; ++binCount) {
  45.                     // 对于ii：若数组的下1个位置，表示已到表尾也没有找到key值相同节点，则新建节点 = 插入节点
  46.                     // 注：此处是从链表尾插入，与JDK 1.7不同（从链表头插入，即永远都是添加到数组的位置，原来数组位置的数据则往后移）
  47.                     if ((e = p.next) == null) {
  48.                         p.next = newNode(hash, key, value, null);
  50.                         // 插入节点后，若链表节点>数阈值，则将链表转换为红黑树
  51.                         if (binCount >= TREEIFY_THRESHOLD - 1) 
  52.                             treeifyBin(tab, hash); // 树化操作
  53.                         break;
  54.                     }
  56.                     // 对于i
  57.                     if (e.hash == hash &&
  58.                         ((k = e.key) == key || (key != null && key.equals(k))))
  59.                         break;
  61.                     // 更新p指向下一个节点，继续遍历
  62.                     p = e;
  63.                 }
  64.             }
  66.         // 对i情况的后续操作：发现key已存在，直接用新value 覆盖 旧value & 返回旧value
  67.         if (e != null) { 
  68.             V oldValue = e.value;
  69.             if (!onlyIfAbsent || oldValue == null)
  70.                 e.value = value;
  71.             afterNodeAccess(e); // 替换旧值时会调用的方法（默认实现为空）
  72.             return oldValue;
  73.         }
  74.     }
  76.     ++modCount;
  78.     // 插入成功后，判断实际存在的键值对数量size > 最大容量threshold
  79.     // 若 > ，则进行扩容 ->>分析4（但单独讲解，请直接跳出该代码块）
  80.     if (++size > threshold)
  81.         resize();
  83.     afterNodeInsertion(evict);// 插入成功时会调用的方法（默认实现为空）
  84.     return null;
  86. }

重要方法之三：risize扩容机制

在resize的方法里，定义了一个叫oldCap的参数，它是记录了原来的table长度，接着又定义了newCap参数来记录最新的table长度，注意newCap它是oldCap长度的两倍。然后循环原来的table，再把原来table的元素放到新的table里。具体看流程图+源码
浅析HashMap原理 - 图3

  1. /**
  2. * 分析4：resize（）
  3. * 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
  4. */
  5. final Node<K,V>[] resize() {
  6.     Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
  7.     int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量 = 长度
  8.     int oldThr = threshold;// 扩容前的数组的阈值
  9.     int newCap, newThr = 0;
  11.     // 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
  12.     if (oldCap > 0) {
  13.         if (oldCap >= MAXIMUM_CAPACITY) {
  14.             threshold = Integer.MAX_VALUE;
  15.             return oldTab;
  16.         }
  18.         // 针对情况2：若无超过最大值，就扩充为原来的2倍
  19.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  20.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  21.             newThr = oldThr << 1; // 通过右移扩充2倍
  22.     }
  24.     // 针对情况1：初始化哈希表（采用指定 or 默认值）
  25.     else if (oldThr > 0) // initial capacity was placed in threshold
  26.         newCap = oldThr;
  28.     else {               // zero initial threshold signifies using defaults
  29.         newCap = DEFAULT_INITIAL_CAPACITY;
  30.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  31.     }
  33.     // 计算新的resize上限
  34.     if (newThr == 0) {
  35.         float ft = (float)newCap * loadFactor;
  36.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  37.                   (int)ft : Integer.MAX_VALUE);
  38.     }
  40.     threshold = newThr;
  41.     @SuppressWarnings({"rawtypes","unchecked"})
  42.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  43.     table = newTab;
  45.     if (oldTab != null) {
  46.         // 把每个bucket都移动到新的buckets中
  47.         for (int j = 0; j < oldCap; ++j) {
  48.             Node<K,V> e;
  49.             if ((e = oldTab[j]) != null) {
  50.                 oldTab[j] = null;
  52.                 if (e.next == null)
  53.                     newTab[e.hash & (newCap - 1)] = e;
  54.                 else if (e instanceof TreeNode)
  55.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  57.                 else { // 链表优化重hash的代码块
  58.                     Node<K,V> loHead = null, loTail = null;
  59.                     Node<K,V> hiHead = null, hiTail = null;
  60.                     Node<K,V> next;
  61.                     do {
  62.                         next = e.next;
  63.                         // 原索引
  64.                         if ((e.hash & oldCap) == 0) {
  65.                             if (loTail == null)
  66.                                 loHead = e;
  67.                             else
  68.                                 loTail.next = e;
  69.                             loTail = e;
  70.                         }
  71.                         // 原索引 + oldCap
  72.                         else {
  73.                             if (hiTail == null)
  74.                                 hiHead = e;
  75.                             else
  76.                                 hiTail.next = e;
  77.                             hiTail = e;
  78.                         }
  79.                     } while ((e = next) != null);
  80.                     // 原索引放到bucket里
  81.                     if (loTail != null) {
  82.                         loTail.next = null;
  83.                         newTab[j] = loHead;
  84.                     }
  85.                     // 原索引+oldCap放到bucket里
  86.                     if (hiTail != null) {
  87.                         hiTail.next = null;
  88.                         newTab[j + oldCap] = hiHead;
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.     }
  94.     return newTab;
  95. }