HashMap是以hash操作作为散列依据。但是又与传统的hash存在着少许的优化。其hash值是key的hashcode与其hashcode右移16位的异或结果。在put方法中，将取出的hash值与当前的hashmap容量-1进行与运算。得到的就是位桶的下标。那么为何需要使用key.hashCode() ^ h>>>16的方式来计算hash值呢。其实从微观的角度来看，这种方法与直接去key的哈希值返回在功能实现上没有差别。但是由于最终获取下表是对二进制数组最后几位的与操作。所以直接取hash值会丢失高位的数据，从而增大冲突引起的可能。由于hash值是32位的二进制数。将高位的16位于低位的16位进行异或操作，即可将高位的信息存储到低位。因此该函数也叫做扰乱函数。目的就是减少冲突出现的可能性。而官方给出的测试报告也验证了这一点。直接使用key的hash算法与扰乱函数的hash算法冲突概率相差10%左右。
>static >final >int hash(Object key) { >int h; >return (key == >null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } n = table.length; index = （n-1） & hash;
根据以上可知，hashcode是一个32位的值，用高16位与低16位进行异或，原因在于求index是是用 （n-1） & hash ，如果hashmap的capcity很小的话，那么对于两个高位不同，低位相同的hashcode，可能最终会装入同一个桶中。那么会造成hash冲突，好的散列函数，应该尽量在计算hash时，把所有的位的信息都用上，这样才能尽可能避免冲突。这就是为什么用高16位与低16位进行异或的原因。
为什么capcity是2的幂？因为 算index时用的是（n-1） & hash，这样就能保证n -1是全为1的二进制数，如果不全为1的话，存在某一位为0，那么0，1与0与的结果都是0，这样便有可能将两个hash不同的值最终装入同一个桶中，造成冲突。所以必须是2的幂。例子：十进制16 转化为 二进制10000，则16-1为 1111
在算index时，用位运算（n-1） & hash而不是模运算 hash % n的好处（在HashTable中依旧是取模运算）？
位运算消耗资源更少，更有效率
避免了hashcode为负数的情况
六、扩容机制resize
在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。
HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。
>final Node<K,V>[] resize() { >//> 拿到数组桶 Node<K,V>[] oldTab = table; >int oldCap = (oldTab == >null) ? 0 : oldTab.length; >int oldThr = threshold; >int newCap, newThr = 0; >//> 如果数组桶的容量大与0 >if (oldCap > 0) { >//> 如果比最大值还大，则赋值为最大值 >if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; >return oldTab; } >//> 如果扩容后小于最大值 而且 旧数组桶大于初始容量16， 阈值左移1(扩大2倍) >else >if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; >//> double threshold } >//> 如果数组桶容量<=0 且 旧阈值 >0 >else >if (oldThr > 0) >//> initial capacity was placed in threshold >//> 新容量=旧阈值 newCap = oldThr; >//> 如果数组桶容量<=0 且 旧阈值 <=0 >else { >//> zero initial threshold signifies using defaults >//> 新容量=默认容量 newCap = DEFAULT_INITIAL_CAPACITY; >//> 新阈值= 负载因子*默认容量 newThr = (>int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } >//> 如果新阈值为0 >if (newThr == 0) { >//> 重新计算阈值 >float ft = (>float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (>float)MAXIMUM_CAPACITY ? (>int)ft : Integer.MAX_VALUE); } >//> 更新阈值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) >//> 创建新数组 Node<K,V>[] newTab = (Node<K,V>[])>new Node[newCap]; >//> 覆盖数组桶 table = newTab; >//> 如果旧数组桶不是空，则遍历桶数组，并将键值对映射到新的桶数组中 >if (oldTab != >null) { >for (>int j = 0; j < oldCap; ++j) { Node<K,V> e; >if ((e = oldTab[j]) != >null) { oldTab[j] = >null; >if (e.next == >null) newTab[e.hash & (newCap - 1)] = e; >//> 如果是红黑树 >else >if (e >instanceof TreeNode) >//> 重新映射时，需要对红黑树进行拆分 ((TreeNode<K,V>)e).split(>this, newTab, j, oldCap); >else { >//> preserve order >//> 如果不是红黑树，则按链表处理 Node<K,V> loHead = >null, loTail = >null; Node<K,V> hiHead = >null, hiTail = >null; Node<K,V> next; >//> 遍历链表，并将链表节点按原顺序进行分组 >do { next = e.next; >if ((e.hash & oldCap) == 0) { >if (loTail == >null) loHead = e; >else loTail.next = e; loTail = e; } >else { >if (hiTail == >null) hiHead = e; >else hiTail.next = e; hiTail = e; } } >while ((e = next) != >null); >//> 将分组后的链表映射到新桶中 >if (loTail != >null) { loTail.next = >null; newTab[j] = loHead; } >if (hiTail != >null) { hiTail.next = >null; newTab[j + oldCap] = hiHead; } } } } } >return newTab; }
整体步骤：
计算新桶数组的容量 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。
七、常用Map遍历方法