学习JDK1.8集合源码之--HashMap
2024-09-04 06:58:16
1. HashMap简介
HashMap是一种key-value结构存储数据的集合，是map集合的经典哈希实现。
HashMap允许存储null键和null值，但null键最多只能有一个（HashSet就是以HashMap实现的，通过HashMap的key存储元素，所以HashSet也最多允许存储一个null值并且其中的元素不可重复）。
HashMap是非线程安全的实现，在多线程环境下会出现数据丢失的情况，与JDK1.8以前不同的是并不会出现死循环的情况。在多线程情况下最好使用ConcurrentHashMap来代替。
需要注意的是，本文主要针对JDK8版本进来分析，JDK8以前的HashMap是数组+链表的简单实现，但在JDK8后，当链表中的元素超过8个后就会采用红黑树来进行存储，为了避免链表中数据量太大造成的查找效率低下的问题。因为链表的查询时间复杂度是O(n)，即随着链表中元素个数的增加，当数据增大n倍时，耗时增大n倍；而红黑树的查询时间复杂度为O(logn)，即当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。
2. HashMap实现
1. 核心参数
//默认初始容量16，1左移4位相当于2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//由链表转换成树的阈值
static final int TREEIFY_THRESHOLD = 8;
//由树转换成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//当桶中的bin被树化时最小的hash表容量
static final int MIN_TREEIFY_CAPACITY = 64;
//Node数组存储元素
transient Node<K,V>[] table;
//内部entry实体的集合
transient Set<Map.Entry<K,V>> entrySet;
//map大小
transient int size;
//修改次数
transient int modCount;
//需要进行扩容的阈值，capacity * loadFactor，如果没有进行扩容过，则threshold的值可能为0，也可能等于底层数组的容量
int threshold;
//加载因子，表明存储元素的最大饱和度
final float loadFactor;
//静态内部类，实现了Map.Entry接口，用于存储每个节点的数据
static class Node<K,V> implements Map.Entry<K,V> {
//key的hashcode值
final int hash;
//Map的key
final K key;
//Map的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;
} //返回map的key
public final K getKey() { return key; }
//返回map的value
public final V getValue() { return value; }
//重写toString方法
public final String toString() { return key + "=" + 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;
}
//重写equals方法
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;
}
} //红黑树节点，由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性
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
//红黑树的颜色，true为red，false为black
boolean red;
}
从上面可以看出，HashMap底层首先是由数组来存储的，存储的元素为Entry实体，Entry中包含hashCode、key、value、next四个属性。理想情况下，数组中每个位置最多存储一个Entry实体，数组中每个Entry实体的hashCode、key都是不同的，next都是null。但如果出现了hash碰撞（两个Entry实体的通过hash运算得到的下标相同），则会以链表形式存储hashCode相同的元素，而链表的头部都存在数组里面。所以当出现hash碰撞时，不会把新的Entry实体插入数组，而是根据hashCode找到数组中存储的链表头，然后根据链表头的next指针依次遍历链表，直到找到next为null的Entry实体，把新加的实体赋给next为null的Entry实体的next，这样就完成了一次插入过程。JDK8之前这样就结束了，但是在JDK8里，当链表超过8个，就会改用红黑树来存储，至于是如何通过红黑树存储的，下面再做分析。
2. 构造方法
//无参构造，默认加载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
} //传入一个初始容量，默认加载因子0.75，初始容量必须是2的次幂，若不是则会使用比传入初始容量大的最小2的次幂
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} //传入初始容量和默认加载因子，初始容量必须是2的次幂，若不是则会使用比传入初始容量大的最小2的次幂
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//初始容量不能大于2^30，因为2^31大于int最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子不能小于等于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//计算初始容量，为了保证容量为2的次幂
this.threshold = tableSizeFor(initialCapacity);
} //传入一个map，使用默认加载因子0.75，并把map中的元素存入HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
构造方法主要以初始容量和加载因子为主，因为这两个参数是HashMap构造的最核心的参数，并且有参构造的初始容量是赋值给threshold的，构造期间没有进行底层数据的实例化。这里和ArrayList一样，都是在添加元素的时候才会实例化一个数组，而实例化时数组的容量就取threshold的值，无参构造构造的话就会取定义的默认初始容量16。这也就解释了threshold值可能存在的三种情况：0，capacity，capacity * loadFactor。
3. 核心方法
HashMap内部的核心方法包括hash、tableSizeFor、putMapEntries、putVal、getNode、resize、treeifyBin、removeNode等方法。
hash：HashMap没有采用Object类的hashCode函数，而是内部实现的hash函数，通过key的hashcode高16位不变，然后低16位采用高16位于低16位进行异或运算的结果，来减少hash碰撞。
tableSizeFor：保证了HashMap初始化的时候容量为2的次幂，这是HashMap的实现核心基础。因为HashMap底层基于数组实现的，数组是一种通过索引机制来进行数组存储的，所以在查询时效率比较高，但是HashMap是一种以key-value形式存储的数据结构，想要通过key快速找到对应的value就要利用数组的索引机制，可是该如何利用呢？答案是根据key的hashCode与元素的length-1进行与运算得到数组的索引，Hashmap在进行存储、查找、删除等操作时都是通过这种方式的。
putMapEntries：向HashMap中添加一个map中的所有元素。putMapEntries实际上也是通过putVal来进行元素添加的。
putVal：向HashMap中添加元素的实现方法。每次添加元素根据key的hashCode与元素的length-1进行与运算得到数组的索引，如果该索引位置为空则添加的时间复杂度为O(1)，这也是HashMap最理想的状态（不存在hash碰撞）。之所以HashMap采用数组+链表的结构存储是为了解决hash碰撞的问题，当出现hash碰撞时就要用链表来存储，因为链表的时间复杂度是O(n)，故当出现hash碰撞时的时间复杂度是O(n)。在JDK1.8以前HashMap最差的情况下时间复杂度是O(n)，但是在JDK1.8里加入红黑树来进行了优化。当链表中的元素个数大于8个的时候就会采用红黑树代替链表来进行存储，因为红黑树的时间复杂度为O(logn)，所以当链表中元素大于8的时候putVal的时间复杂度为O(logn)，不过因为putVal方法还涉及到扩容、链表转红黑树等操作，情况比较复杂。
getNode：根据key获取对应节点。跟putVal差不多，根据key的hashCode与元素的length-1进行与运算得到数组的索引，如果该索引位置的key就是需要查找的key则查找的时间复杂度为O(1)；若不是则要看该索引位置的节点是不是树形节点，如果是树形节点则说明是由红黑树存储的，这时的查找时间复杂度为O(logn)；若不是树形节点则说明是由链表存储，这时的时间复杂度为O(n)。
resize：HashMap核心扩容算法。该方法会把原数组扩容1倍并进行reHash，将原来的存储结构（链表和红黑树）打乱重新构造，使新数组数组尽量的分布均匀。至于是如何实现的，请看下面的resize方法注释。当是红黑树存储时，会调用红黑树的split函数进行处理，如果是链表则会把key的hashCode与原数组的容量进行与运算，结果为0则在新数组位置不变，否则在新数组的位置为原数组容量+原数组下标。
treeifyBin：树形化，链表转为红黑树的核心处理逻辑。实际上是调用内部类TreeNode的treeify方法来构建红黑树。
removeNode：根据key移除对应节点。先查找到该节点，逻辑与getNode一致。然后判断该节点类型，如果是树形节点，则移除后重组红黑树；如果是链表，则移除后重组链表。
//hash函数，高16bit不变，低16bit和高16bit做了一个异或，目的是减少hash碰撞。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} //判断x是否实现了Comparable接口并且Comparable的泛型类型与x的类型相同
//若是则返回x的Class类型，否则返回null
static Class<?> comparableClassFor(Object x) {
//如果x没有实现Comparable接口，则直接返回null
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
//x.getClass()返回x的class类型并赋值给c，同时判断c是否为String.class，是则将c返回
if ((c = x.getClass()) == String.class) // bypass checks
return c;
//将c中直接实现的所有接口赋值给ts
//Type是Java 编程语言中所有类型的公共高级接口（官方解释），
//Type体系中类型的包括：原始类型(Class)、参数化类型(ParameterizedType)、数组类型(GenericArrayType)、类型变量(TypeVariable)、基本类型(Class);
//原始类型，不仅仅包含我们平常所指的类，还包括枚举、数组、注解等；
//参数化类型，就是我们平常所用到的泛型List、Map；
//数组类型，并不是我们工作中所使用的数组String[] 、byte[]，而是带有泛型的数组，即T[] ；
//基本类型，也就是我们所说的java的基本类型，即int,float,double等
if ((ts = c.getGenericInterfaces()) != null) {
//遍历c中实现的接口类型
for (int i = 0; i < ts.length; ++i) {
//如果当前类型属于参数化类型
if (((t = ts[i]) instanceof ParameterizedType) &&
//并且该类型是Comparable.class （getRawType返回声明了这个类型的类或接口）
((p = (ParameterizedType)t).getRawType() == Comparable.class) &&
//并且该类型的泛型参数列表不为空 （getActualTypeArguments以数组的形式返回泛型参数列表）
(as = p.getActualTypeArguments()) != null &&
//并且该类型的泛型参数列表只有一个参数该参数就是c
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
} //比较两个实现了Comparable接口的同类型元素的大小，k比x大返回1，k比x小返回-1，x为null或不是同类型返回0
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
} //用于初始化HashMap时保证容量是2的次幂，这里的算法和ArrayDeque差不多，如果传入的容量不是2的次幂，则会通过一系列位运算得到大于传入容量的最小2的次幂
//唯一的区别是ArrayDeque传入的容量是2的n次幂，会初始化一个2的n+1次幂的初始容量
//而HashMap如果传入的容量是2的n次幂，会初始化一个2的n次幂的初始容量，只因为开始做了int n = cap - 1;
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;
} //Implements Map.putAll and Map constructor
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//取传入的map大小赋值给s
int s = m.size();
if (s > 0) {
//如果HashMap为空，则计算需要
if (table == null) { // pre-size
//(ft - 1.0F) * loadFactor = s ;
//ft为满足容纳s个元素的最小容量
float ft = ((float)s / loadFactor) + 1.0F;
//如果ft小于2^30则t=ft,否则t=2^30
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
//未被扩容的HashMap的threshold值等于容量
if (t > threshold)
threshold = tableSizeFor(t);
}
//如果HashMap不为空且s大于需要扩容的阈值，则进行扩容
else if (s > threshold)
resize();
//在这之前已经保证HashMap足够容纳传入的map，下面开始遍历传入的map
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
//依次获取map的key和value
K key = e.getKey();
V value = e.getValue();
//通过putVal方法将key-value存入HashMap
putVal(hash(key), key, value, false, evict);
}
}
} //返回HashMap的大小
public int size() {
return size;
} //返回HashMap的是否为空
public boolean isEmpty() {
return size == 0;
} //根据key获取value
public V get(Object key) {
Node<K,V> e;
//根据key和key的hashCode获取Node，若Node为空则返回null，否则根据Node获取value并返回
return (e = getNode(hash(key), key)) == null ? null : e.value;
} //实现了根据key和key的hashCode获取Node
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//将底层数组赋值给tab，底层数组容量赋值给n
if ((tab = table) != null && (n = tab.length) > 0 &&
//tab[(n - 1) & hash]来根据key的hashCode与底层数组的length-1通过与运算获取到对应的存储位置下标
//这也是为什么数组的容量必须是2的次幂的原因，因为2的n次幂的二进制都是 1 + n个0 ，
//length为2的4次幂的二进制为10000，这样length-1的二进制为01111
//这样length-1与任何二进制数通过与运算的结果都会小于等于length-1，大于等于0，也就保证了不会出现数组越界的情况
//并且可以通过key的hashCode与length-1通过与运算获取到对应的存储位置下标，真是一举多得啊！！！
//因为HashMap是数组加链表（或红黑树）存储的，所以这里first取的是链表的头部或者红黑树的根节点
(first = tab[(n - 1) & hash]) != null) {
//检查first节点的hashCode值是否跟key的hashCode相同，如果相同且key与first.key相同，则直接将first节点返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果first节点的next节点不为空，则继续寻找key相同的节点，否则返回null
if ((e = first.next) != null) {
//如果first节点是树形节点，说明是红黑树实现的，则根据红黑树的算法查找节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否则为链表实现，循环根据next指针遍历链表，直到找到key相同的节点并返回，找不到则返回null。
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} //判断HashMap中是否包含key，通过判断getNode是否为空实现
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
} //添加key-value结构数据，若key已存在则替换value
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} //添加元素的实现方法，若onlyIfAbsent为true则不会改变已经存在的value值，若evict为false则说明HashMap处于创建状态
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果HashMap为空则
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;
//如果传入的非空key已存在且与该位置的链表头节点的key相同，则将value替换
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) {
//将链表遍历完后还没遇到相同的key，新建一个节点追加到链表尾节点
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与插入的key相同的节点，则将该节点value值替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//key在map中已存在，替换为新值并将旧值返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//key在map中不存在，插入次数+1
++modCount;
//如果添加后的元素数量大于扩容阈值，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} //核心扩容算法
final Node<K,V>[] resize() {
//把原底层数组备份一份
Node<K,V>[] oldTab = table;
//取原数组的容量大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//取原数组的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
//非HashMap初始化阶段
if (oldCap > 0) {
//如果原数组的容量大于等于2^30,一般只会等于2^30，因为已经是最大容量，不支持再进行扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
//将扩容阈值设为int最大值，这样threshold<oldCap就不会再扩容了
threshold = Integer.MAX_VALUE;
//直接将旧的数组返回
return oldTab;
}
//否则将容量扩容1倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果扩容后的容量小于2^30且扩容前的容量大于等于默认初始容量，则将扩容阈值翻倍
newThr = oldThr << 1; // double threshold
}
//HashMap初始化阶段，并且扩容阈值大于0，则把容量设为与扩容阈值一致，
//除了无参构造，其他三个构造函数都会把threshold设为数组容量的值，然后在存入元素时才实例化一个数组，容量就取threshold的值
else if (oldThr > 0)
newCap = oldThr;
//HashMap初始化阶段，无参构造只会初始化一个loadFactor
else {
//数组容量取默认初始容量16
newCap = DEFAULT_INITIAL_CAPACITY;
//扩容阈值取 16 * 0.75 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//这里针对 oldCap > 0 && oldThr > 0 的情况做的处理，这时候的newCap = oldThr;
//所以需要把threshold 变成 newCap * loadFactor，oldThr仅仅作为临时存储容量的容器
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数组（如果oldCap == 0，这里就是首次创建底层数组的地方）
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;
//将就数组中的数据依次存入e，如果为空则继续取下一个数据
if ((e = oldTab[j]) != null) {
//依次将就数组中存储的数据清空，方便GC回收旧数组
oldTab[j] = null;
//如果当前数据没有next节点，直接把e放入新数组
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 {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历链表
do {
next = e.next;
//将元素的hashCode与原数组容量进行与运算
//结果为0则在新数组中的索引位置不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
//原数组中的链表头
loHead = e;
else
loTail.next = e;
loTail = e;
}
//结果不为0则将在原数组中的索引加上原数组的容量作为新数组中的索引
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;
} //将链表树形化，转为红黑树存储
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果底层数组为空或者数组的长度小于树形化最小容量，则进行resize
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);
}
} //将一个map中的所有元素存入HashMap
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
} //将指定key从HashMap中移除
public V remove(Object key) {
Node<K,V> e;
//若该key存在则将value返回，不存在则返回null
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
} //移除指定节点，若matchValue为true则只有当该节点值与value匹配时才进行移除
//若movable为false，则移除后不改变其他元素的位置
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;
//底层数组不为空且该通过与运算计算的索引位置存在元素，否则直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//该索引位置的链表头节点的key与移除的key匹配，直接取出该节点，待后面判断需不需要删除
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//否则如果链表中不止一个元素则继续，否则返回null
else if ((e = p.next) != null) {
//如果是红黑树节点，则根据红黑树的规则找到key相同的节点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//否则遍历链表寻找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);
}
}
//如果找到了key相同的节点，若matchValue为false则进行移除逻辑
//若matchValue为true则只有当该节点值与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;
//否则将移除节点的next节点链接到移除节点的pre节点
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
} //清空HashMap，遍历底层数组，依次清空
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
} //判断HashMap中是否包含value
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) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
} //返回HashMap中所有key的Set集合
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
} //返回HashMap中所有value的集合
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
} //返回HashMap中所有key-value实体的Set集合
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
最新文章
- 详解AsyncTask的使用
- iOS开发小技巧--自定义带有占位文字的TextView(两种方式)
- [转]Oracle 多行的数据合并
- MySQL分区表例子——List分区
- Info
- ORM框架Hibernate (四) 一对一单向、双向关联映射
- 今天修改 wifi hal 的时候碰见一个问题
- 团队作业8——第二次项目冲刺（Beta阶段）博客汇总
- Qt---Xml文件解析
- JavaSE语法基础(3)---函数、数组
- java9学习之模块化
- linux nginx 如何配置多个端口
- thingsboard改造使用mysql数据库
- [福大软工] Z班 第7次成绩排行榜
- 哈希表（Hash Table）原理及其实现
- oracle数据库迁移相关
- [转]使用Runtime.getRuntime().exec()方法的几个陷阱
- Length of Last Word leetocde java
- spring boot 错误：Check your ViewResolver setup
- 两个List中的补集