大家好,又见面了,我是你们的朋友全栈君。
看了看HashMap的源码,有些心得先写下,以便以后查看,不然又要忘了,但不知道对不对,希望没误人子弟吧。
主要是解释下HashMap底层实现与如何解决hash碰撞的。
HashMap底层是table数组,Entry是HashMap的内部类。
可以看到HashMap的key与value实际是保存在Entry中的,next是下一个Entry节点。
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key);
//计算通过key的hash值与table长度来计算位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判断key是否重复,如果重复则替换
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断是否容量超过极限
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
这里实际才是将key与value保存了,先获取之前的位于bucketIndex位置的的Entry元素e(如果不存在则为null,如果存在则代表有重复的hash值,我自己理解为这就是HashMap的hash碰撞),在新建一个Entry元素,将之前的Entry元素e放入新建的Entry元素内部,新建的Entry保存在table中。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
0,1,2,3位置都有Entry元素,但1,3有两个Entry元素,(21,21)与(13,13)实际保存在13与8元素next属性上。如果还有重复的hash(key)值那就继续保存,这就是HashMap对hash碰撞的处理方式,拉链法。
写的不好请见谅,如果哪里说的不对,请讲出来,小菜鸟一个。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150598.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...