HashMap的hash碰撞

大家好，又见面了，我是你们的朋友全栈君。

看了看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碰撞的处理方式，拉链法。

写的不好请见谅，如果哪里说的不对，请讲出来，小菜鸟一个。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/150598.html原文链接：https://javaforall.cn