【数据结构】Java 常用集合类 HashMap(JDK 1.8)

用户头像
Alex🐒
关注
发布于: 2020 年 07 月 21 日

整体设计

HashMap 实现了 Map 接口,存储 key-value 的散列表。与 HashTable 类似相似,区别是:

  1. 线程不安全;

  2. 允许键或值为 null;



HashMap 采用“数组+链表/红黑树”的结构存储,数组可以扩容,链表可以转化为红黑树。能提供常量时间性能的基本操作 get()put()。迭代器遍历的效率与容量和存储KV数量有关。HashMap 不保证存入的KV的次序。

HashMap 属性

DEFAULT_INITIAL_CAPACITY # 默认初始化容量(1<<4=16)
MAXIMUM_CAPACITY # 最大的容量(1<<30=2^30)
DEFAULT_LOAD_FACTOR # 默认的载入因子(0.75f)
TREEIFY_THRESHOLD # 当桶上的结点数(链表长度)大于这个值时转红黑树(8)
UNTREEIFY_THRESHOLD # 当桶上的结点数(红黑树大小)小于这个值时转为链表(6)
MIN_TREEIFY_CAPACITY # 桶进行转换的时,Map的最小的容量(64),为了避免扩容和转换的冲突,至少是4*TREEIFY_THRESHOLD

初始容量大小和载入因子会影响 HashMap 的性能。初始容量指的是桶的数量。载入因子是来衡量 HashMap 在其容量增加之前允许达到的完整度。当 HashMap 中的 key 数量超过了载入因子和当前容量,HashMap 就会扩容(resize),新的 HashMap 桶的数量变为原来的两倍。



通常载入因子设置成 0.75,超过这个值会减少空间开销,但是会增加查询开销。设置初始容量的时候需要考虑 HashMap 将容纳的数量和载入因子,这样可以减少 resize 次数,从而减少性能损耗。



HashMap 在 JDK8 与 JDK7 实现上比较大的不同在于,当桶上结点的数量过大的时候,会将结构改变成树结构。树结构在数量过多的时候查找效率会得到提升。

HashMap 构造函数

transient Node<K,V>[] table; // 存储数据的桶
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
public HashMap(int initialCapacity, float loadFactor) {
// ... 检查 initialCapacity 和 loadFactor
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(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;
}



tableSizeFor(initialCapacity) 返回大于等于初始容量的的最小的二次幂数值,threshold 作为判断 resize 的阈值。



从构造函数可以看出,这时候并没有初始化桶(Node<K,V>[] table)。这里和 JDK7 的操作不同,JDK7 HashMap 构造方法中就初始化了哈希表。



另外一个重要的构造函数,用一个 Map 初始化 HashMap

public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// 将 m 的所有元素存入当前 HashMap 实例中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
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);
}
}
}

哈希桶

HashMap 采用哈希表存储数据,使用拉链法(链地址法)解决哈希值冲突,即每个哈希值对应存储一个链表。Node<K,V> 对象就是链表的实现。

static class Node<K,V> implements Map.Entry<K,V> {
// 键的哈希值,定位在 Node[] 中的位置
final int hash;
final K key;
V value;
// 桶是一个链表,表示当前结点所在链表的下一个结点
Node<K,V> next;
}

HashMap get() 方法

首先计算出 key 的 hashCode,找到 table 中的数组索引,即 Node<K, V> 对象,如果存在,判断该结点是否等于要查询的节点,如果不是,按照链表或者红黑树的查询方式查找。

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断 table 是否存在,hashCode 所在的索引是有为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 查询 key,先查询第一个,然后在查询 Node
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;
}



(n - 1) & hash 得到哈希值对应 table 的索引。如果桶是由树组成,Node 是子类 TreeNode 实现的。

HashMap put() 方法

put 相比 get 更复杂,会涉及到 table 的 resize()treeify()。首先判断 table 是否存在,不存在就创建。



判断 hashCode 对应位置是否有值,没有值就直接存入。如果存在就判断这第一个键是否相等,最后才根据 onlyIfAbsent(是否覆盖)来决定是否更新 value。如果第一个不相同,根据链表或者树的对应插入方法插入或更新(如果 key 存在,根据 onlyIfAbsent 判断)。



如果插入数据成功并且 Node 是链表,判断当前数量是否达到转换成树结构的阈值(TREEIFY_THRESHOLD),进行 treeify() 操作。最后再判断哈希表是否需要扩容。

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
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 对应位置为空,直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 先判断 Node 一个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 第一个元素的 key 和当前元素相同
e = p;
else if (p instanceof TreeNode)
// 使用 TreeNode 的方法插入数据
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 使用链表的方法插入数据
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 不存则在插入
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表转换为树结构
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
// 如果 key 存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// Callbacks to allow LinkedHashMap post-actions
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 哈希表进行扩容
resize();
// Callbacks to allow LinkedHashMap post-actions
afterNodeInsertion(evict);
return null;
}



