今天的文章将以一问一答的形式来跟大家一起分享HashMap，这样可能更有助于大家对HashMap的理解。
Q1：什么是HashMap?
HashMap是一种以Key(唯一性)-Value(可重复)形式储存键值对的集合，允许null键（仅一个）null值（可多个），每一对键值对以Entry的基本单位保存，键值对是无序的，HashMap的主干结构为数组，数组的初始长度一般为2的幂，数组的每个位置称为bucket(桶)，初始化为null。
Q2：HashMap的主要方法有哪几个？
put方法
put方法的作用是要将一个key-value键值对插入HashMap中，现在假设我们要put(“aaa”, 1)，首先会根据key求得该键值对插入的桶(index)，根据key求hashCode(aaa)，该值进行一次hash运算，求得hashCode(“aaa”).hash() 的值后，再跟数组的长度-1进行与运算就是aaa最后插入的位置index，有了index之后，会对该位置做一个判断，如果该位置目前为空，就将(“aaa”, 1)插入index对应的桶；毕竟数组的初始长度是有限的，当插入一部分数据后，此时我们要put(“ooo”, 3)，但发现根据“ooo”计算得到的index与“aaa”的相等，即两个不同的key值有相同的index，而且，随着插入的键值对越来越多，这样的情况不可避免，我们把该现象称为“哈希碰撞”，解决方法是把后来的键值使用尾插法插在先到键值对组成的链表中，这个链表并不能无限延长，当它的长度等于8时，再有新的entry想挂在链表尾部，链表就会转化成红黑树。所以，Jdk 1.8版的HashMap由数组+链表+红黑树组成，在Jdk 1.7中，HashMap由数组+链表组成。
get方法
了解了put方法，那get方法相信不难理解，HashMap的突出优点在于查找的时间复杂度为O(1)，因为存储的时候put(key, value)，所以get起来就很方便，下面，我们还是以get(“aaa”)为例，此时，首先要做的还是根据key去求得一个在数组里的桶位置(index)，key→index的方法跟put()方法一样，此时，若在数组index位的桶里的key正好是想get的key，那立刻返回该键值对；否则，需要从桶的位置开始顺着链表链表或红黑树一个一个找下来。
注意事项：get()方法其实是链表或红黑树的遍历查找指定key的过程；如果get(key)返回值为null，一种情况可能是该key不存在于HashMap中，另一种情况是该key对应的value为null。
Q3：为什么不直接使用hashCode，还要多进行一次hash计算？为什么计算数组索引的时候需要(n-1)&hash?
hash()
hashCode()其实是Object类里面的方法，之所以对key的hashCode要再进行一次hash()方法，主要是为了防止低质量的hashCode()，让key计算得到的index分布地更加均匀，以降低哈希碰撞的概率，可以说hash()方法的优劣，决定了哈希碰撞的频率低高。下面将hash方法的代码贴在这里：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看了以上的代码，可能你还会疑问，为什么hash()方法进行了右移16位和^位异或运算？
key的hashCode运算后，会得到一个32位的二进制数，将这个数右移16位相当于将它的高位挪到了低位，然后再跟它的hashCode值进行^位异或运算，位异或运算就是相同为0，不同为1，以“aaa”为例：
aaa：01101000010001100011000000000000
向右位移16：00000000000000000110100001000110
^位异或：01101000010001100101100001000110
发现没？右移16位，正好是32bit的一半，相当于让自己的高16位和低16位做异或运算，好混合原始hashCode(key)，以此加大低位的随机性。混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
(n-1)&hash
在Jdk 1.8中，index= (n-1)&hash，n是数组的长度，初始化一般为16 ，所以n-1的值为15，15用二进制表示为1111，接下来进行&运算，&运算的规则是两个都为1时得1，其余得0，如下所示：
hash：01101000010001100101100001000110
15：00000000000000000000000000001111
&： 00000000000000000000000000000110
结果为6，发现了吗？在n为2的幂时，n-1正好相当于一个“低位掩码”， &操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。我们可以看看如果n为11，结果如下：
hash：01101000010001100101100001000110
10：00000000000000000000000000001010
&： 00000000000000000000000000000010
所以，n的长度为2的幂时，n-1的所有二进制位都为1，只有全是1 ，才能最大限度的利用 hash 值，才能有更多的散列结果。如果是 1010，有的散列结果是永远都不会出现的，比如 0111，0101，1111，1110…，只要 & 之前的数有 0， 对应的 1 肯定就不会出现（因为只有都是1才会为1）。大大限制了散列的范围。
Q4：HashMap的扩容是如何进行的？
在之前我们说过，HashMap的主干是数组，但数组在Java中长度是固定的，在1.8版HashMap中，桶数组的初始长度是16，但由于put的键值对增多，
挂在数组上的链表也越来越多，其实是会降低HashMap的查找效率的，所以必须要扩容，是否扩容取决于关键点threshold，threshold = 数组长度*装载因子（0.75f），
当前通数组到达阈值后，HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。
Q5：什么是哈希碰撞，HashMap如何解决Hash冲突？
哈希碰撞也称为哈希冲突说直接一点就是不同key的散列值相同，目前解决哈希冲突的方案有以下几种：
链表法：
在Java的HashMap中，使用该方法缓解哈希碰撞。就是直接将冲突的键值对以链表的形式挂在桶数组元素的尾部（1.8为尾插法，之前版本为头插法），但链表长度不能超过8个，否则会影响HashMap的查找性能。
优点：处理冲突简单；无堆积现象；删除操作方便。
缺点：链表会占用额外空间。
开放寻址法：
在M>N的前提下，大小为M的桶数组，装下N个键值对，所以在发生哈希碰撞时，需要数组中的空位来解决哈希冲突。它的核心思想是：与其将内存用作链表，不如用作数组里的空桶。
缺点：删除节点时不方便。
优点：数据规模小时，节省空间。
rehash法：
发生哈希冲突时，换一个哈希函数计算index，如果还是冲突，再换一个，以此类推，直到不再冲突。缺点：耗费的时间比较多。
Q6：为什么HashMap的最大容量是 1 << 30？
阅读源码的时候，可能有小伙伴发现HashMap的最大容量为“static final int MAXIMUM_CAPACITY = 1 << 30”，1左移30位是什么意思呢？主要是因为int类型的数据在JVM里占用的内存为32位，4字节，所以按照理论来说，最大容量不应该是1<<31吗？但之前我们说过，数组的长度必须为2的n次幂，数组的索引用int来表示，所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂，而最接近int最大值的2个指数幂用位运算符表示就是 1 << 30。
网友评论