hashMap是Map接口的一个实现类，主要用来存储（key,value）类型的数据，是平时用得比较多的数据结构。
本篇主要讨论一下hashMap底层代码的实现。
核心成员变量
//node表示存储数据的一个单链表，table是实际存储数据的数组，所以hashMap底层是基于数组+链表（树）的方式存储
transient Node<K,V>[] table;
//已经存储的元素的数量
transient int size;
//默认的容量大小，也就是table数组的默认大小，该值为2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//table数组容量的最大大小，该值为2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子，也就是每次table容量不够时扩容的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//数组转变为tree的阈值，当table下的链表长度大于等于8-1时，就将链表转换为tree
static final int TREEIFY_THRESHOLD = 8;
//table数组扩容的阈值，当添加的数据的数量大于该值时，需要对数组扩容
int threshold;
//实际的负载因子，当调用无参构造方法时，该值=DEFAULT_LOAD_FACTOR
final float loadFactor;
Node的实现
//链表结构的节点信息
static class Node<K,V> implements Map.Entry<K,V> {
//key对应的hash值
final int hash;
//传入的key值
final K key;
//传入的value值
V value;
//该节点的下一个节点
Node<K,V> next;
...
}
无参构造函数
public HashMap() {
//设置负载为默认的负载因子0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
put(K key, V value)方法实现
public V put(K key, V value) {
//首先调用hash(key)来获取key的hash值
//然后调用putVal往hashMap中添加数据
return putVal(hash(key), key, value, false, true);
}
//获取key的hash值
static final int hash(Object key) {
int h;
//当key== null时，hash值为0
//(h = key.hashCode()) ^ (h >>> 16) 这个操作获取的hash值是为了后面计算table的下标时减少碰撞
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//hash为key的hash值
//key为添加的Key
//value为添加的value
//onlyIfAbsent表示当Key相同时是否要覆盖旧的值，为false为要覆盖旧值
//evict在hashMap中没有使用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab指向当前hashMap中的table
//n为tab的长度
//i = (n - 1) & hash， 计算hash值在table中的索引下标是多少
//p为当前table中存放的Node，也就是 p = table[i]
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//如果当前table为空，则需要对table进行初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//如果当前table[i]中为null，则新建一个node节点并赋予table[i]
tab[i] = newNode(hash, key, value, null);
else {
//执行到这里，说明当前table[i]下已经存在节点node，p=table[i]
//e表示当前key已经在链表中已经存在的节点，后面要覆盖e的value
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果链表中的第一个节点的hash值与传入的hash值一致，Key值与传入的key值一致，则将p赋予e，表示链表中第一个节点就是key对应的节点
e = p;
else if (p instanceof TreeNode)
//如果p是TreeNode，那么就按照treeNode的方式添加数据
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//执行到这里，说明p为链表结构，那么循环链表中的数据，查找是否已经存在对应key的节点
//如果存在，那么已经存在的节点赋予e并退出循环
//如果不存在key对应的节点，那么创建新的节点，并添加到链表最后
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表的节点数量大于转换为tree的阈值（8-1），那么将链表转换为树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//如果链表中已经存在key对应的节点，那么将该该节点返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不等于null，说明已经存在key对应的节点，那么直接替换掉节点对应的value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//替换旧的值
e.value = value;
afterNodeAccess(e);
//将旧的值返回
return oldValue;
}
}
++modCount;
//size+1，如果已添加的数据大小大于设置的阈值，那么需要对执行resize()方法扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//该方法创建一个新的节点并返回
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
具体步骤：
- 当调用hashMap无参构造函数的时候，会设置hashMap的负载因子（loadFactor）为默认的0.75f;
- 当添加元素时，首先调用hash(key)函数，获取key的hash值；
- 接着调用putVal去添加值到hashMap中，首先判断table数组是否为空，如果为空，执行resize方法对table数组进行初始化；
- 然后，根据 i = (n - 1) & hash 计算出添加的key应该存放在table数组中那个位置；
- 如果table[i]对应存储的值为null，则调用newNode创建一个新的链表节点赋予table[i]该位置；
- 如果table[i]对应存储的节点不为空，则获取该节点，首先判断第一个节点的key是否与传入的key一致，如果一致，则覆盖该节点的value，并将oldValue返回；
- 如果链表第一个节点的key与传入的key信息不一致，则判断节点是否是树结构，如果是树结构，则调用putTreeVal按照树结构的方法设置（key,value）数据；
- 如果第一个节点是链表节点，则遍历链表中的节点，如果遍历到的节点的key信息与传入的key信息一致，则覆盖该节点的value数据，并返回旧的value数据；
- 如果没有遍历到链表结尾没发现有key值一致的节点，则调用newNode创建一个新节点，并设置链表的最末尾；
- 往链表中添加完节点后，会判断当前链表的长度是否大于等于7，如果大于等于7，则将链表转换为tree结构；
- 最后，如果hashMap中已经存在key对应的节点数据，则覆盖该节点的数据，并将该节点旧的值放回；如果添加的（key,value）在hashMap中原来没有存在，则添加成功后将size+1，然后返回null；
resize()方法实现
//该方法对table数组初始化或者进行扩容，如果原来的table中的有数据，那么会将数据移动到扩容后的table中
final Node<K,V>[] resize() {
//将当期table数组赋予一个局部变量
Node<K,V>[] oldTab = table;
//该变量表示旧的table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的table数组扩容的阈值
int oldThr = threshold;
//扩容后的table的大小与新的数组扩容阈值
int newCap, newThr = 0;
if (oldCap > 0) {
//执行到这里，说明table数组的已经初始化过了
if (oldCap >= MAXIMUM_CAPACITY) {
//如果旧table的容量大于最大阈值，那么将数组的扩容阈值设置为Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
//直接返回旧的table的大小，因为table的数组的大小已经达到最大值，所以不需要进行扩容
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//将旧容量扩容为原来的2倍，并将该值赋予newCap，并且旧的数组容量小于默认的table容量大小16
//那么就将旧的扩容阈值扩大为原来的2倍
newThr = oldThr << 1;
}
else if (oldThr > 0)
//如果旧的table扩容阈值大于0，那么就将新的table容量设置为跟就得扩容阈值一样大
//当调用HashMap(initialCapacity,loadFactor)构造函数时，会执行到这里
newCap = oldThr;
else {
//当调用HashMap无参构造函数，并且table还没有初始化时，会指定到这里
//将数组的容量设置为默认值16
//将数组的扩容阈值设置为0.75*16=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//如果table的扩容因子为0，那么将扩容因子设置为数组容量*负载因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//根据计算出来的新数组容量，创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将table指向新创建的数组
table = newTab;
//如果旧的table数组中存在数据，那么需要将数据移动到新创建的数组中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//将oldTable[j]下的节点赋予局部变量e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//如果e链表中只有一个节点，那么根据e.hash & (newCap - 1)计算出该节点对应的table下标，并将该节点放置到table中
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果table下的节点树节点，则按照tree的方式移动数据
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//下面这段代码，将旧数组下的链表中的数据移动到新的数组中
//循环遍历链表中的节点，取出每个节点的hash值
//将hash值与旧的数组大小进行与（&）操作，如果得到的值为0，
//那么该节点在新数组中的下标索引与旧数组中的下标索引一致
//如果得到的值不为0，那么该节点在新数组中的下标索引=该节点在旧数组中的下标索引+旧数组的容量
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
//loHead与loTail存储的是索引下标不变的链表结构的链表头与链表尾
//hiHead与hiTail存储的是索引下标需要改变的链表结构的链表头与链表尾
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) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的数组
return newTab;
}
说明：
- 对数组进行初始化，将数组的默认大小设置为DEFAULT_INITIAL_CAPACITY=16，将数组的扩容阈值设置为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY=0.75 * 16=12；
- 如果table的大小大于默认大小16，则将table大小扩容为16 * 2，数组的扩容阈值扩大为12 * 2；
- 如果调用HashMap构造函数，并传入初始化table的大小，那么数组的大小与数组的扩容阈值一致；
- 如果旧数组中存在数据，那么需要将数据移动到新数组中，移动规则是：
循环遍历链表中的节点，取出每个节点的hash值，
将hash值与旧的数组大小进行与（&）操作，如果得到的值为0，
那么该节点在新数组中的下标索引与旧数组中的下标索引一致，
如果得到的值不为0，那么该节点在新数组中的下标索引=该节点在旧数组中的下标索引+旧数组的容量；
get(Object key)方法实现
//根据key获取value
public V get(Object key) {
Node<K,V> e;
//首先根据hash(key)返回获取key的hash值
//然后调用getNode方法获取对应的节点
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//根据hash值与key获取节点
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//将table赋予tab局部变量，并且table数组不为空
//根据 (n - 1) & hash 计算出hash值对应table的索引下标
//取出table指定下标的第一个节点信息赋予first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//校验第一个节点的hash与key是否与要查询的信息一致
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
//返回第一个节点
return first;
//first的下一个节点不为null
if ((e = first.next) != null) {
//判断该first是否为tree结构，如果为tree结构，则按照tree的形式获取节点信息返回
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//遍历链表节点数据，判断节点的key与hash是否与传入的key与hash一致
//如果一致，说明找到该节点，那么直接返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//找不到返回null
return null;
}
具体步骤：
- 根据传入的key调用hash函数获取到key对应的hash值；
- 根据key的hash值，根据表达式(n - 1) & hash计算出该hash值在table中对应的索引下标；
- 获取table对应的索引下标节点，首先判断第一个节点的key与hash跟传入的key与hash是否一致；
- 如果匹配，则直接返回第一个节点，如果不匹配，则判断该节点是否为tree结构的数据；
- 如果是tree结构，则按照tree结构的方式查找到key对应的节点，如果是链表结构，则遍历链表去查找key对应的节点；
- 如果找到对应的节点，则返回该节点；如果没有找到，则返回null；
entrySet()方法实现
//改方法返回了EntrySet对象
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//如果entrySet为空，则创建EntrySet方法并返回
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
//该内部类继承自AbstractSet，该类实现了Set接口，因此EntrySet也是set的一个实现类
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
....
//主要看一下forEach的实现，该方法传入一个函数式接口，也就是要回调的自定义函数
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
//如果回调函数为null，报空指针异常
if (action == null)
throw new NullPointerException();
//如果当前table不为空，则遍历table数组中的元素
if (size > 0 && (tab = table) != null) {
//将modCount赋予mc，后面判断如果在遍历之后，两个值不相等，则报错
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
//遍历每一个元素，并回调传入的已定义函数
action.accept(e);
}
//如果modCount 与 mc不相等，则报ConcurrentModificationException，表示在遍历数组的时候，不允许对数组进行修改操作
//在putVal，clear等修改操作的时候会对modCount执行加1的操作
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
....
}
说明：
- entrySet()返回一个Set接口的实现类EntrySet，该实现类是基于HashSet中的元素实现的；
- 当对EntrySet中的元素进行遍历时，会在遍历之前，将modCount赋予一个临时遍历mc，遍历完后，在对最新的modCount与mc进行比较；
- 这里的遍历方式是直接遍历table数组中的每一个元素；
- 如果最新的modCount与mc不相等，则报ConcurrentModificationException异常，表示不允许在遍历数据期间，对HashMap中的数据进行修改操作，当执行putValu,clear,remove等修改数据操作的时候，会对modCount执行加1的操作。
jdk1.8中调用foreach例子
HashMap<String, String> hashMap = new HashMap<String, String>();
hashMap.forEach((key, value) -> {
System.out.println(key + " " + value);
});