modCount 记录 HashMap 内部结构发生变化的次数,主要用于 fast-fail 机制。但是 key 值对应的 value 被更新不会计数 modCountafterNodeAccess()afterNodeInsertion() 方法,提供了后置处理接口,子类可以实现该方法。

treeify 转换

链表转换为树结构,当该链表的长度超过8时执行。(扩展:为什么Map桶中个数超过 8 才转为红黑树?

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// tab 容量小于 MIN_TREEIFY_CAPACITY 优先扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// Node 转换 TreeNode
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);
// 把转换后的 TreeNode,替换原来位置上的 Node
// 此时 TreeNode 还是双向链表的结构
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}



如果 table 大小小于 MIN_TREEIFY_CAPACITY(树结构化的最小限制),优先进行 resize 的效果更好,因为当 table 某个位置上集中了多个键值对,是因为这些 key 的 hashCode 和数组长度取模之后结果相同(并不是因为这些 key 的 hashCode 相同,hashCode 相同的概率比较低),所以可能是 table 数组的数量比较小造成的,可以通过扩容的方式,使得这些 key 分散到多个数组位置上。

treeify 方法

遍历双向链表,转换为红黑树结构。

final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}

resize 扩容

每次 resize,新的数组是原数组大小的两倍。resize 过程:

  1. 初始化过程,包括 oldTab(原表),oldCap(原表长度),newCap(新表长度)和 newThr(新表扩容阈值)。

  2. 根据计算出来的新表大小生成新表 newTab

  3. 如果 oldTab 不为空,遍历 oldTab 的每个桶,放入 newTab。

  4. 返回 newTab。

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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 扩容一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
// 使用默认容量(16)
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;
// 创建新的表,并且覆盖 table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历 oldTable 的每个桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果桶中只有一个元素,直接放入 newTab
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果桶中是 TreeNode
// 将树的数据重新散列到 newTab 中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 如果桶中是链表 Node
// 这里就看出了为什么要扩容为两倍
// 扩容两倍之后,数据在新桶中的位置只有两个 lo 和 hi
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;
}
// 新桶中位置为 old + oldCap
else {
// 逻辑与上面相同
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 转换为两个新的链表(或一个),放入 newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

在扩容开始的时候,table 就被覆盖为 newTab(空的扩容后大小),<u>如果自此有 put 方法调用,会写入新的空的 table,不会写入 oldTab</u>。



为什么扩容两倍?

更加容易计算他们所在的新桶位置。如原桶长度是 4,现在桶长度是 8,那么:桶0中的元素会被分到桶0和桶4中,桶1中的元素会被分到桶1和桶5中,以此类推。



oldCap 假如是16(二进制为10000),扩容变成32(二进制为100000)。当 hashCode & 10000 ==0,那么 hashCode 的右起第五位肯定也是0,所以 hashCode & 100000 还是0,反之亦然。

与 JDK7 的区别

JDK7 种扩容的实现

void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个新的 Entry 数组
Entry[] newTable = new Entry[newCapacity];
// 将数据转移到新的 Entry 数组里
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 覆盖 table 和 threshold
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 重点全在这个函数中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 元素在新数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}



函数 transfer() 是链表重新散列方法,也是导致 HashMap 死锁问题的关键:

  1. 对原数组中的元素遍历,并计算出元素 e 在新数组中的位置 i

  2. e 放入新数组 i 对应链表 Entry 的头部,因为 Entry 可能有元素存在,所以先将 e.next 指向 Entry 第一个元素(如果 Entry 是空,则 e.next = null),这时候 Entry 第一个元素是 e,newTable[i] 指向的是原 Entry 的第一个元素,所以设置 newTable[i] = e

  3. 循环2,直到链表节点全部转移

  4. 循环1,直到所有索引数组全部转移



在多线程场景下会出现同时 put 操作,并进入了 transfer。假设现在有三个线程:T1、T2, oldTable[i]=A,newTable[i]=B(B.next=C),A 在 newTable 的位置还是 i,当前 e 引用 A。

1. 当T1运行到 e.next=newTable[i] 时,T2运行到 Entry<K,V> next = e.next。
2. T1运行 newTable[i]=e, e=next,会产生的结果:newTable[i]=A,A.next=B,B.next=C,e=B。
3. T2运行 e.next=newTable[i],会产生的结果:B.next=A,同时 A.next=B,



JDK8 改进算法后不会再出现环状链表的情况,但并发时仍然不建议使用 HashMap。






发布于: 2020 年 07 月 21 日 阅读数: 32
用户头像

Alex🐒

关注

还未添加个人签名 2020.04.30 加入

还未添加个人简介

评论

发布
暂无评论
【数据结构】Java 常用集合类 HashMap(JDK 1.8)