声明：本文使用JDK1.8
HashMap 是我们平时开发过程中使用最多的 Java 集合框架之一，它继承 AbstractMap，实现 Map 接口，是一种 key-value，并允许使用空值和空键。
public class HashMap<K，V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
从结构实现来讲，HashMap 是 数组+链表+红黑树 （JDK1.8增加了红黑树部分）实现的，相比于Java7，Node可以被扩展成TreeNode。
HashMap类加载
//初始容量为16的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量(1073741824)
static final int MAXIMUM_CAPACITY = 1 << 30;
//哈希表在其容量自动增加之前可以达到多满的一种尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表中数据的临界值，如果达到8，就进行resize扩展，如果数组大于64则转换为树.
static final int TREEIFY_THRESHOLD = 8;
//如果链表的数据小于6，则从树转换为链表.
static final int UNTREEIFY_THRESHOLD = 6;
//如果数组的size大于64，则把链表进行转化为树
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
//通过key计算hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对于HashMap初始化的容量是16的原因，可以看这里：漫画：什么是HashMap？,
感觉讲的还是挺详细的。之所以选择 16 这个数字，是服务于从 key 映射到 index 的算法。index = HashCode(Key) & (length - 1)， 如果 length 是2的幂的话，则 length - 1 就是全是 1的二进制数，比如 16 - 1 = 1111，这样相当于是坐落在长度为 length 的 hashMap 上的位置只和 HashCode 的后四位有关，这只要给出的 HashCode 算法本身分布均匀，算出的index就是分布均匀的。
可以了解下 漫画：高并发下的HashMap，不过这里的代码比较老。HashMap 在高并发下出现死锁，主要发生在 rehash 时，链表出现环链了。不过在Java8 中，对于链表超过8时，转化为红黑树，这有效的防止这个问题。
tableSizeFor
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;
}
这个方法被调用的地方：
public HashMap(int initialCapacity, float loadFactor) {
/**省略此处代码...**/
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
当实例化 HashMap 实例时，如果给定了 初始容量initialCapacity，由于 HashMap 的 capacity 都是 2 的幂，因此这个方法用于找到大于等于 initialCapacity 的最小的2的幂。
Node
Java8中相对之前的版本增加了Node，从代码中可以看出，是一个哈希桶数组，实现Map.Entry接口，是一个键值对。
key 和 index
在 HashMap 中，下标的选择是计算key的hash值，具体公式是：(n - 1 ) & hash 。其中 n 是 hashmap table[] 数组的长度，hash 是当前key的hash值。& 是与运算，两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。详细的可以看之前的那篇链接。
hasCode 和 equals
HashMap 重写了 hasCode 和 equals，源码如下：
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCod(value);
}
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;
}
hash
HashMap 的 hash 计算方法。key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。h>>>16 无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。异或位运算(0 ^ 1 得 1、1 ^ 1 得 0、0 ^ 0 得 0、1 ^ 0 得 1)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
初始化
HashMap提供三种初始化HashMap：
//默认初始化16，加载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//给定容量，加载因子0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用与指定的Map相同的映射构造一个新的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
get相关
get方法
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//(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 {//遍历链表，得到节点值，通过hash和equals(key)确认所查找元素。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
contains
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
put
put函数是想HashMap中添加键值。
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空||length为0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;// 分配空间，初始化
//hash所在位置(第i个桶)为null，直接put
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//tab[i]有元素，则需要遍历结点后再添加
Node<K,V> e; K k;
// hash、key均等，说明待插入元素和第一个元素相等，直接更新
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//红黑树冲突插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 链表
for (int binCount = 0; ; ++binCount) {//死循环，直到break
if ((e = p.next) == null) {//表尾仍没有key相同节点,新建节点
p.next = newNode(hash, key, value, null);
//若链表数量大于阀值8【9个】，则调用treeifyBin方法，仅当tab.length大于64才将链表改为红黑树
// 如果tab.length<64或table=null，则重构一下链表
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);//binCount>=9则链表转树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;// hash、key均相等，说明此时的节点==待插入节点，更新
p = e;//更新p指向下一个节点
}
}
//当前节点e = p.next不为null，即链表中原本存在了相同key，则返回oldValue
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent值为false，参数主要决定当该键已经存在时，是否执行替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//调用linkedHashMap,move node to last
return oldValue;
}
}
++modCount;
if (++size > threshold)//++size后再检测是否到了阀值
resize();
afterNodeInsertion(evict);//调用linkedHashMap,true则possibly remove eldest
return null;// 原hashMap中不存在相同key的键值对，则在插入键值对后，返回null。
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//当tab长度小于64的时候，只是扩容，而不是转化成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
扩容
先了解一些字段含义：
// HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
int threshold;
// 加载因子实际大小
final float loadFactor;
int size; //实际存在的键值对数量
transient volatile int modCount; // HashMap被改变的次数
看下源码里面扩容的代码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //赋值老的Node
int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的Node的大小
int oldThr = threshold; //旧阀值
int newCap, newThr = 0; // 新容量，新阀值
if (oldCap > 0) {
//扩容前的数组大小如果已经达到最大(2^30)了
if (oldCap >= MAXIMUM_CAPACITY) {
///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
//大于初始容量，旧容量2倍小于最大容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; //2倍
}// oldCap=0 ,oldThr>0，threshold(新的扩容resize临界值)
else if (oldThr > 0)
newCap = oldThr;//新容量=旧阀值（扩容临界值）
else { // oldCap=0 ,oldThr=0，调用默认值来初始化
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16
}
if (newThr == 0) {//新阀值为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;
// table初始化,bucket copy到新bucket，分链表和红黑树
if (oldTab != null) { // 不为空则挨个copy，影响效率！！
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//先赋值再判断
oldTab[j] = null;//置null，主动GC
if (e.next == null)
//1.6 的indexFor，计算key；tableSizeFor性能优化
newTab[e.hash & (newCap - 1)] = e;//hash&(length-1)
else if (e instanceof TreeNode) // 红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //链表，preserve order保持顺序
//一个桶中有多个元素，遍历将它们移到新的bucket或原bucket
Node<K,V> loHead = null, loTail = null;//lo原bucket的链表指针
Node<K,V> hiHead = null, hiTail = null;//hi新bucket的链表指针
Node<K,V> next;
do {
next = e.next;
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) {//原bucket位置的尾指针不为空(即还有node)
loTail.next = null;//链表最后得有个null
newTab[j] = loHead;//链表头指针放在新桶的相同下标(j)处
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
put(K key, V value)的逻辑：
①.判断键值对数组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的话，同时需要判断 table 数组大小是否大于64，如果只满足前一个条件，只进行扩容；若果两个条件都满足，把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
JDK7和JDK8之后，HashMap 的区别？
- 1.7中采用数组+链表，1.8采用的是数组+链表/红黑树，即在1.7中链表长度超过一定长度后就改成红黑树存储。
- 1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
- 1.7是采用表头插入法插入链表，1.8采用的是尾部插入法。
在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。