前几天面试被问到了 hashMap 的底层实现原理,虽然之前有所了解,并且对源码大概看了一遍,回答的时候仍然不是太满意,今天写这篇文章来对 HashMap 的源码进行详细的分析。
提到对 HashMap 的操作,无非就是 put、get、初始化等操作。首先来分析下 HashMap 的 put 操作,废话不多讲,先看下 put 的源码:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
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;
}
第一行首先判断存放键值对的 Entry 数组是否为空,为空的话对其进行初始化,对于 inflateTable 方法,我们稍后再对其进行分析,先继续往下看,接下来判断 key 是否为 null,如果为 null 调用 putForNullKey 方法,由此我们可以看出
HashMap 的 key 是允许为 null 的(HashTable 的 key 是不允许为空的,感兴趣的同学可以去看下 HashTable 的实现),在继续往下分析之前先看下这个 putForNullKey:
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
从中可以 HashMap 是将 key 为 null 的元素放到了 Entry 数组的开头,接着遍历检查 key 是否为 null,是则用新值替换掉旧值,否则调用 addEntry 添加到索引为 0 的 Entry 数组中。
下面我们接着看 put 方法,分析 key 不为 null 的处理过程:
下面是获取 key 的 hash 值的过程:
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
上面就是获取的 key 的 hashCode 的方法,其中用到了 hashSeed,那么 hashSeed 是什么?为什么在此处要用到 hashSeed 呢?jdk 的源码注释中是这么解释的:
hashSeed 的是一个与当前 hashhMap 相关联的一个随机值,用于减少 hash 冲突,此算法加入了高位计算,防止低位不变,高位变化产生的 hash 冲突。
接下来就是根据计算出的 hashCode 获取当前 key 在 Entry 数组中的位置:
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
这里我们来解释下为什么要使用取模运算来计算位置,我们都知道 HashMap 是使用数组 + 链表来存储元素,因为链表的查找效率比较低,这样我们肯定希望 HashMap 的数组中的
元素尽量分布的均匀一些,这样就会尽量使数组的每一个位置上只有一个元素,这样我们在查找元素的时候就可以根据 hashCode 计算出的索引直接查找到该元素,而不用遍历
Entry 链表,这样就会使查找效率大大提高。
接下来就是根据计算出的索引位置遍历数组对应位置的 Entry 链表,如果找到就替换掉旧值,否则将其添加到链表中。
至此我们整个 put 方法分析完毕。下一篇我们来分析一下 HashMap 的构造方法,并会讲解 Hash 在什么情况会进行 reHash 操作。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于