Hashmap原理总结2
问题
- 知道HashMap的put元素的过程是什么样吗
- 知道get过程是是什么样吗
建议读源码进行一次分析，再查看列点方式，进行回顾总结源码流程内容进行回顾，加深记忆！！
以加注释的形式进行一次分析
Put过程源码分析
JDK1.8源码分析
/**
* 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为空或还没有元素时，则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 获取当前key 对应的 i，判断桶中是否有节点
// 注：index 为n-1 & hash 得到
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果没有，则新建一个Node节点放入桶中
tab[i] = newNode(hash, key, value, null);
else { // 出现hash碰撞
Node<K,V> e; K k;
// 若hash相同、key引用相同或key 值相同，则先记录至e
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;
}
// 判断新节点是否是链表上已经有的，若是，e已记录节点信息
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 记录到相同位置的节点，进行value覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 当结点数+1大于threshold时，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
注：JDK1.8采用链表尾插法，JDK1.8之前采用头插法
PUT过程再次总结
以列点方式进行二次总结
1.计算关于key的hashcode值
2.如果散列表为空，则调用resize()进行扩容
3.检查是否发生碰撞
3.1未发生碰撞，则直接将节点加入桶中
3.2若发生碰撞
- 首节点若key地址相同或者equals后内容相同，记录e
- 为红黑树类型，采用红黑树类型添加node方法
- 为链表类型，遍历链表
- 遍历到链表尾节点，进行尾插法，并进行判断节点数是否超过树阈值，若超过则转为红黑树
- 若key地址相同或者equals后内容相同，记录e
4.进行e覆盖原value
5.判断加入新节点后是否大于threshold即（capacity * load_factor ），若超过则进行扩容操作
Get过程源码分析
// hash(key)方法实现根据code求hashcode
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断table是否为空
// 根据n-1 & hash 求出index
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 若首节点table[i] == key 则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若该桶中存在多节点
if ((e = first.next) != null) {
// 为红黑树则使用树的遍历方式
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 为链表，则进行遍历，通过判断hash值来区分不同节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Get过程再次总结
以列点方式进行二次总结
1.根据key值得到hash值
2.根据hash得到key所对应的下标
3.判断table是否为空
3.1若为空，则返回null
3.2若不为空
- 首节点相同，返回node
- 为红黑树类型，采用树查找便利的方式
- 为链表类型，进行循环遍历，找到返回node，找不到返回null
经个人总结归纳
参考文章
1.https://www.bilibili.com/read/cv5517205/
2.https://zhuanlan.zhihu.com/p/353846426
3.https://blog.csdn.net/u011277123/article/details/80467673（put详解）
4.https://blog.csdn.net/m0_37550986/article/details/115833221（get详解）
|