学习笔记HashMap源码学习-蒲公英云

学习笔记HashMap源码学习

怼烎@ 2021-11-04 23:18 520阅读 0赞

学习笔记

HashMap
HashMap extends AbstractMap
implements Map, Cloneable, Serializable 继承AbstractMap类,实现顶层接口Map接口
int DEFAULT_INITIAL_CAPACITY = 1 << 4 默认容量为16
int MAXIMUM_CAPACITY = 1 << 30 最大容量为1左移30位，即2的30次方
float DEFAULT_LOAD_FACTOR = 0.75f 默认的负载系数为0.75
transient int size 实际存储的元素个数
transient int modCount HashMap被修改的次数
final float loadFactor 负载因子
int threshold HashMap存储临界值
class Node implements Map.Entry
transient Node[] table 底层使用实现了Map.Entry接口的Node存储数据
static final int hash(Object key) 调用hashCode函数计算存储位置
public HashMap(int initialCapacity, float loadFactor) hashMap构造函数，能够指定容量大小和负载因子
HashMap(Map<? extends K, ? extends V> m) hashMap构造函数，并将一个已有的Map作为参数传入，自动将Map中的元素拷贝到当前HashMap中
int size() 获取当前元素个数
boolean isEmpty() 判断HashMap是否为空
V get(Object key) 通过getNode()方法获取key中的元素
boolean containsKey(Object key) 判断键key是否存在
V put(K key, V value)
V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) 调用putVal方法将一个键值对添加到HashMap中去
void putAll(Map<? extends K, ? extends V> m) 将Map m中的所有元素都进行添加
V remove(Object key) 移除键为key的元素
void clear() 清空所有元素
boolean containsValue(Object value) 判断值为value的元素是否存在
Set keySet() 返回所有key集合
Collection values() 返回所有value的集合
V replace(K key, V value) 对键为key的值替换为value
V putIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) 当key不存在是才put
V putIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) 当key存在时才put
V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) 根据已知的key和value重新计算value并进行put
final Node[] resize() { 自动扩容函数
Node[] oldTab = table; 用于存储旧的Node
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之后仍然不是最大，则用目前的容量乘以2
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold 如果存在临界值并且大于0，则直接用临界值代替新的容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults 不存在元素的时候，进行初始化容量与临界值使用默认的16和16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { 新的Node数组临界值初始化
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({“rawtypes”,“unchecked”})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; 旧的Node数组元素清空
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; 如果为最后一个元素
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { 记录下原下标为0的一组node
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { 记录原下标不为0的一组node
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { 如果oldtab［j］开始找到的是原下标为0一组node，放入新table的相同位置
loTail.next = null;
newTab[j] = loHead;该
}
if (hiTail != null) { 如果node的下标不为0，放入新table的对应位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}