HashMap底层的数据结构
HashMap底层是一个hash表加链表结构，jdk1.7以后，链表长度达到阈值(8)以后会转成红黑树。
下面我们通过源码看看HashMap的底层实现。
源码解析
这里主要分析两个重要方法：put()和resize()方法
put()方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}put()方法中会将key的hash值传入到putVal()方法中。
hash()方法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}(h = key.hashCode()) ^ (h >>> 16)这行代码叫做扰动函数，它可以将哈希值的高位与低位混合，以减少碰撞率。
这里提一下^异或运算符，我们平时写代码的时候可能不太常用到这个运算符，但是它在很多源码中都会出现，因为它属于位运算符，这必然决定了它的效率非常高，而且它还有个用途，就是用来变量交换。
^有两条重要性质：A^A=0，A^0=A。利用这两个性质，我们可以实现变量交换，而且不需要使用中间变量temp。
a = a ^ b;//a充当tempb = b ^ a;//b^a=b^a^b=aa = b ^ a;//b^a=a^a^b=bputVal()方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //tab是外层的Node数组，如果tab是空的就通过扩容方法创建。 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //取模运算，如果对应的table位置里没有Node，就直接放进去。 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //否则，就是哈希冲突 else { Node<K,V> e; K k; //两个key相同，直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //p是树类型，进行红黑树添加节点操作 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //否则是链表操作 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果链表长度超过8，就会通过treeifyBin()方法转成红黑树（HashMap长度大于64才会转红黑树） if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //节点数量超过最大阈值，就要进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}put()方法中计算元素要添加到table中的位置时，采用的是(n - 1) & hash来实现取模。这种做法有什么好处呢？
正常情况下，我们取模都是采用%，也就是hash % 16，这样会得到0-15之间的值。但是源码中采用的是&与运算，这种做法怎么会是取模呢？记住：&与运算，在二进制中，两个为1则为1，例如
16 = 0001 0000;15 = 0000 1111;hash = 0111 0110;15 & hash = 0000 0110;结果的高四位肯定是0000，最大值一定是0000 1111，也就是15，这种也保证了结果在0-15之间。&是位运算，效率要比%取模高很多。但是这种做法需要保证table的长度必须是2的n次方，这样n-1才会保证高位都是0，低位都是1。通过这里也能看出高位是没有参与计算的，所以上面的hash()算法需要h >>> 16了。
resize()方法
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //第一次put元素时，table是空的，oldCap=0，最后newCap=初始容量，newThr=负载因子×初始容量 //table=(Node<K,V>[])new Node[newCap];通过扩容方法达到初始化作用 //第二次进来时，oldTab.length=16;oldCap=16; int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldThr=16*0.75=12; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { //如果oldCap超过最大值，threshold就设置为Integer最大值 threshold = Integer.MAX_VALUE; return oldTab; } //newCap=oldCap<<1=oldCap*2=32 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //newThr=24 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); } //第一次put元素时，newThr == 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) {//oldCap=16 Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) //取模，和putVal里(n-1)&hash一样 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; //oldCap=16=0001 0000 //任何数&oldCap，要么是0，要么是16 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;}扩容：首先是容量扩充为原来的两倍，然后链表中的元素，如果hash值&oldCap的值是0，则索引不变，如果值是oldCap，则索引值+oldCap。
总结
HashMap里的内容太多了，尤其是1.7以后引入红黑树，就更复杂了，我这里只是说了一下里面比较重要的两个方法。当然，HashMap也是面试的高频问题之一。如果在高并发的情况下，推荐使用ConcurrentHashMap，这是HashMap的线程安全版，里面添加了分段锁，这个后面再详说。
<center>扫一扫，关注我</center>