HashMap
2019-10-17 本文已影响0人
sizuoyi00
1.HashMap信息
HashMap是一个散列表，底层数据结构由数组和链表（或树形结构）组成，存储的内容是键值对(key-value)映射。
特点：键和值可为null
关于循环删除，增强for循环删除会修改modCount++，导致fail-fast，所以会报错ConcurrentModificationException
迭代器循环删除节点后会重新赋值expectedModCount = modCount;，所以迭代器支持删除
2.HashMap内部结构
集合类一般都没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。
自定义序列化原因：多数情况下内部数组是无法被存满的，序列化未使用的部分，浪费空间
/** 成员变量信息 */
// 底层桶数组，循环数组
transient Node<K,V>[] table;
//HashMap键值对的集合Set，entryset迭代
transient Set<Map.Entry<K,V>> entrySet;
//长度
transient int size;
// fail-fast机制
transient int modCount;
// 初始容量initialCapacity：HashMap初始容量默认16，
// HashMap类并没有该成员变量，有参构造函数的初始容量以threshold临时存储
// 当前HashMap所能容纳键值对数量的最大值，超过这个值，则需扩容
// threshold = capacity * loadFactor
int threshold;
// 负载因子，默认0.75
final float loadFactor;
// 内部类结构 实现链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
//当前结点key
final K key;
//当前结点value
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;
}
//内部类结构 实现红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
3.HashMap构造器
// 初始容量initialCapacity：HashMap初始容量默认16，
// HashMap类并没有该成员变量，有参构造函数的初始容量以threshold临时存储
public HashMap(int initialCapacity, float loadFactor) {
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;
// 有参构造方法还没有对threshold真正计算，阈值真正计算是在初始化容量时计算的，详见后边resize()扩容逻辑
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 找到大于或等于 cap 的最小2的幂 与arrayDeque同
*/
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方法解析
1. int n = cap - 1赋值操作
cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000，十进制数值为8。如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。
2.位操作运算
先来假设n的二进制为01xxx...xxx。接着
对n右移1位：001xx...xxx，再位或：011xx...xxx
对n右移2为：00011...xxx，再位或：01111...xxx
即该算法让最高位的1后面的位全变为1，即0000111111这样前半部分是0后半部分是1的形式也就是2的n次幂减一这样的数的二进制形式。
最后再让结果n+1，即得到了2的整数次幂的值了。
参考：https://www.cnblogs.com/loading4/p/6239441.html
4.get方法
定位键值对所在桶的位置(hash) -> 如果定位到了该位置，key是否与链表第一个相同，相同则返回 -> 如果key值不同，则遍历链表，知道找到key值相同
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;
// 1.定位键值对所在桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 当 tab.length为2的n次幂时 (tab.length - 1) & hash == hash % tab.length
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 2.查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 2. 查找链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4.1.小亮点
// 定位桶数组位置 n=length 数值形如2的n次幂
first = tab[(n - 1) & hash]
- 长度必须为2的n次幂设计原则
1.位运算替换取余运算。
位运算高的效率要远高于取余的计算，通过(length - 1) & hash即可算出桶的在桶数组中的位置，因为HashMap 中桶数组的大小 length 总是2的幂，此时，(length - 1) & hash = hash % length。
为什么上边的两个等式成立?
2的n次幂减一这样的数length的二进制都是如0000111111这样前半部分是0后半部分是1的形式。所以, 用2的n次幂减一这样的数length & 另一个数hash 做与运算时，会保留hash中后x位的1，即保留余数
2.(n - 1) & hash的结果是均匀分布的，可以减少hash冲突。
3.(n - 1) & hash的结果能保证索引值肯定在HashMap的容量大小范围内
合理利用数组+链表的结构，而不是一直扩容桶数组的长度，利用循环数组的思想
参考:https://blog.csdn.net/qq_40378034/article/details/88220732
// 自定义hash计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- HashMap 不直接使用键对象原始 hash 的原因：
1.增加 hash 的复杂度
当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。
2.高位数据参与运算
Java 中，hashCode 方法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。
5.put方法
查找键值对桶位置(hash) -> 如果当前位置无元素，则新增元素到当前位置->如果当前位置有元素，且key相同，则替换元素 -> 如果当前位置有元素，但key不相同，遍历链表，如果链表存在key与入参key相同则替换 -> 遍历到链表最后没有key相同，则新增元素
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;
// 初始化桶数组 1.8new HashMap()默认没有初始化，通过扩容进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 这里计算key的hash%length是否存在元素，循环数组 如果不存在则存放
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果当前key与hash都相同，后边做替换操作
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) {
// 遍历链表中最后一个为空的位置，存放元素
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表长度大于或等于树化阈值，则进行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍历链表元素，如果不为空且hash与key值都相同，跳出遍历后边做替换操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e不为空代表key与hash重复，进行替换
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值(默认16*0.75) 进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
5.1.扩容机制
扩容条件：1.达到阈值后扩容，扩容会rehashing，重新计算位置，一种为原位置，一种为原下标+原容量。2.链上长度达到阈值8，但是数组长度不到64，同1扩容rehashing。3.链表长度达到阈值8，数组长度达到64，链表转红黑树。
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 链表长度达到阈值8，数组长度达到64，链表转红黑树
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组长度<=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);
}
}
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;
}
// 如果 数组长度 大于默认长度16 且 2倍数组长度小于最大值 则 新容量和阈值2倍处理
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 有参构造方法时，将阈值作为初始容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//new HashMap，在这里扩容，桶数组容量为默认容量，阈值为默认容量与默认负载因子乘积
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;
// 扩容情况
if (oldTab != null) {
// 遍历旧桶数组，对新桶数组赋值
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
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
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 会进行 “分组” rehashing
// 即原可能在一条链上，现在会分为两条链，节点顺序不变
// 一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置
// 高低位拆分，原顺序不变，jdk为倒转顺序，可能形成闭环，jdk8原顺序
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);
//将分组后的链表映射到新桶数组中
// rehash分组位置->j
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// rehash分组位置->j + oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
5.2.链表树化、红黑树链化与拆分
6.remove方法
定位键值对所在桶的位置 -> 如果键的值等于链表上第一个节点，则删除数组的值 -> 如果键的值不等于链表的第一个节点，则删除链表的值 -> 遍历链表/红黑树查找删除节点
fail-fast机制
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 1.定位键值对所在桶的位置
Node<K,V> node = null, e; K k; V v;
// 2.键的值与链表第一个节点相等，删除的是数组上的值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 2.键的值与链表第一个节点不同，则删除的是链表上的值
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结点的赋值为删除节点
node = e;
break;
}
//这里p的赋值为删除节点的上一节点
p = e;
} while ((e = e.next) != null);
}
}
// 匹配到的删除节点
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);
//node赋值为删除节点 p赋值在删除链表的情况赋值为上一节点
else if (node == p)
// 桶数组删除节点，两种情况
// 1.该index只有一个值 2该index上有链表，删除第一个值
// 所以这里使用node.next ，如果是情况1该index值为null，情况2该inde值为删除节点的next结点
tab[index] = node.next;
else
// 链表删除节点，与桶数组无关，只需更改"删除节点上一节点p"的next结点为"删除节点下一节点node.next"
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
7.遍历
关于循环删除，增强for循环删除会修改modCount++，导致fail-fast，所以会报错ConcurrentModificationException
迭代器循环删除节点后会重新赋值expectedModCount = modCount，所以迭代器支持删除
// map.keySet().iterator()遍历迭代器
final class KeyIterator extends HashMap.HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
// map.values().iterator()遍历迭代器
final class ValueIterator extends HashMap.HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
// map.entrySet().iterator()遍历迭代器
final class EntryIterator extends HashMap.HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
// 当前角标(桶位置)
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
// 这里index赋值为 第一个包含链表节点 角标
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
// fast-fail机制
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 如果当前结点有next结点，对next节点赋值为链表下一节点，index不变
// 如果当前结点非链表，对next节点赋值为下一角标元素，index+1
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
// 这里删除节点后并没有对modCount修改，所以迭代器支持删除
// 而增强for循环删除会modCount++，与构造器生成的expectedModCount不等，则会删除异常
// 且这里使用内部类的index记录角标无变化，即上边获取next元素不会数组越界
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
8.常见关注点
并发下的hashmap
jdk7死循环：1.7链表新节点采用的是头插法，这样在线程一扩容迁移元素时，会将元素顺序改变，导致两个线程中出现元素的相互指向而形成循环链表，1.8采用了尾插法，从根源上杜绝了这种情况的发生。
面试高频
参考：
https://segmentfault.com/a/1190000012926722?utm_source=tag-newest#articleHeader3
