作者:好学的程序员 | 来源:互联网 | 2023-01-11 14:46
HashMap的解析HashMap源码的脑图:HashMap的基本数据结构:HashMap的底层是一个数组,数组的每一项又是一个链表基本的数据操作:put方法
HashMap的解析
HashMap源码的脑图:
HashMap的基本数据结构:
HashMap的底层是一个数组,数组的每一项又是一个链表
基本的数据操作:put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab存放hashmap的基本数据结构,p存放键值,n存放当前数据个数,i当前位数
Node[] tab; Node p; int n, i;
//如果table是null,创建这个数组,同时将基本的数据结构赋值给tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据hash算法求取位置,将相应位置的node赋值到p,判断是否为null1
if ((p = tab[i = (n - 1) & hash]) == null)
//如果是null的话,新建这个位置的node
tab[i] = newNode(hash, key, value, null);
else {
//如果当前位置有值的话,开始进行下面的步骤
Node e; K k;
//如果当前key相等,怎将数据替换掉
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//将老数据换成新数据
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
其中key的hash算法如下:
求取key的hashcode,然后求取hash值的右移16,将hash与右移之后的值求取异或,从而将高位的特征保留下来,这个叫做扰动函数
怎样根据key的hash值求取它在数组中的位置呢?
n-1 = 16 - 1 =15= 1111,这样hash的高位信息就丢失了,主要反映了hash最低四位的特征,这样可以保证在0-15这个16个数字均匀分布
基本的数据获取方法:
hash函数
这里说明hashMap的key可以为null
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//首先检查tab是否为null,将数组赋值为tab,将数组的长度赋值给n,如果hash位置的第一个值不等于null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一个hash==hash,同时key.equals(key)
if (first.hash == hash && // always check first node
//判断key相等的条件:hash相等,并且符合equals
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不相等的话,如果first是treeNode属性
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)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;
}