开放定址法是哈希表冲突解决的一种方法,该方法通过探测未使用的数组槽来解决散列冲突。常见的探测方法包括:
- 线性探测
探测的间隔是固定的,通常为 1。 - 平方探测
探测的间隔呈二次方增加。 - 两次哈希
探测的间隔依然是固定的,只是间隔由另一个哈希函数计算得出。
这些方法的主要区别在于线性探测具有最好的缓存性能,但是对聚集敏感,虽然两次哈希的缓存性能很差,但是几乎不存在聚集的问题,平方探测介于两者之间。相比其他的探测方法,两次哈希需要更多的计算。
对开放定址法性能起到关键影响的是负载因子,随着负载因子向 100% 增加,查询或写入数据时探测的数量急剧增加,一旦哈希表变满,探测算法甚至可能无法终止。即使具有良好的哈希函数,负载因子也通常被限制在 80%。即使在非常低的负载因子下,使用最简单的线性探测,较差的哈希函数也会导致大量的聚集,表现出较差的性能。通常,大多数开放定址法的负载因子被设置为 50%,而单独链表法可以高达 100%。
在 JDK 中,IdentityHashMap
与 ThreadLocal.ThreadLocalMap
就使用了线性探测,它们采用的负载因子均为 2/3
,即没有像 HashMap
与 Hashtable
一样使用 0.75
作为负载因子。
根据 Linear probing - Wikipedia 中的解释,线性探测中一次碰撞存在导致附近更多碰撞的趋势,当负载因子较高时性能下降较快。
Linear probing provides good locality of reference, which causes it to require few uncached memory accesses per operation. Because of this, for low to moderate load factors, it can provide very high performance. However, compared to some other open addressing strategies, its performance degrades more quickly at high load factors because of primary clustering, a tendency for one collision to cause more nearby collisions.
在 Hash table - Wikipedia 还给出了一张负载因子与缓存未命中的关联图:
根据这张图即容易理解 JDK 里面不同 Map
实现中默认负载因子为何不同了。
Reference
Open addressing - Wikipedia
Why does IdentityHashMap use 2/3 as the load factor instead of 0.75? - Stack Overflow
HashMap
IdentityHashMap