对于hash函数，具体的来看下源码
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
以上可以看到key==null时，直接返回0，所以HashMap中键为NULL的键值对，一定在第一个桶中。
h >>> 16是用来取出h的高16位(>>>是无符号右移) 如下展示：
0000 0100 1011 0011 1101 1111 1110 0001
>>> 16
0000 0000 0000 0000 0000 0100 1011 0011
通过之前putVal的源码可以知道，HashMap是用(length - 1) & hash来计算数组下标的。绝大多数情况下length一般都小于2^16即小于65536。所以hash & (length-1)；结果始终是hash的低16位与（length-1）进行&运算。要是能让hash的高16位也参与运算，会让得到的下标更加散列。
如何让高16也参与运算呢。方法就是让hashCode()和自己的高16位进行^运算。由于与运单和或运单都会使得结果偏向0或者1，并不是均匀的概念，所以用异或。
结合源码来看HashMap的get操作：
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //如果是红黑树，就调用树的查找方法，否则遍历链表直到找到 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
在这里能够根据key快速的取到value，除了和HashMap的数据结构密不可分外，还和Node有莫大的关系。在前面就已经提到过，HashMap在存储过程中并没有将key/value分开来存储，而是当做一个整体key-value来处理的，这个整体就是Node对象。
1.4 为什么HashMap的底层数组长度总是2的n次方
当底层数组的length为2的n次方时， hash & (length - 1)就相当于对length取模，其效率要比直接取模高得多，这是HashMap在效率上的一个优化。
我们希望HashMap中的元素存放的越均匀越好。最理想的效果是，Node数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较Key，而且空间利用率最大。
那如何计算才会分布最均匀呢？正如上一节提到的，HashMap采用了一个分两步走的哈希策略：
使用hash()方法对Key的hashCode进行重新计算，以防止质量低下的hashCode()函数实现。由于HashMap的支撑数组长度总是2的倍数，通过右移可以使低位的数据尽量的不同，从而使Key的hash值的分布尽量均匀；使用hash & (length - 1)方法进行取余运算，以使每个键值对的插入位置尽量分布均匀；由于length是2的整数幂，length-1的低位就全是1，高位全部是0。在与hash值进行低位&运算时，低位的值总是与原来hash值相同，高位&运算时值为0。这就保证了不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。
1.5 HashMap的扩容
随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度*加载因子）。但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。
首先回答一个问题，在插入一个临界节点时，HashMap是先扩容后插入还是先插入后扩容？这样选取的优势是什么？
答案是：先插入后扩容。通过查看putVal方法的源码可以发现是先执行完新节点的插入后，然后再做size是否大于threshold的判断的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... //如果插入新结点后的size超过了临界值，就扩容，注意是先插入节点再扩容 if (++size > threshold) resize(); //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现 afterNodeInsertion(evict); return null; }
为什么是先插入后扩容？源码已经很清楚的表达了扩容原因，调用put不一定是新增数据，还可能是覆盖掉原来的数据，这里就存在一个key的比较问题。以先扩容为例，先比较是否是新增的数据，再判断增加数据后是否要扩容，这样比较会浪费时间，而先插入后扩容，就有可能在中途直接通过return返回了（本次put是覆盖操作，size不变不需要扩容），这样可以提高效率的。
JDK1.8相对于JDK1.7对HashMap的实现有较大改进，做了很多优化，链表转红黑树是其中的一项，其实扩容方法JDK1.8也有优化，与JDK1.7有较大差别。
JDK1.8中resize方法源码如下：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 原来的容量就已经超过最大值就不再扩容了，就只好随你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 没超过最大值，就扩容为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize上限，即新的threshold值 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) { // 把旧的bucket都移动到新的buckets中 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); // 扩容后，键值对在新table数组中的位置与旧数组中一样 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 扩容后，键值对在新table数组中的位置与旧数组中不一样 // 新的位置=原来的位置 + oldCap if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
必要的位置已经加了注释。最让人疑惑的有两个点：
为什么（e.hash & oldCap）== 0时就放入lo链表，否则就是hi链表; 为什么 j + oldCap就是键值对在新的table数组中的位置；其实这里包含着一些数学技巧。类似于上一小节为什么HashMap中数组的长度总是取2的整数次幂。
查看源码，我们发现扩容时，使用的是2次幂的扩展即长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图中上半部分表示扩容前的key1和key2两个Node的索引位置，图中下半部分表示扩容后key1和key2两个Node新的索引位置。
元素在重新计算hash之后，因为n变为2倍，那么n-1在高位多1bit，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，这个设计确实非常的巧妙，既省去了重新hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了，这一块就是JDK1.8新增的优化点。
1.6 HashMap为什么引入红黑树而不是AVL树
首先要说明的是引入红黑树是了防止多次发生hash冲突时，链表长度过长，查找的时间复杂度会变成O(N)，同时同一位置再次发生hash冲突时采用尾插法插入的时间复杂度也会变成O(N)。用了红黑树可以把查找以及插入的时间复杂度都降低成O(logN)。
那么接下来问题就变成了：有了二叉查找树、平衡树（AVL）为啥还需要红黑树？
二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；任意节点的左、右子树也分别为二叉查找树; 没有键值相等的节点（no duplicate nodes） 因为一棵由N个结点随机构造的二叉查找树的高度为logN，所以顺理成章，二叉查找树的一般操作的执行时间为O(logN)。但二叉查找树若退化成了一棵具有N个结点的线性链后，则这些操作最坏情况运行时间为O(N)。可想而知，我们不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡二叉树，即AVL树，它对二叉查找树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行左旋或右旋，使之平衡。
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logN)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树，但是提出了为节点增加颜色，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，相较于AVL树为了维持平衡的开销要小得多。
AVL树是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多，所以红黑树的插入效率相对于AVL树更高。单单在查找方面比较效率的话，由于AVL高度平衡，因此AVL树的查找效率比红黑树更高。
对主要的几种平衡树作个比较，发现红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。实际应用中，若搜索的频率远远大于插入和删除，那么选择AVL，如果发生搜索和插入删除操作的频率差不多，应该选择红黑树。
