一、HashMap概述
在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
下图中代表jdk1.8之前的hashmap结构，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。=
jdk1.8之前的hashmap都采用上图的结构，都是基于一个数组和多个单链表，hash值冲突的时候，就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时，将会花费O（n）的查找时间，会有很大的性能损失。到了jdk1.8，当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树，如下图所示。
HashMap Jdk1.8源码分析
1、链表的实现
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。来看具体代码：
//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
final int hash;
final K key;
V value;
Node<k,v> next;
//构造函数Hash值 键 值 下一个节点
Node(int hash, K key, V value, Node<k,v> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + = + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
可以看到，node中包含一个next变量，这个就是链表的关键点，hash结果相同的元素就是通过这个next进行关联的。
2、红黑树
//红黑树
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
TreeNode<k,v> parent; // 父节点
TreeNode<k,v> left; //左子树
TreeNode<k,v> right;//右子树
TreeNode<k,v> prev; // needed to unlink next upon deletion
boolean red; //颜色属性
TreeNode(int hash, K key, V val, Node<k,v> next) {
super(hash, key, val, next);
}
//返回当前节点的根节点
final TreeNode<k,v> root() {
for (TreeNode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
红黑树比链表多了四个变量，parent父节点、left左节点、right右节点、prev上一个同级节点.红黑树详情请点击链接
3、位桶
HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。
有了以上3个数据结构，只要有一点数据结构基础的人，都可以大致联想到HashMap的实现了。首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
HashMap的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
HashMap的实例有两个参数影响其性能。
初始容量：哈希表中桶的数量
加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度
当哈希表中条目数超出了当前容量*加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。
Java中默认初始容量为16，加载因子为0.75。
1）loadFactor加载因子
定义：loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。
loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，
那么数组中存放的数据也就越稀，也就是可能数组中每个位置上就放一个元素。那有人说，就把loadFactor变为1最好吗，存的数据很多，但是这样会有一个问题，就是我们在通过key拿到我们的value时，
是先通过key的hashcode值，找到对应数组中的位置，如果该位置中有很多元素，则需要通过equals来依次比较链表中的元素，拿到我们的value值，这样花费的性能就很高，
如果能让数组上的每个位置尽量只有一个元素最好，我们就能直接得到value值了，所以有人又会说，那把loadFactor变得很小不就好了，但是如果变得太小，在数组中的位置就会太稀，也就是分散的太开，
浪费很多空间，这样也不好，所以在hashMap中loadFactor的初始值就是0.75，一般情况下不需要更改它。
2）桶
根据前面画的HashMap存储的数据结构图，你这样想，数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素(entry)，这就是桶的意思。也就相当于把元素都放在桶中。
3）capacity
capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。
一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
4）size的含义
size就是在该HashMap的实例中实际存储的元素的个数
5）threshold的作用
threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。
注意这里说的是考虑，因为实际上要扩增数组，除了这个size>=threshold条件外，还需要另外一个条件。
什么时候会扩增数组的大小？在put一个元素时先size>=threshold并且还要在对应数组位置上有元素，这才能扩增数组。
HashMap的构造方法
有四个构造方法，构造方法的作用就是记录一下16这个数给threshold（这个数值最终会当作第一次数组的长度。）和初始化加载因子。注意，hashMap中table数组一开始就已经是个没有长度的数组了。
构造方法中，并没有初始化数组的大小，数组在一开始就已经被创建了，构造方法只做两件事情，一个是初始化加载因子，另一个是用threshold记录下数组初始化的大小。注意是记录。
1）HashMap()
//看上面的注释就已经知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75
//初始化容量：也就是初始化数组的大小
//加载因子：数组上的存放数据疏密程度。
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
2）HashMap(int)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3）HashMap(int,float)
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于0，不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
4）HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将m中的所有元素添加至HashMap中
putMapEntries(m, false);
}
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函数将m的所有元素存入本HashMap实例中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
// 未初始化，s为m的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
resize方法
final Node<K,V>[] resize() {
//旧数组
Node<K,V>[] oldTab = table;
//旧数组的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。
int oldThr = threshold;
//初始化新数组的容量和阈值，分三种情况讨论。
int newCap, newThr = 0;
//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。
//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。
//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。
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
}
//2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况
//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。
//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。
//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)
//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，
//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，
//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。这是为了延迟加载，提高效率。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中
//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。
if (oldTab != null) {
//遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//1.如果当前元素的下一个元素为空，则说明此处只有一个元素
//则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并
//判断当前位置的链表是否需要移动到新的位置
else { // preserve order
// loHead 和 loTail 分别代表链表旧位置的头尾节点
Node<K,V> loHead = null, loTail = null;
// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//如果当前元素的hash值和oldCap做与运算为0，则原位置不变
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;
}
上边还有一个非常重要的运算，我们没有讲解。就是下边这个判断，它用于把原来的普通链表拆分为两条链表，位置不变或者放在新的位置。
我们以原数组容量16为例，扩容之后容量为32。说明下为什么这样计算。
还是用之前的hash值举例。
//e.hash值
0110 1101 0110 1111 0110 1110 0010 1000
//oldCap值，即16
0000 0000 0000 0000 0000 0000 0001 0000
//做与运算，我们会发现结果不是0就是非0，
//而且它取决于 e.hash 二进制位的倒数第五位是 0 还是 1，
//若倒数第五位为0，则结果为0，若倒数第五位为1，则结果为非0。
//那这个和新数组有什么关系呢？
//别着急，我们看下新数组的容量是32，如果求当前hash值在新数组中的下标，则为
// e.hash &( 32 - 1) 这样的运算 ，即 hash 与 31 进行与运算，
0110 1101 0110 1111 0110 1110 0010 1000
&
0000 0000 0000 0000 0000 0000 0001 1111
=
0000 0000 0000 0000 0000 0000 0000 1000
//接下来，我们对比原来的下标计算结果和新的下标结果，看图
看下面的图，我们观察，hash值和旧数组进行与运算的结果 ，跟新数组的与运算结果有什么不同。
会发现一个规律：
若hash值的倒数第五位是0，则新下标与旧下标结果相同，都为 0000 1000
若hash值的倒数第五位是1，则新下标（0001 1000）与旧下标（0000 1000）结果值相差了 16 。
因此，我们就可以根据 （e.hash & oldCap == 0）
这个判断的真假来决定，当前元素应该在原来的位置不变，还是在新的位置(原位置 + 16)。
如果，上边的推理还是不明白的话，我再举个简单的例子。
18%16=2 18%32=18
34%16=2 34%32=2
50%16=2 50%32=18
怎么样，发现规律没，有没有那个感觉了？
计算中的18，34 ，50 其实就相当于 e.hash 值，和新旧数组做取模运算，得到的结果，要么就是原来的位置不变，要么就是原来的位置加上旧数组的长度
①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
②.每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
在resize前和resize后的元素布局如下:
hash算法
在JDK 1.8中，hash方法如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1）首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。
（2）在putVal源码中，我们通过(n-1)&hash获取该对象的键在hashmap中的位置。（其中hash的值就是（1）中获得的值）其中n表示的是hash桶数组的长度，并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算。
我们把高16位值和当前h的低16位进行了混合，这样可以尽量保留高16位的特征，从而降低哈希碰撞的概率。
思考一下，为什么这样做，就可以降低哈希碰撞的概率呢？先别着急，我们需要结合 i = (n - 1) & hash 这一段运算来理解。
//②
//这是 put 方法中用来根据hash()值寻找在数组中的下标的逻辑，
//n为数组长度， hash为调用 hash()方法混合处理之后的hash值。
i = (n - 1) & hash
我们知道，如果给定某个数值，去找它在某个数组中的下标位置时，直接用模运算就可以了（假设数组值从0开始递增）。如，我找 14 在数组长度为16的数组中的下标，即为 14 % 16，等于14 。 18的位置即为 18%16，等于2。
而②中，就是取模运算的位运算形式。以18%16为例
//18的二进制
0001 0010
//16 -1 即 15的二进制
0000 1111
//与运算之后的结果为
0000 0010
// 可以看到，上边的结果转化为十进制就是 2 。
//其实我们会发现一个规律，因为n是2的n次幂，因此它的二进制表现形式肯定是类似于
0001 0000
//这样的形式，只有一个位是1，其他位都是0。而它减 1 之后的形式就是类似于
0000 1111
//这样的形式，高位都是0，低位都是1，因此它和任意值进行与运算，结果值肯定在这个区间内
0000 0000 ~ 0000 1111
//也就是0到15之间，（以n为16为例）
//因此，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。
为什么高低位异或运算可以减少哈希碰撞
我们想象一下，假如用 key 原来的hashCode值，直接和 (n-1) 进行与运算来求数组下标，而不进行高低位混合运算，会产生什么样的结果。
//例如我有另外一个h2，和原来的 h相比较，高16位有很大的不同，但是低16位相似度很高，甚至相同的话。
//原h值
0110 1101 0110 1111 0110 1110 0010 1000
//另外一个h2值
0100 0101 1110 1011 0110 0110 0010 1000
// n -1 ,即 15 的二进制
0000 0000 0000 0000 0000 0000 0000 1111
//可以发现 h2 和 h 的高位不相同，但是低位相似度非常高。
//他们分别和 n -1 进行与运算时，得到的结果却是相同的。（此处n假设为16）
//因为 n-1 的高16位都是0，不管 h 的高 16 位是什么，与运算之后，都不影响最终结果，高位一定全是 0
//因此，哈希碰撞的概率就大大增加了，并且 h 的高16 位特征全都丢失了。
可以看到两个值进行与运算，结果会趋向于0；或运算，结果会趋向于1；而只有异或运算，0和1的比例可以达到1:1的平衡状态。
所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，哈希碰撞的概率当然就更小了。
以上，就是为什么要对一个hash值进行高低位混合，并且选择异或运算来混合的原因。
put方法
1）put(K key,V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// hash值不相等，即key不相等；为红黑树结点
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);
// 结点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) {
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
get()方法
public V get(Object key) {
Node<K,V> e;
//如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。
//因此，我们就明白了，为什么hashMap支持Key和value都为null
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;
//首先要确保数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//若hash值和key都相等，则说明我们要找的就是第一个元素，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不是的话，就遍历当前链表（或红黑树）
if ((e = first.next) != null) {
//如果是红黑树结构，则找到当前key所在的节点位置
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);
}
}
//否则，说明没有找到，返回null
return null;
}
jdk1.7
1、存储结构
HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。 Entry是HashMap中的一个静态内部类。代码如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
经过以上分析，HashMap的存储结构图如下：
2、构造方法
先看HashMap中的几个重要属性：
//默认初始化化容量,即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态
static final Entry<?,?>[] EMPTY_TABLE = {};
//空的存储实体
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;
//默认的threshold值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//计算Hash值时的key
transient int hashSeed = 0;
//通过初始容量和状态因子构造HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//参数有效性检查
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//参数有效性检查
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//参数有效性检查
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
//通过扩容因子构造HashMap,容量去默认值，即16
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//装载因子取0.75，容量取16，构造HashMap
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//通过其他Map来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);//初始化HashMap底层的数组结构
putAllForCreate(m);//添加m中的元素
}
putAllForCreate(m)
// 根据Map创建所有对应的桶
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext();) {
Map.Entry<? extends K, ? extends V> e = i.next();
putForCreate(e.getKey(), e.getValue());
}
}
3.put操作
如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？为了解决这个问题，HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);//分配数组空间
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
inflateTable的源码如下：
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
table = new Entry[capacity];//分配空间
initHashSeedAsNeeded(capacity);//选择合适的Hash因子
}
inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16；to_size=16，capacity=16；to_size=17,capacity=32。其实现如下：
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值。
在对数组进行空间分配后，会根据hash函数计算散列值，其实现如下：
//用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {//这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
从上面的操作看以看出，影响HashMap元素的存储位置的只有key的值，与value值无关。
通过hash函数得到散列值后，再通过indexFor进一步处理来获取实际的存储位置，其实现如下：
//返回数组下标
static int indexFor(int h, int length) {
return h & (length-1);
}
h&（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为
最终计算出的index=2。有些版本的对于此处的计算会使用 取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些（HashMap中有大量位运算）。
通过以上分析，我们看到，要得到一个元素的存储位置，需要如下几步：
1、获取该元素的key值
2、通过hash方法得到key的散列值，这其中需要用到key的hashcode值。
3、通过indexFor计算得到存储的下标位置。
最后，得到存储的下标位置后，我们就可以将元素放入HashMap中，具体通过addEntry实现：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);//扩容后重新计算插入的位置下标
}
//把元素放入HashMap的桶的对应位置
createEntry(hash, key, value, bucketIndex);
}
//创建元素
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; //获取待插入位置元素
table[bucketIndex] = new Entry<>(hash, key, value, e);//这里执行链接操作，使得新插入的元素指向原有元素。
//这保证了新插入的元素总是在链表的头
size++;//元素个数+1
}
通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
4、扩容操作
扩容操作通过resize操作实现：
//按新的容量扩容Hash表
void resize(int newCapacity) {
Entry[] oldTable = table;//老的数据
int oldCapacity = oldTable.length;//获取老的容量值
if (oldCapacity == MAXIMUM_CAPACITY) {//老的容量值已经到了最大容量值
threshold = Integer.MAX_VALUE;//修改扩容阀值
return;
}
//新的结构
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));//将老的表中的数据拷贝到新的结构中
table = newTable;//修改HashMap的底层数组
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阀值
}
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法：
//将老的表中的数据拷贝到新的结构中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//容量
for (Entry<K,V> e : table) { //遍历所有桶
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
if (rehash) {//如果是重新Hash，则需要重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//定位Hash桶
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
}
这个方法将老数组中的数据逐个链表地遍历，重新计算后放入新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
注意：HashMap数组元素长度的设计
通过源码可以发现，hashMap的数组长度一定保持2的次幂，这样做有什么好处
//根据Hash值和Hash表的大小选择合适的Hash桶
static int indexFor(int h, int length) {
return h & (length-1);
}
如果length为2的次幂，其二进制表示就是100….0000；则length-1 转化为二进制必定是0111….11的形式，在于h的二进制与操作效率会非常的快，而且空间不浪费；如果length不是2的次幂，比如length为15，则length-1为14，对应的二进制为1110，再于h与操作，
最后一位都为0，所以0001，0011，0101，1001，1011，0111，1101这几个位置永远都不会存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。
5、get操作
//获取key值为key的元素值
public V get(Object key) {
if (key == null)//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑
return getForNullKey();
Entry<K,V> entry = getEntry(key);//获取实体
return null == entry ? null : entry.getValue();//判断是否为空，不为空，则获取对应的值
}
//获取key为null的实体
private V getForNullKey() {
if (size == 0) {//如果元素个数为0，则直接返回null
return null;
}
//key为null的元素存储在table的第0个位置
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)//判断是否为null
return e.value;//返回其值
}
return null;
}
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法：
//获取键值为key的元素
final Entry<K,V> getEntry(Object key) {
if (size == 0) {//元素个数为0
return null;//直接返回null
}
int hash = (key == null) ? 0 : hash(key);//获取key的Hash值
for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度，定位到Hash桶
e != null;
e = e.next) {//进行遍历
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key，合适则返回值
return e;
}
return null;
}
为什么HashMap链表会形成死循环
准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能，因为JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.8做了改进，用的是尾插法，不会产生死循环。
我们从 put()方法开始，最终找到线程不安全的那个方法。这里省略中间不重要的过程，我只把方法的跳转流程贴出来：
//添加元素方法 -> 添加新节点方法 -> 扩容方法 -> 把原数组元素重新分配到新数组中
put() --> addEntry() --> resize() --> transfer()
问题就发生在 transfer 这个方法中。
我们假设，原数组容量只有2，其中一条链表上有两个元素 A,B，如下图
现在，有两个线程都执行 transfer 方法。每个线程都会在它们自己的工作内存生成一个newTable 的数组，用于存储变化后的链表，它们互不影响（这里互不影响，指的是两个新数组本身互不影响）。但是，需要注意的是，它们操作的数据却是同一份。
因为，真正的数组中的内容在堆中存储，它们指向的是同一份数据内容。就相当于，有两个不同的引用 X，Y，但是它们都指向同一个对象 Z。这里 X、Y就是两个线程不同的新数组，Z就是堆中的A，B 等元素对象。
假设线程一执行到了上图1中所指的代码①处，恰好 CPU 时间片到了，线程被挂起，不能继续执行了。 记住此时，线程一中记录的 e = A ， e.next = B。
然后线程二正常执行，扩容后的数组长度为 4， 假设 A，B两个元素又碰撞到了同一个桶中。然后，通过几次 while 循环后，采用头插法，最终呈现的结构如下：
此时，线程一解挂，继续往下执行。注意，此时线程一，记录的还是 e = A，e.next = B，因为它还未感知到最新的变化。
我们主要关注图1中标注的①②③④处的变量变化：
/**
* next = e.next
* e.next = newTable[i]
* newTable[i] = e;
* e = next;
*/
//第一次循环,(伪代码)
e=A;next=B;
e.next=null //此时线程一的新数组刚初始化完成，还没有元素
newTab[i] = A->null //把A节点头插到新数组中
e=B; //下次循环的e值
第一次循环结束后，线程一新数组的结构如下图：
然后，由于 e=B，不为空，进入第二次循环。
//第二次循环
e=B;next=A; //此时A，B的内容已经被线程二修改为 B->A->null，然后被线程一读到，所以B的下一个节点指向A
e.next=A->null // A->null 为第一次循环后线程一新数组的结构
newTab[i] = B->A->null //新节点B插入之后，线程一新数组的结构
e=A; //下次循环的 e 值
第二次循环结束后，线程一新数组的结构如下图：
此时，由于 e=A，不为空，继续循环。
//第三次循环
e=A;next=null; // A节点后边已经没有节点了
e.next= B->A->null // B->A->null 为第二次循环后线程一新数组的结构
//我们把A插入后，抽象的表达为 A->B->A->null，但是，A只能是一个，不能分身啊
//因此实际上是 e(A).next指向发生了变化，A的 next 由指向 null 改为指向了 B，
//而 B 本身又指向A，因此A和B互相指向，成环
newTab[i] = A->B 且 B->A
e=next=null; //e此时为空，结束循环
第三次循环结束后，看下图，A的指向由 null ，改为指向为 B，因此 A 和 B 之间成环。
这时，有人可能就会问了，就算他们成环了，又怎样，跟死循环有什么关系？
我们看下 get() 方法（最终调用 getEntry 方法）
可以看到查找元素时，只要 e 不为空，就会一直循环查找下去。若有某个元素 C 的 hash 值也落在了和 A，B元素同一个桶中，则会由于， A，B互相指向，e.next 永远不为空，就会形成死循环。