学习笔记HashMap源码学习

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

### 学习笔记 ###

HashMap  
HashMap<K,V> extends AbstractMap<K,V>  
implements Map<K,V>, 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<K,V> implements Map.Entry<K,V>  
transient Node<K,V>\[\] 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<K,V>\[\] resize() \{ 自动扩容函数  
Node<K,V>\[\] 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<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; 旧的Node数组元素清空  
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;  
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;  
\}