Java8 HashMap结构
Paste_Image.png
构造方法
threshold = tableSizeFor(initialCapacity);
这里只是将initialCapacity暂放在threshold中，threshold最终并不是用这值作为实际的阀值在下面的resize的红色方框中会判断这情况当oldThr>0,会将oldThr，即threshold = tableSizeFor(initialCapacity);中的threshold赋值给newCap
Paste_Image.png
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;
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor
tableSizeFor 主要的目的是得到一个不小initialCapacity的最小的2^n 值，如initialCapacity = 3 则取22=4,initialCapacity=6取23=8 等等
算法的原理是让（initialCapacity-1）从最高位1往右都变为1，即mask
mask：二进制所有位都是1，如：111，1111，1111...等等
然后mask+1 即可得到最小的2^n
为什么要先n = cap - 1，最后再n + 1呢？
这时为了兼容cap本身就是2^n的情况，不先
n = cap - 1，最后cap值会是2^（n+1） 即最小的2^n的两倍
当cap=2^n时
又2^n =mask+1，
所以cap - 1= 2^n -1=mask+1-1=mask
mask执行算法最后还是为mask原值，最终执行n+1，即mask+1=2^n
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;
}
Paste_Image.png
put（putVal）
put方法实际调用的就是putVal，整个方法分为三种情况：
1.新建的节点与table索引上的第一个节点key相同
2.table索引上的节点为红黑树节点，新建的节点转为红黑树节点
3.新建的节点与table索引上的一条链表一一比较（table索引上的第一个节点key与新建节点Key不相同）
当执行完上面的步骤后判断当前table的size是否超过阀值threshold，超过则进行扩容 resize()
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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为空，则调用resize()初始化table
//resize() 两种情况：1.开始阶段初始化table 2.扩容新的table 原先的2倍容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果在table的索引位置没有节点，即没有任何冲突
//则直接将新建的节点放到table[索引] 即可
//注意索引=(n - 1) & hash 计算出来的
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果在table的索引位置已有节点了，即冲突了
else {
Node<K,V> e; K k;
//情况1：table索引上的节点 与 新建的节点hash冲突了，且key相同
//首先p = tab[i = (n - 1) & hash]，即p为该table索引上的第一个节点
//用p与新建的节点 相比较，如果key相同，则将p节点 暂存到 e中待后面出来
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//情况2：table索引上的节点是树节点TreeNode，则将新建的节点putTreeVal 放到该红黑树节点上
//如果 p instanceof TreeNode，可以判断出该table索引上已经不是链表了，而是红黑树结构
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//情况3：table索引上是链表，而且第一个节点 与新建的节点key 不相同
//则遍历该链表，一个节点一个节点与新建节点对比 看是否存在与 新建的节点key相同
else {
for (int binCount = 0; ; ++binCount) {
//上面提到了，p为该table索引上的第一个节点
//所以p.next == null ,说明p没有下一个节点
//说明该table索引上只有p节点时
if ((e = p.next) == null) {
//将p的下一个节点指向 新建的节点
p.next = newNode(hash, key, value, null);
//如果binCount>=8-1=7
//实际上这里统计的节点个数还是8个，因为binCount是从0开始的
//当节点个数超过8个时（包含8）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//则将该链表 转换 为红黑树
treeifyBin(tab, hash);
break;
}
//因为上面执行了(e = p.next)，所以现在e是p的下一个节点
//如果e与 新建节点的key 相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//统一为上面的几种情况设值
//如果e不为空，设置e的value为新建节点的value，并返回e原先的值
//包含情况1：e为table索引上的第一个节点
//包含情况2：e为红黑树的节点
//包含情况3：e为链表上的节点，非table索引上的第一个节点，而是其他节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//threshold=newThr:(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//默认0.75*16，大于threshold值就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize
Paste_Image.png
/**
* <pre>
* 以哈希表方式实现的Map接口，允许key和value为null
* （除非线程安全及允许null值外，HashMap基本与Hashtable等价）
*
* 本类不保证元素的顺序，特别地，顺序也可能随时间改变
*
* 在散列特性较好（元素基本均匀分布于bucket）时，本类get和put操作均为O(1)量级
* 遍历整个map的时间正比于：HashMap的容量（capacity）+元素总数（注意不只是元素数）
* 因此最好不要把初始容量设置过高或负载因子（load factor）设置过低
*
* 容量指HashMap中桶的个数，负载因子指HashMap填充到多大比例时允许自动扩容
* 当size>load factor*capacity时, 哈希表将重组（rehashed），其内部结构会发生改变。rehash以后桶的数量将大致翻倍
* 根据经验，负载因子=0.75（默认值）时时空效率达到较好的平衡值
* 设置初始容量时，最好综合考虑元素数的估计值和负载因子，从而减少rehash的次数
*
* 注意如果很多key的hashCode相同必然会降低HashMap的速度
* 为改善这点，当key实现{@link Comparable}时，本类会利用Comparable的顺序来处理hashCode相同
*
* 本类不是线程同步的，如果多线程访问HashMap，且至少有一个线程进行了结构更改，那么这个需要在外层synchronize
* （结构更改指增删元素，不包含更新已有key的value值）
* 使用Collections.synchronizedMap(new HashMap(...)是另一种同步方式
*
* 本类返回的所有迭代子都是fail-fast的
* 即迭代子生成后如果发生任何结构更改（迭代子自身的remove方法除外），迭代子都会抛出{@link ConcurrentModificationException}
* 注意fail-fast特征并不能严格保证，而只是尽可能实现（有可能漏抛）
* 因此不能利用是否抛ConcurrentModificationException来保证程序的正确性，这个异常的作用是辅助发现bug
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*
* @author Doug Lea,Josh Bloch,Arthur van Hoff,Neal Gafter
* @see Object#hashCode(),Collection,Map,TreeMap,Hashtable
* @since 1.2
*/
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
/**
* 实现说明
*
* <pre>
* 本类通常是由桶组成的哈希表，然而当桶的尺寸过大时，会将节点重构为TreeNode（每个节点类似java.util.TreeMap）
* 大部分方法实现会判断节点的instanceof，如果是TreeNode，则会采取不同的实现方式
* TreeNode元素支持普通元素的所有操作（对外透明），但提供更快的查询速度
*
* 包含TreeNode的桶首先按hashCode排序，在tie时如果实现了Comparable，则会根据Comparable决定顺序
* （这里通过反射来判断，参见comparableClassFor方法）
* TreeNode机制使得在散列特性不好的情况下，也能保证最差O(log n)的时间性能
*
* 由于TreeNode的尺寸是常规节点大约2倍，因此仅当桶的尺寸大于TREEIFY_THRESHOLD时才会使用TreeNode
* 如果TreeNode的尺寸减小到一定程度（由于remove或resize），还会重新变回普通节点
* 如果散列值的随机性较好，则桶的尺寸与桶数大致服从Poisson分布，因此基本不会用到TreeNode
* (http://en.wikipedia.org/wiki/Poisson_distribution)
*
* 一个TreeNode桶的根节点通常是第一个节点，但有些时候（目前只有Iterator.remove）也会是其他元素
* but can be recovered following parent links (method TreeNode.root()).
*
* 所有具体实现的内部方法都包含hashcode参数（通常在调用public方法是生成），用以在互相调用时不必重新计算hashCode
* 大部分方法包含tab参数，其值大部分情况下就是当前的哈希表自身，但在resizing或converting时可能不同
*
* 当桶列表发生建树（treeify）、分裂、退化（untreeify）时，仍然维护其原先链结构(i.e., Node.next)
* 树结构中按照hash值、Comparator、tie-breakers三层优先方式进行排序
*
* 树结构与链结构的转换在子类LinkedHashMap中会更复杂一些，本类中预留了一些回调方法给LinkedHashMap
*/
// 一些常量/////////////////
// 默认的初始容量，必须是2的幂次
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 建树阈值，桶内元素大于这个数值时会转为TreeNode桶
// 这个数值至少为8以兼容remove操作时退化为普通节点的机制
static final int TREEIFY_THRESHOLD = 8;
// 退树阈值，TreeNode桶内元素小于这个数值时会退化为普通节点
// 数值必须小于TREEIFY_THRESHOLD，至少为6
static final int UNTREEIFY_THRESHOLD = 6;
// 最小的建树容量，这个数值不能小于4 * TREEIFY_THRESHOLD以免resize和treeify机制相互冲突
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 基础的桶节点（bin node），大部分Entry的实现类
*/
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;
}
@Override
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
@Override
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
@Override
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;
}
}
// 一些静态辅助方法/////////////////////
/**
* 计算key的hashCode，并将高低16字节异或（注意不是直接key.hashCode()拿来用）
*
* 由于容量是2的幂次，仅高位不同的hashCode总会落到同一个桶（例如整数部分相同的若干浮点数）
* 这使得原始的hashCode很可能造成不好的散列特性，因此通过xor操作将高位的影响扩散到低位
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 通过反射判断对象x是否实现Comparable<C>接口
*
* @return 如果实现了Comparable，返回x的实际类型，也就是Class<C>，否则返回null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c;
Type[] ts, as;
Type t;
ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType)
&& ((p = (ParameterizedType) t).getRawType() == Comparable.class)
&& (as = p.getActualTypeArguments()) != null && as.length == 1
&& as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
/**
* 如果x实际类型是kc，则返回k.compareTo(x)，否则返回0
*
* @param kc 必须实现Comparable
* @param k 类型为kc
* @param x 类型无限制
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
}
/**
* 返回不小于cap的最小的2的幂次
*/
static final int tableSizeFor(int cap) {
// 低位全部用1填充
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;
}
// 实例属性/////////////////////
// 实际数据的存储结构，尺寸可能变更
transient Node<K, V>[] table;
// entrySet()缓存
transient Set<Map.Entry<K, V>> entrySet;
// 实际元素个数
transient int size;
// HashMap发生结构变更的计数器，结构变更包括增删元素、rehash等，这个属性为实现迭代子的fast-fail特性
transient int modCount;
// 下一个resize的元素个数 (capacity * load factor).
int threshold;
// 负载因子
final float loadFactor;
// public方法/////////////////////
/**
* 含参构造函数
*
* @param initialCapacity
* @param loadFactor
* @throws IllegalArgumentException initialCapacity<0或loadFactor<=0
*/
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;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 根据已有Map构造一个新的HashMap，负载因子取默认值，初始容量根据m.size()确定
*
* @throws NullPointerException if m==null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 将m的所有元素放入本对象，实现Map.putAll和构造函数
*
* @param m the map
* @param evict 初始化调用为false，否则为true
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
// 初始化情形，根据m.size初始化threshold
float ft = (s / loadFactor) + 1.0F;
int t = ((ft < MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold) {
// 非初始化，如果m.size已经超过threshold，则立刻resize
// 注意不包含现有元素，putVal()还有尺寸操作
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);
}
}
}
/**
* 返回key对应的value，如果没有返回null
*
* 是否包含通过key.equals()确定
*
* @return 注意返回null不一定代表key不存在，有可能对应的value就是null。如需区分可使用{@link #containsKey containsKey}
* @see #put(Object, Object)
*/
@Override
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* get的实现
*
* @param hash
* @return the node 不存在返回null
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab; // table的快照
Node<K, V> first, e;
int n;
K k;
// first = tab[(n - 1) & hash]是hash对应桶的第一个元素
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; // 第一个equal就直接返回了
}
// 否则如果是TreeNode就调用TreeNode的get，不是就直接根据.next遍历桶
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;
}
/**
* 是否包含，这个实际逻辑与get基本是一样的
*/
@Override
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
/**
* 放入一个kv对，如果key已经存在，则value被替换
*
* @return 如果原先包含key，则返回旧的value，否则返回null
*/
@Override
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* put的实现
*
* @param hash
* @param onlyIfAbsent true表示仅当key不存在的情况才执行put（不修改已存在的值）
* @param evict false表示创建过程中
* @return 如果原先包含key，则返回旧的value，否则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化情况
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// key对应的桶不存在情况（key也必然不存在），new一个新node就行了
tab[i] = newNode(hash, key, value, null);
else { // 桶存在情况
Node<K, V> e; // 表示key的（可能有的）现有节点
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 第一个就是，直接拿过来
else if (p instanceof TreeNode) {
// TreeNode情况
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
} else {
// 非TreeNode，循环遍历桶
for (int binCount = 0;; ++binCount) {
if ((e = p.next) == null) { // 确实没有，new一个新node
p.next = newNode(hash, key, value, null);
// 如果桶的尺寸超过了TREEIFY_THRESHOLD，这个桶要转化为树
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) { // 所有的已存在情况，更新value并返回旧value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 子类回调
return oldValue;
}
}
// 到这说明新加了节点，modCount+1
// 注意这里只处理增加节点，如果触发resize或者treeify，会在对应方法里继续维护modCount
++modCount;
if (++size > threshold) // size超过阈值，触发resize
resize();
afterNodeInsertion(evict); // 子类回调
return null;
}
/**
* 初始化或扩容
*
* 由于容量是2的幂次，resize后元素下标或者不变，或者增加2的幂次
*
* @return 扩容后的表
*/
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 // 扩容，容量*2
&& oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // 初始化情况
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 更新threshold
if (newThr == 0) {
float ft = newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ? (int) ft
: Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({ "unchecked" })
Node<K, V>[] newTab = 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; // 旧表置null以便空间快速回收
if (e.next == null) { // 只有一个元素的桶，直接扔到新的桶（新桶一定是空的）
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) { // 处理TreeNode分裂
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
} else { // 普通的桶，逐个处理
Node<K, V> loHead = null, loTail = null; // 原桶的首位指针
Node<K, V> hiHead = null, hiTail = null; // 新桶(+oldCap)的首位指针
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;
}
/**
* 将指定的桶转化为TreeNode
*/
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)
resize(); // 如果容量小于MIN_TREEIFY_CAPACITY，则直接扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K, V> hd = null, tl = null;
do { // 先把Node链表转成TreeNode链表
TreeNode<K, V> p = replacementTreeNode(e, null); // 当前节点生成的TreeNode
if (tl == null) {
hd = p;
} else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 然后将TreeNode链表转成树
if ((tab[index] = hd) != null) {
hd.treeify(tab);
}
}
}
/**
* 批量put
*/
@Override
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
/**
* 删除对应Key的元素
*
* @param key 注意是Object，类型不要传错
* @return 如果key存在，返回删除前的value，否则返回null
*/
@Override
public V remove(Object key) {
Node<K, V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
/**
* 删除节点实现
*
* @param hash
* @param key
* @param value 如果matchValue=true，表示匹配的value，否则无作用
* @param matchValue true表示仅当key对应value等于matchValue时才删除
* @param movable false表示不移动其他元素（迭代子使用）
* @return 如果删了，返回被删的元素，否则返回null
*/
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) {
Node<K, V> node = null, e; // node为待删元素
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) // 如果是TreeNode，从TreeNode取key的元素
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);
}
}
if (node != null
&& (!matchValue || (v = node.value) == value || (value != null && value
.equals(v)))) { // 这条件表示确实要删
// TreeNode就按TreeNode删，否则在链表删
if (node instanceof TreeNode) {
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
} else if (node == p)
tab[index] = node.next;
else {
p.next = node.next;
}
++modCount; // 删除元素造成的结构变更
--size;
afterNodeRemoval(node); // 子类回调
return node;
}
}
return null;
}
/**
* 清空（全部删除）
*/
@Override
public void clear() {
Node<K, V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i) { // 所有的桶都置为null
tab[i] = null;
}
}
}
/**
* 包含（一个或多个）value。因为没有倒排，这个方法要遍历全表，慎用
*
* @param value
*/
@Override
public boolean containsValue(Object value) {
Node<K, V>[] tab;
V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) { // 遍历表
for (Node<K, V> e = tab[i]; e != null; e = e.next) {
// 遍历桶。注意TreeNode还是维持打平的链表关系，所以不用特别处理
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
