-6a7f1793900c4ab1836ed19dd29623a2.jpg)
HashMap源码分析
一、HashMap介绍
HashMap采用key/value存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序；
HashMap继承体系图
-
HashMap实现了Cloneable，可以被克隆。
-
HashMap实现了Serializable，可以被序列化。
-
HashMap继承自AbstractMap，实现了Map接口，具有Map的所有功能。
二、源码解析
HashMap属性
//默认初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//桶的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//缺省负载因子大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化阈值
static final int TREEIFY_THRESHOLD = 8;
//树降级为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//树化的阈值，即当哈希表table中元素个数大于64时，才会允许树化
static final int MIN_TREEIFY_CAPACITY = 64;
//哈希(散列)表,总是2的倍数。数组，又叫作桶（bucket）
transient Node<K, V>[] table;
//存放具体元素的集
transient Set<Map.Entry<K, V>> entrySet;
//当前哈希表中元素个数
transient int size;
//当前哈希表结构修改次数（只有扩容和更改才会记录）
transient int modCount;
//扩容阈值，当哈希表中元素超过阈值时触发扩容
int threshold;
//负载因子(加载因子) threshold = capacity * loadFactor; capacity:数组长度
final float loadFactor;
Node结点
//通过Node变成链表
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;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(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;
}
}
HashMap构造方法
HashMap一共有四个重载方法
空参构造方法——HashMap()
这里没有使用给HashMap指定容量
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 0.75
}
HashMap(int initialCapacity, float loadFactor)
传入初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
//做校验
//capacity是否合法
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;
//计算扩容门槛，不将initialCapacity赋值给threshold是因为必须是2的幂指数
this.threshold = tableSizeFor(initialCapacity);
}
我们接下来继续看看其中的this.threshold = tableSizeFor(initialCapacity);的tableForSize(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;
}
初始一看，属实蒙*....
我们可以带两个数字试试
作用：返回一个大于等于当前cap且最小的2的次方数的一个数字。
即例如 0001 1101 1100 => 0001 1111 1111 + 1 => 0010 0000 0000
cap = 10
n = 10 - 1 = 9
0b1001 | 0b0100 => 0b1101
0b1101 | 0b0011 => 0b1111
0b1111 | 0b0000 => 0b1111
......
0b1111 => 15
返回16
如果 n = cap,不是cap-1
cap = 16
0b10000 | 0b01000 => 0b11000
0b11000 | 0b00110 => 0b11110
0b11110 | 0b00001 => 0b11111
......
0b11111 = 31
return 31+1;
由此可见tableSizeFor(initialCapacity)的作用是返回一个大于等于当前cap且最小的2的次方数的一个数字。不得不佩服JDK的编写者们。
HashMap(int initialCapacity)
这个不难看出这里套娃上面的构造方法......负载因子传入0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap(Map<? extends K, ? extends V> m)
这里不具体展开此构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//hash(key):让key的高16位也参与路由运算
//异或：相同为0，不同为1
//假设 h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
//0b 0010 0101 1010 1100 0011 1111 0010 1110
//^
//0b 0000 0000 0000 0000 0010 0101 1010 1100
//=> 0010 0101 1010 1100 0001 1010 1000 0010
//增加散列性
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
由此可见put()方法具体实现还是putVal(hash(key), key, value, false, true);方法.所以我们来看此方法.
在此之前我们再来看一个预备知识
(n - 1) & hash //其中 n = tab.length;等价于hash % length
上面的代码其实是计算出插入元素在桶的位置，为什么这么做呢？
首先使用位运算，增加运算速率。其次我们知道桶的长度都是2的幂指数，都是形如1000...0000,当我们将length-1后就是01111...111,因此与hash按位与后并不会数组越界，取值范围为[0,length-1)。
由此可见put()方法具体实现还是putVal(hash(key), key, value, false, true);方法.所以我们来看此方法.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab:引用当前hashmap散列表
Node<K, V>[] tab;
//p:当前散列表的元素
Node<K, V> p;
//n：表示散列表数组的长的
//i：表示路由寻址结果
int n, i;
//懒（延迟）初始化，第一次调用putVal时会初始化hashmap中的最耗费内存的散列表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n - 1) & hash 计算元素在哪个桶中
//最简单的一种情况：寻址找到的桶位，刚好是null，这个时候，直接将当前元素k-v扔进去
if ((p = tab[i = (n - 1) & hash]) == null)
// 新建一个节点放在桶中
tab[i] = newNode(hash, key, value, null);
else {
//e:不为null的话，找到了一个与当前要插入的key-value一致的key的元素（如果桶中已经有元素存 //在了）
Node<K, V> e;
//k:表示临时的一个元素
K k;
//表示桶位中的该元素，与你当前要插入的元素的key完全一致，表示后续需要进行替换操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
//链表的情况，而且链表的头元素与我们要插入的key不一致
for (int binCount = 0; ; ++binCount) {
// 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最 //后插入一个新节点
//条件成立的话，说明迭代到最后一个元素了，也没有找到一个与你要插入的key一致的node
//说明 要加到链表的末尾
if ((e = p.next) == null) {
// 如果插入新节点后链表长度大于8，则判断是否需要树化，因为第一个元素没有加到 //binCount中，所以这里-1
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//树化操作
treeifyBin(tab, hash);
break;
}
//条件成立的话，说明找到相同key的node元素，需要进行替换操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// e!=null,条件成立如果找到了一个与你插入元素key一致的数据，需要进行替换
if (e != null) { // existing mapping for key
// 记录下旧值
V oldValue = e.value;
//// 判断是否需要替换旧值
if (!onlyIfAbsent || oldValue == null)
// 替换旧值为新值
e.value = value;
// 在节点被访问后做点什么事，在LinkedHashMap中用到
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
//到这里说明没有找到
//modCount:表示 散列表被修改的次数，替换Node元素的value不计数
++modCount;
//元素数量加1，判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
reSize()方法
final Node<K, V>[] resize() {
//oldTab:引用扩容之前的哈希表
Node<K, V>[] oldTab = table;
//oldCap:引用扩容之前的数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr:表示扩容之前的阈值，触发本次扩容的阈值
int oldThr = threshold;
//newCap:扩容之后table的大小，
//newThr:扩容之后在次出发扩容的条件
int newCap, newThr = 0;
//条件如果成立，说明hashMap的散列表已经初始化过了，是一次正常扩容
if (oldCap > 0) {
//扩容之前的table数组大小已经达到最大阈值，则不扩容，且设置扩容条件为 int 最大值。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//oldCap左移一位实现数据翻倍，并且newCap小于数组最大值 且 扩容之前的数组长度大于16
//这种情况下，则下一次扩容的阈值 等于当前阈值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldCap == 0，说明hashMap中的散列表是null，使用非默认构造方法创建的map，第一次插入元素 //会走到这里
//1.new HashMap(initialCapacity,loadFactor)
//2.new HashMap(initialCapacity)
//3.new HashMap(map)并且map有数据
else if (oldThr > 0) // initial capacity was placed in threshold
{
newCap = oldThr;
}
//oldCap == 0，oldThr == 0
//new HashMap()
// 调用默认构造方法创建的map，第一次插入元素会走到这里
// 如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量 //*默认装载因子
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
}
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;
//说明hashMap本次扩容之前，table不为null
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//当前node节点
Node<K, V> e;
//桶中的第一个元素不为空，即有数据，但是不知道是单个数据还是链表还是红黑树不知道
if ((e = oldTab[j]) != null) {
//清空旧桶，便于GC回收内存
oldTab[j] = null;
//第一种情况：当前桶位只有一个元素，从未发生碰撞，这情况直接计算出当前元素存
// 放在 新数组 中的位置 然后扔进去就可以了
// 因为每次都扩容两倍，所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//第二种情况：判断当前节点已经树化，则把这颗树打散成两颗树插入到新桶中去
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
//第三种情况：桶位已形成链表
else { // preserve order
// 如果这个链表不止一个元素且不是一颗树
// 则分化成两个链表插入到新的桶中去
// 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中
// 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
// 也就是分化成了两个链表
// 低位链表：存放在扩容之后的数组下标位置，与当前数组的下标位置一致。
Node<K, V> loHead = null, loTail = null;
// 高位链表：存放在扩容之后的数组下标位置为当前数组的下标位置 + 扩容之前 //数组的长度。
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
// (e.hash & oldCap) == 0的元素放在低位链表中
//hash-> ...... 1 1111
//hash-> ...... 0 1111
// 0b 10000
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
// (e.hash & oldCap) != 0的元素放在高位链表中
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍历完成分化成两个链表了
// 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容机制很好玩呢，因为它会将原来的链表同过计算e.hash&oldCap==0分成两条链表,再将两条链表散列到新数组的不同位置上.原来有一条链表在tab[2]的位置，扩容以后仍然有一条链在tab[2]的位置，另外一条链在tab[2+8]即tab[10]的位置处。
下面通过一组示例来解释
* 测试目的：理解HashMap发生resize扩容的时候对于链表的优化处理：
* 初始化一个长度为8的HashMap，因此threshold为6，所以当添加第7个数据的时候会发生扩容；
* Map的Key为Integer，因为整数型的hash等于自身；
* 由于hashMap是根据hash &（n - 1）来确定key所在的数组下标位置的，因此根据公式 m（m >= 1）* capacity + hash碰撞的数组索引下标index，可以拿到一组发生hash碰撞的数据；
* 例如本例子capacity = 8， index = 7，数据为：15，23，31，39，47，55，63；
* 有兴趣的读者，可以自己动手过后选择一组不同的数据样本进行测试。
* 根据hash &（n - 1）， n = 8 二进制1000 扩容后 n = 16 二进制10000， 当8的时候由后3位决定位置，16由后4位。
*
* n - 1 : 0111 & index resize--> 1111 & index
* 15 : 1111 = 0111 resize--> 1111 = 1111
* 23 : 10111 = 0111 resize--> 10111 = 0111
* 31 : 11111 = 0111 resize--> 11111 = 1111
* 39 : 100111 = 0111 resize--> 100111 = 0111
* 47 : 101111 = 0111 resize--> 101111 = 1111
* 55 : 110111 = 0111 resize--> 110111 = 0111
* 63 : 111111 = 0111 resize--> 111111 = 1111
*
* 按照传统的方式扩容的话那么需要去遍历链表，然后跟put的时候一样对比key，==，equals，最后再放入新的索引位置；
* 但是从上面数据可以发现原先所有的数据都落在了7的位置上，当发生扩容时候只有15，31，47，63需要移动（index发生了变化），其他的不需要移动；
* 那么如何区分哪些需要移动，哪些不需要移动呢？
* 通过key的hash值直接对old capacity进行按位与&操作如果结果等于0，那么不需要移动反之需要进行移动并且移动的位置等于old capacity + 当前index。
*
* hash & old capacity（8）
* n : 1000 & index
* 15 : 1111 = 1000
* 23 : 10111 = 0000
* 31 : 11111 = 1000
* 39 : 100111 = 0000
* 47 : 101111 = 1000
* 55 : 110111 = 0000
* 63 : 111111 = 1000
*
* 从下面截图可以看到通过源码中的处理方式可以拿到两个链表，需要移动的链表15->31->47->63，不需要移动的链表23->39->55；
* 因此扩容的时候只需要把loHead放到原来的下标索引j（本例j=7），hiHead放到oldCap + j（本例为8 + 7 = 15）
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) {
//引用当前hashMap的散列表
Node<K, V>[] tab;
//first:桶位中的头元素 e:临时元素
Node<K, V> first, e;
//table数组长度
int n;
K k;
//桶有数据，不为空
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;
}
-
根据hash值查找到指定位置的数据
-
校验指定位置第一个节点的数据是key是否为传入的key，如果是直接返回第一个节点，否则继续查找第二个节点
-
如果数据是TreeNode（红黑树结构），直接通过红黑树查找节点数据并返回
-
如果是链表结构，循环查找所有节点，返回数据
-
如果没有找到符合要求的节点，返回null
remove()方法
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//引用当前hashmap中的散列表
Node<K, V>[] tab;
//当前node元素
Node<K, V> p;
//表示寻址结果
int n, index;
// 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空，需要进行查找操作并且删除
//p：指向某个桶位
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node:查找到的结果
//e:当前Node的下一个元素
Node<K, V> node = null, e;
K k;
V v;
//第一种情况：当前桶位中的元素 即为 你要删除的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
node = p;
}
//说明当前桶位要么是链表，要么是树
else if ((e = p.next) != null) {
//第二种情况：当前桶位是红黑树
if (p instanceof TreeNode) {
//红黑树的查找操作
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
}
//第三种情况：链表的情况 遍历
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//判断node不为空的话，说明按照ke查找到需要删除的数据了，看参数是否需要匹配value值，
// 如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//第一种情况：待删除的结点是树，调用删除
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
//第二种情况：待删除的元素是第一个元素，把第二个元素移到第一的位置
else if (node == p)
tab[index] = node.next;
//第三种情况：链表的情况，删除node结点
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
-
先查找元素所在的节点；
-
如果找到的节点是树节点，则按树的移除节点处理；
-
如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置；
-
否则按链表删除节点处理；
-
修改size，调用移除节点后置处理等；
总结
（1）HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构；
（2）HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是2的n次方；
（3）HashMap扩容时每次容量变为原来的两倍；
（4）当桶的数量小于64时不会进行树化，只会扩容；
（5）当桶的数量大于64且单个桶中元素的数量大于8时，进行树化；
（6）当单个桶中元素数量小于6时，进行反树化；
（7）HashMap是非线程安全的容器；
（8）HashMap查找添加元素的时间复杂度都为O(1)；
Q.E.D.
Comments | 0 条评论