HashMap作为常用的Map类，他是基于哈希表实现，继承了AbstractMap并实现了Map接口.
哈希表就是把hash值映射到内存地址，即根据键获取对应的值,并将其存储到内存地址，而HashMap是根据键值的hash值来决定对应值的存储位置，通过这种索引方式，HashMap获取数据的速度非常快。 当然根据hash值，会有多个值的hash值是一样的，这样就会发生Hash冲突，那么如何解决呢，其实有很多方案
- 开放地址法
- 在哈希函数法
- 链地址法
开放地址法，就是当发生冲突的时候，如果哈希表没有满，说明哈希表必然还有空位置，那么可以把key存放到冲突位置的后面，同时会带来查找，扩容等问题，因此不建议使用
在哈希函数法，就是产生地址冲突时，再计算另一个哈希函数地址，知道不冲突为止，这种方法不易产生聚集，但是增加了计算时间，如果我们不考虑计算时间，且对查询元素的要求较高，可以采用这种方式
而HashMap则综合考虑所有因素，采用链地址法，这种方式采用数组和链表的数据结构，当发生哈希冲突的时候， 用一个链表结构存储hash值的数据
HashMap重要的属性
从HashMap的源码中,我们发现，HashMap是一个由一个Node数组构成，每个Node包含一个key-value键值对
transient Node[] table;
Node类作为HashMap中的一个内部类，除了key,value两个属性，还定义一个next指针,当存在哈希冲突的时候,HashMap会把之前数组中相同的hash值对应的存储的Node指向新增的相同哈希值的Node对象的引用。
static class Node implements Map.Entry {final int hash;final K key; V value; Node next; Node(int hash, K key, V value, Node next) {this.hash = hash;this.key = key;this.value = value;this.next = next; }}
HashMap还有两个重要的属性，加载因子(loadFactor)和边界值(threshold).在初始化HashMap时,就会涉及到这两个关键初始化参数
int threshold;final float loadFactor;
loadFactor属性用来间接设置Entry数组的内存大小。他的初始值是0.75。为什么是0.75呢 这是因为使用链表法的哈希表来说,查找一个元素的平均时间是O(1+N),其中N是代表遍历链表的长度,因为加载因子是扩容的参考标准,如果加载因子过大，就会产生更多的哈希冲突，这样导致数组的链表长度增加，影响查询效率,比如,把0.75改成1，这个时候数组的长度为16的时候，才会进行扩容。 Entry数组的Threshold是通过初试容量和LoadFactor计算所得,默认情况下边界值=12，如果HashMap中的Node的数量超过边界值，HashMap就会调用resize方法重新分配table数组,这样会导致HashMap的数组复制，迁移到另外一块内存，从而影响HashMap的效率
HashMap添加元素
在初始化完后，当元素添加到HashMap中的时候，我们会调用put,首先会根据该key的hashCode()返回值,再通过hash()方法计算hashcode值，在通过putval方法中(n-1)&hash决定该Node的存储位置.
public V put(K key, V value) {return putVal(hash(key), key, value, false, true); }
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//通过putVal方法中的(n - 1) & hash决定该Node的存储位置if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
为什么我们不是用对象的hashCode的值呢,比如添加两个对象a和b,如果数组的长度是16,使用(16-1)&a.hashCode和(16-1)&b.hashCode计算hash值,而15的二级制为0000000000000000000000000001111,假设对象a的hashCode为1000010001110001000001111000000,对象b的hashCode为0111011100111000101000010100000我会发现计算结果都是0,这样哈希结果就是不太优秀，不是好算法。 然后我们使用hashCode右移16位,(h>>>16)也就是去int的一半，刚好就可以将改二进制对半切开,并使用位异或运算,(如果两个数对应的位置相反，则为1，否则为0),
这样就能避免上面的情况发生,这就是hash()方法具体实现方法,尽量打乱hashCode真正参与运算低16位.
那为什么要设置成(n-1)&hash,那是因为哈希表习惯将长度设置为2的n次方,这样恰好计算你的索引值在数组table数组索引之内.
元素添加的逻辑
在获取Node位置后，如果存在不在哈希表中,就新增一个Node,并添加哈希表中,整个流程如下
从上面看到，如果链表的长度超过8的时候，链表就会转变成红黑树，因为我们不在担心链表过长导致查询时间复杂度的问题.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)//1、判断当table为null或者tab的长度为0时，即table尚未初始化，此时通过resize()方法得到初始化的table n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)//1.1、此处通过(n - 1) & hash 计算出的值作为tab的下标i，并另p表示tab[i]，也就是该链表第一个节点的位置。并判断p是否为null tab[i] = newNode(hash, key, value, null);//1.1.1、当p为null时，表明tab[i]上没有任何元素，那么接下来就new第一个Node节点，调用newNode方法返回新节点赋值给tab[i] else {//2.1下面进入p不为null的情况，有三种情况：p为链表节点；p为红黑树节点；p是链表节点但长度为临界长度TREEIFY_THRESHOLD，再插入任何元素就要变成红黑树了。 Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//2.1.1HashMap中判断key相同的条件是key的hash相同，并且符合equals方法。这里判断了p.key是否和插入的key相等，如果相等，则将p的引用赋给e e = p; else if (p instanceof TreeNode)//2.1.2现在开始了第一种情况，p是红黑树节点，那么肯定插入后仍然是红黑树节点，所以我们直接强制转型p后调用TreeNode.putTreeVal方法，返回的引用赋给e e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else {//2.1.3接下里就是p为链表节点的情形，也就是上述说的另外两类情况：插入后还是链表/插入后转红黑树。另外，上行转型代码也说明了TreeNode是Node的一个子类 for (int binCount = 0; ; ++binCount) {//我们需要一个计数器来计算当前链表的元素个数，并遍历链表，binCount就是这个计数器 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // 插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加1，而binCount并不包含新节点，所以判断时要将临界阈值减1 treeifyBin(tab, hash);//当新长度满足转换条件时，调用treeifyBin方法，将该链表转换为红黑树 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; }
HashMap获取元素
当hashmap中只存在数组，而数组中没有Node链表时，是HashMap查询数据性能最好的时候，一旦发生大量冲突，就会产生链表，导致要遍历Node节点，从而降低查询数据的性能， 红黑树就是为了解决这个性能问题而引进的，使得查询的平均复杂度减低到了O(log(n)),链表越长，使用红黑树后查询效率提升越明显.
HashMap扩容
在1.7jdk中，HashMap整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表的元素，然后遍历以该元素为头的链表元素，一次遍历元素的hash值，计算在新数组中的下标，进行交换，这样扩容方式将原来哈希冲突的单项链表尾部变成了扩容后的头部。
扩容前
扩容后
而在 JDK 1.8 中，HashMap 对扩容操作做了优化。
HashMap初始化长度是16,扩容之后就是32，而length-1对应就是15和31,而计算存储位置的公式如下.
(n-1)&hash
15：0000 0000 0000 0000 0000 0000 0000 1111 (15的二进制)31：0000 0000 0000 0000 0000 0000 0001 1111(31的二进制)
我们假设某个元素的的hashcode是52
52：0000 0000 0000 0000 0000 0000 0011 0100 (52的二进制)
(16-1)&52运算结果是4
4：0000 0000 0000 0000 0000 0000 0000 0100
(32-1)&52运算结果是20
20：0000 0000 0000 0000 0000 0000 0001 0100
我发现这个20=4+16，正好就是原位置+原数组的长度,我们在举个例子如下
某个元素的hashcode=100
100：0000 0000 0000 0000 0000 0000 0110 0100(100的二进制)
而(16-1)&100和(32-1)&100的计算结果都是4
4：0000 0000 0000 0000 0000 0000 0000 0100(4的二进制)
发现扩容之后存储位置没有发生变化。 因此证明，扩容之后，元素要么在原位置,要么在原位置加原位置的长度
可以看到，扩容之后元素的位置是否改变，完全取决于紫色框中的运算结果是0还是1,如果是0则新位置和原位置相同，如果是1,新位置=原位置+原数组长度,说明在jdk1.8中扩容并不用重新计算hash值。
为什么初始容量，一般都是2的整数次幂
- 使用2的整数次幂时候,使用(n-1)&hash计算和hash%n的计算结果一样,而&的运算速度比取模块.且可以保证不超过数组长度
- n是2的次幂，则n-1转化为二进制必定是11111...的形式，在和元素的hash值与操作速度快，而且不浪费空间，比如如果长度是15，而n-1=14,而14的二进制是1110.在和元素的hash与操作之后，最后一位总是0，而某些位置永远不会存储元素，浪费空间
如果对您有一丝丝帮助，麻烦点个关注，也欢迎转发，谢谢
扫码关注