按照从构造方法->常用API（增、删、改、查）的顺序来阅读源码，并做简要分析。
一. 概要
- 概括的说
HashMap 是一个关联数组、哈希表，它是线程不安全的，允许key为null,value为null。遍历时无序。 - 底层
其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表中的每个元素。 (因其底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。)
在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率，它实现了Map<K,V>, Cloneable, Serializable接口。 - 遍历
迭代器遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后，依次遍历的。属于无序集合。
二. 定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- 实现了Cloneable接口
即覆盖了函数clone()，能被克隆 - 实现java.io.Serializable接口
支持序列化，能通过序列化去传输
三. 介绍
结构实现
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率
HashMap
HashMap
3 .属性
初始容量--DEFAULT_INITIAL_CAPACITY
初始容量，必须是2的倍数，默认是16 (1 << 4)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
最大容量--MAXIMUM_CAPACITY
最大所能容纳的key-value 个数，最大值是 10 7374 1824(1 << 30)
static final int MAXIMUM_CAPACITY = 1 << 30;
默认的加载因子 -- DEFAULT_LOAD_FACTOR
默认的加载因子0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表转成红黑树的阈值--TREEIFY_THRESHOLD
树化链表节点的阈值，当某个链表的长度大于或者等于这个长度，则扩大数组容量，或者数化链表
static final int TREEIFY_THRESHOLD = 8;
红黑树转为链表的阈值--UNTREEIFY_THRESHOLD
static final int UNTREEIFY_THRESHOLD = 6;
Node<K,V>
- Node<K,V> 类是HashMap中的静态内部类，实现Map.Entry<K,V>接口。 定义了key键、value值、next节点，也就是说元素之间构成了单向链表
- 每一个节点的
hashCode()，是将key的hashCode 和value的hashCode 亦或得到的
Objects.hashCode(key) ^ Objects.hashCode(value);
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;
V value;
Node<K,V> next;
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; }
//每一个节点的hash值，是将key的hashCode 和 value的hashCode 异或得到的
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置新的value 同时返回旧value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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<K,V>[] table
哈希桶，存放链表。 长度是2的N次方，或者初始化时为0.
transient Node<K,V>[] table;
至此，HashMap存储的数据结构也就很清晰了：维护了一个数组，每个数组又维护了一个单向链表。之所以这么设计，考虑到遇到哈希冲突的时候，同index的value值就用单向链表来维护。
size
map中保存的键值对的数量
transient int size;
threshold
The next size value at which to resize (capacity * load factor).
- 容量*装载因子
threshold = CAPACITY * loadFactor
- threshold是HashMap判断size是否需要扩容的阈值：如果key-value的数量等于该值，则调用resize方法，扩大容量（2倍），同时修改threshold的值
int threshold;
loadFactor
装载因子
final float loadFactor;
4. 构造函数
HashMap一共有4个构造方法，主要的工作就是完成容量和加载因子的赋值。Hash表都是采用的懒加载方式，当第一次插入数据时才会创建。
1)无参构造函数--HashMap()
Constructs an empty {@code HashMap} with the default initial capacity
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2)指定初始化容量的构造函数--HashMap(int initialCapacity)
Constructs an empty {@code HashMap} with the specified initial capacity and the default load factor (0.75).
并不是指定的初始容量是多少，初始化之后的HashMap的容量就是多大，tableSizeFor（）方法会把初始化的容量变成是2的次方数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3)指定初始化容量 以及 加载因子--HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
//边界处理
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量最大不能超过2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子不能为负数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置阈值 1.>= 初始化容量 2. 是2的n次方
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor(int cap)
- 根据期望容量cap，返回**2的n次方形式的 **哈希桶的实际容量 length
- 返回值一般会大于等于cap
static final int tableSizeFor(int cap) {
//经过下面的 或 和位移 运算， n最终各位都是1。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判断n是否越界，返回 2的n次方作为 table（哈希桶）的阈值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 给定的cap减1
int n = cap - 1
如果cap本来就是2的幂次方，经过后续的未操作的，cap将会变成2 * cap，是不符合我们预期的
- n无符号右移1位
n |= n >>> 1
- 即n二进制最高位的1右移一位，导致的结果是n二进制的高2位值为1
- 目前n的高1~2位均为1
- n继续无符号右移2位
n |= n >>> 2
- 导致n二进制表示高3~4位经过运算值均为1
- 目前n的高1~4位均为1
- n继续无符号右移4位
n |= n >>> 4
- 导致n二进制表示高5~8位经过运算值均为1；
- 目前n的高1~8位均为1。
- n继续无符号右移8位。
n |= n >>> 8
- n | (n >>> 8)，导致n二进制表示高9~16位经过运算值均为1
- 目前n的高1~16位均为1
- n继续无符号右移16位。
n |= n >>> 16
- 导致n二进制表示高17~32位经过运算值均为1
- 目前n的高1~32位均为1
可以看出，无论给定cap(cap < MAXIMUM_CAPACITY )的值是多少，经过以上运算，其值的二进制所有位都会是1。再将其加1，这时候这个值一定是2的幂次方。当然如果经过运算值大于MAXIMUM_CAPACITY，直接选用MAXIMUM_CAPACITY。
这里可以举个栗子，假设给定的cap的值为20。
int n = cap - 1; —> n = 19(二进制表示：0001 0011)
n |= n >>> 1;
n -> 0001 0011
n >>> 1 -> 0000 1001
n |= n >>> 1 -> 0001 1011
n |= n >>> 2;
n -> 0001 1011
n >>> 2 -> 0000 1101
n |= n >>> 2 -> 0001 1111此时n所有位均为1，后续的位操作均不再改变n的值。
...
n + 1 -> 0010 0000 (32)
最终，tableSizeFor(20)的结果为32(2^5)。
至此tableSizeFor保证cap为2的幂次方
为什么cap要保持为2的幂次方？
- index怎么算
HashMap中存储数据table的index是由key的Hash值决定的 - Hash怎么算
在JDK1.8中，HashMap中key的Hash值由Hash(key)方法（后面会详细分析）计算得来
在HashMap存储数据的时候，我们期望数据能够均匀分布，以避免哈希冲突。自然而然我们就会想到去用%取余的操作来实现我们这一构想 - 优化
取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作
index = e.hash & (newCap - 1)
等同于：
index = e.hash % newCap
采用二进制位操作&，相对于%，能够提高运算效率
参数是map 的构造函数
将另一个map m 里的所有元素加入表中
HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
- 将另一个Map的所有元素加入表中，参数evict初始化时为false，其他情况为true
- 用get() put()
- 判断表是否为空
1.1 为空表，计算阈值
1.2 非空表，判断是否需要扩容 - 遍历 m 依次将元素加入当前表中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();//m的元素数量
if (s > 0) {//元素数量大于0
//如果当前表是空的
if (table == null) { // pre-size
//根据m的元素数量和当前表的加载因子，计算出阈值
float ft = ((float)s / loadFactor) + 1.0F;
//修正阈值的边界
//不能超过MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果新的阈值大于当前阈值
if (t > threshold)
//返回一个>=新的阈值且满足2的n次方的阈值
threshold = tableSizeFor(t);
}
//如果当前元素表不是空的
else if (s > threshold)
resize();
//遍历 m 依次将元素加入当前表中
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()
时机
当前的HashMap的大小大于阀值时，HashMap会对此HashMap的容量进行扩充，即对内部的Entry[] table 数组进行扩充
要求
HashMap对容量（Entry[] table数组长度） 有两点要求：
- 容量的大小应当是 2的N次幂
- 当容量大小超过阀值时，容量扩充为当前的一倍
步骤
容量扩充分为以下几个步骤：
- 确定新的阈值和容量
1.1 旧容量>0
没有超过最大容量，则新表容量、门限为旧表2倍
1.2 旧容量=0，旧门限>0
旧表门限值赋值给新表容量，新表阈值=容量 * 负载因子
1.3 旧容量=0，旧门限=0
则新的容量和门限为默认的容量（16）和门限值（12） - 将当前哈希桶中的所有节点转移到新的哈希桶中
旧的链表不空，且链表中有元素
2.1 链表中就一个元素（没有发生哈希碰撞）
直接将这个元素放置在新的哈希桶里
2.2 发生过哈希碰撞 ,且节点数超过8个
转化成了红黑树
2.3 发生过哈希碰撞，节点数小于8个- 根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置
- 因为扩容是容量翻倍，原链表上的每个节点，现在可能存放在原来的下标low位； 或者扩容后的下标high位
- high位= low位+原哈希桶容量
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //1.1 -------------------------------------------
if (oldCap >= MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
//修改阈值为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; // double threshold
}//表是空的，但有阈值。代表是初始化时指定了容量、阈值的情况
else if (oldThr > 0) // 1.2 -----------------------
newCap = oldThr;
else {// 1.3----------------------------------------
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];
table = newTab; //更新哈希桶引用
//2.-----------------------------------------
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果当前桶中有元素,则将链表赋值给e
oldTab[j] = null;//将原哈希桶置空以便GC
if (e.next == null) //2.1--------------------
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//2.2-----------------------
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //2.3------------------------------------
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
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);
//将低位链表存放在原index处，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
5. 增加---put
确定桶的位置
添加一个元素
put(K key, V value)
Associates the specified value with the specified key in this map.If the map previously contained a mapping for the key, the old value is replaced.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash(K,V) 方法
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower.
- HashMap中table的index是由Key的哈希值决定的
- 而上面我们提到index的运算规则是e.hash & (newCap - 1)。由于newCap是2的幂次方，那么newCap - 1的高位应该全部为0。如果e.hash值只用自身的hashcode的话，那么index只会和e.hash低位做&操作。这样一来，index的值就只有低位参与运算，高位毫无存在感，从而会增加哈希冲突的风险
- HashMap并没有直接使用key的hashcode()，在计算key的哈希值的时候，用其自身hashcode值与其低16位做异或操作
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
。
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
@param
hash： hash for key
key ：the key
value： the value to put
onlyIfAbsent： if true, don't change existing value
evict： if false, the table is in creation mode.
return：previous value, or null if none
流程图和步骤参考自美团点评
对步骤语序逻辑有所调整
流程图
流程图
步骤
- 判断键值对数组table[i]是否为空或为null
如果当前哈希表是空的，代表是初始化，则执行resize()进行扩容 - 根据键值key计算hash值得到插入的数组索引i
- 如果table[i]==null，直接新建节点添加（index 是利用 哈希值 & 哈希桶的长度-1，替代模运算）转向⑥
- 如果table[i]不为空，转向③
- 发生了哈希冲突
判断table[i]的首个元素是否和key一样，相同指的是hashCode以及equals- 如果相同直接覆盖value
- 否则转向④
- 判断table[i] 是否为treeNode，即table[i] 是否是红黑树
- 如果是红黑树，则直接在树中插入键值对
- 否则转向⑤
- 遍历table[i]，判断链表长度是否大于8
- 大于8的话把链表转换为红黑树，在红黑树中执行插入操作
- 否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
- 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容
源码
在构造函数中最多也只是设置了initialCapacity、loadFactor的值，并没有初始化table，table的初始化工作是在put方法中进行的
inal V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.----------------------------------------空表？
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.----------------------------------------数组索引
if ((p = tab[i = (n - 1) & hash]) == null)
//3.----------------------------------------
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果哈希值相等，key也相等，则是覆盖value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4.----------------------------------------
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//5.----------------------------------------
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到尾部，追加新节点到尾部
p.next = newNode(hash, key, value, null);
//如果追加节点后，链表数量>=8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key相同则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null，说明有需要覆盖的节点
if (e != null) { // existing mapping for key
//则覆盖节点值，并返回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这是一个空实现的函数，用作LinkedHashMap重写使用
afterNodeAccess(e);
return oldValue;
}
}
//6.------------------------------------
++modCount;
if (++size > threshold)
resize();
//这是一个空实现的函数，用作LinkedHashMap重写使用
afterNodeInsertion(evict);
return null;
}
6. 删除---remove
remove(key)
执行逻辑：
1）根据key得到key的hash值
2）根据key 和hash值定位需要remove的Node
- 将Node从对应的链表移除，然后再将Node 前后的节点对接起来
4）返回被移除 的Node
5）key-value的数量减一，修改次数加一
小总结：
- 运算尽量都用位运算代替，更高效
- 对于扩容导致需要新建数组存放更多元素时，除了要将老数组中的元素迁移过来，也记得将老数组中的引用置null，以便GC
- 取下标 是用 哈希值 与运算 （桶的长度-1） i = (n - 1) & hash。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
- 扩容时，如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置
- 因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量
- 利用哈希值 与运算 旧的容量 ，if ((e.hash & oldCap) == 0),可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位。这里又是一个利用位运算 代替常规运算的高效点
- 如果追加节点后，链表数量》=8，则转化为红黑树
- 插入节点操作时，有一些空实现的函数，用作LinkedHashMap重写使用。
参考文章
Java集合干货系列-（三）HashMap源码解析
Java官方文档
美团技术团队Java 8系列之重新认识HashMap
源码分析之 HashMap
[Java基础要义] HashMap的设计原理和实现分析
HashMap源码解析（JDK8）
网友评论