在JDK1.8之前，HashMap使用数组+链表实现，即使用链表处理冲突，同一hash值的节点都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间
HashMap数据结构
下图代表jdk1.7的hashmap结构，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中
jdk1.8之前的hashmap都采用上图的结构，都是基于一个数组和多个单链表，hash值冲突的时候，就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时，将会花费O（n）的查找时间，会有很大的性能损失。到了jdk1.8，当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树，如下图所示
链表
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; } }
红黑树
红黑树比链表多了四个变量，parent父节点、left左节点、right右节点、prev上一个同级节点，红黑树内容较多，不在赘述
//红黑树 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; } } }
位桶
HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组
transient Node<k,v>[] table;//存储（位桶）的数组
有了以上3个数据结构可以想到HashMap的实现了。首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率
HashMap常用方法
HashMap中包含如下的常用方法，在接下来使用过程中需要理解。
Map的创建：HashMap() 往Map中添加键值对：即put(Object key, Object value)方法 获取Map中的单个对象：即get(Object key)方法 删除Map中的对象：即remove(Object key)方法 判断对象是否存在于Map中：containsKey(Object key) 遍历Map中的对象：即keySet()，在实际中更常用的是增强型的for循环去做遍历 Map中对象的排序：主要取决于所采取的排序算法
HashMap类
包括类的基础关系，属性说明和构造方法
类的基础结构
可以看到HashMap继承自父类（AbstractMap），实现了Map、Cloneable、Serializable接口。其中，Map接口定义了一组通用的操作；Cloneable接口则表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；Serializable接口表示HashMap实现了序列化，即可以将HashMap对象保存至本地，之后可以恢复状态
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
类的属性说明
类中包含的属性的含义说明
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)上的结点数大于这个值时会转成红黑树;+对应的table的最小大小为64，即MIN_TREEIFY_CAPACITY ；这两个条件都满足，会链表会转红黑树 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(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; }
其他的构造方法，如：HashMap(int)，HashMap()，HashMap(Map<? extends K>)就不再赘述
Hash算法
我们知道在进行元素插入的时候需要通过hash计算确定它去到哪个桶里，那么就用到hash算法了。
算法源码
在JDK 1.8中，hash方法如下
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
- 首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。
- 在putVal源码中，我们通过(n-1)&hash获取该对象的键在hashmap中的位置。（其中hash的值就是（1）中获得的值）其中n表示的是hash桶数组的长度，并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算。
其中 n表示hash槽数组大小；i表示Node在数组中的索引值；上述关键代码： i = (n - 1) & hash
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... if ((p = tab[i = (n - 1) & hash]) == null)//获取位置 tab[i] = newNode(hash, key, value, null); ... }
tab即是table，n是map集合的容量大小，hash是上面方法的返回值。因为通常声明map集合时不会指定大小，或者初始化的时候就创建一个容量很大的map对象，所以这个通过容量大小与key值进行hash的算法在开始的时候只会对低位进行计算，虽然容量的2进制高位一开始都是0，但是key的2进制高位通常是有值的，因此先在hash方法中将key的hashCode右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。
异或运算表示相同为0，相异为1
0 ^ 1 得 1 1 ^ 1 得 0 0 ^ 0 得 0 1 ^ 0 得 1
扩容位置变化推演
下面我们推演一下，当扩容时，原Node节点在新老数组中的位置变化：
结论：扩容后，节点的位置有两种可能：还在原来的数组索引上；原索引+扩容的长度
HashMap 的容量为什么建议是 2的幂次方？
到这里，我们提了一个关键的问题： HashMap 的容量为什么建议是 2的幂次方？为什么要 2 的幂次方呢？hash 算法的目的是为了让hash值均匀的分布在桶中（数组），那么，如何做到呢？试想一下，如果不使用 2 的幂次方作为数组的长度会怎么样？
假设我们的数组长度是10，还是上面的公式： 1010 & 101010100101001001000 结果：1000 = 8 1010 & 101000101101001001001 结果：1000 = 8 1010 & 101010101101101001010 结果： 1010 = 10 1010 & 101100100111001101100 结果： 1000 = 8
这种散列结果，会导致这些不同的key值全部进入到相同的插槽中，形成链表，性能急剧下降。所以说，我们一定要保证 & 中的二进制位全为 1，才能最大限度的利用 hash 值，并更好的散列，只有全是1 ，才能有更多的散列结果。如果是 1010，有的散列结果是永远都不会出现的，比如 0111，0101，1111，1110…，只要 & 之前的数有 0， 对应的 1 肯定就不会出现（因为只有都是1才会为1）。大大限制了散列的范围
核心方法分析
主要包括Put操作，Get操作以及获取Size的操作。
Put操作
首先说明，HashMap并没有直接提供putVal接口给用户调用，而是提供的put方法，而put方法就是通过putVal来插入元素的
public V put(K key, V value) { // 对key的hashCode()做hash return putVal(hash(key), key, value, false, true); }
putVal方法执行过程可以通过下图来理解：
整体步骤如下：
- 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
- 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
- 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
- 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
- 遍历table[i]，判断链表长度是否大于8（且），大于8的话（且Node数组的数量大于64）把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
- 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
以上就是Put操作，操作过程相对繁琐，涉及到扩容机制。
Get操作
HashMap同样并没有直接提供getNode接口给用户调用，而是提供的get方法，而get方法就是通过getNode来取得元素的
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; // table已经初始化，长度大于0，根据hash寻找table中的项也不为空 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; }
扩容方法
在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容，每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//oldTab指向hash桶数组 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空 if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值 threshold = Integer.MAX_VALUE; return oldTab;//返回 }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold 双倍扩容阀值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); } 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];//新建hash桶数组 table = newTab;//将新数组的值复制给旧的hash桶数组 if (oldTab != null) {//进行扩容操作，复制Node对象值到新的hash桶数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给e oldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gc if (e.next == null)//如果e后面没有Node结点 newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得存储位置 else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中 ((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;//将Node结点的next赋值给next if ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0 if (loTail == null)//如果loTail为null loHead = e;//将e结点赋值给loHead else loTail.next = e;//否则将e赋值给loTail.next loTail = e;//然后将e复制给loTail } else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0 if (hiTail == null)//如果hiTail为null hiHead = e;//将e赋值给hiHead else hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next hiTail = e;//将e复制个hiTail } } while ((e = next) != null);//直到e为空 if (loTail != null) {//如果loTail不为空 loTail.next = null;//将loTail.next设置为空 newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处 } if (hiTail != null) {//如果hiTail不为空 hiTail.next = null;//将hiTail.next赋值为空 newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度] } } } } } return newTab; }
HashMap死循环
在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表，形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，在get操作时遍历链表就会产生死循环。那么这个死循环是如何生成的呢？
HashMap如果超过容量会进行rehash操作扩容，随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个同时触发了rehash操作，产生了闭合的回路
