一、Hash 冲突可以避免?
Hash 冲突是肯定存在的,但是可以 尽量 避免
散列均匀:元素远小于存储空间的时候,避免冲突,要有好的 hash 算法。
二、散列冲突的解决方法
- 为什么 Java 的 Map 使用了 16 个 Entry?
可以使用 位运算 替换 模运算,速度比较快。
java 中 Hash 冲突(碰撞)的解决方法
链表的方式(1.7)
红黑树(1.8)
线性探测(ThreadLocalMap)
1. 开放定址法(开地址法)
1.1 线性探测法
1.2 二次探测法
散列函数:
其中,m 为散列表长度,m 要求是某个 4k+3 的质数; 为增量序列:
1.3 伪随机探测法
其中,mod 为散列长度, 为伪随机数。
2. 链地址法(拉链法)
基本思想:相同散列地址的记录链成一个单链表。
m 个散列地址就设 m 个单链表,然后用一个数组将 m 个单链表的表头指针存储起来,形成一个动态的结构。
散列表的装填因子 :$$a = \frac{表中填入的数据}{哈希表的长度}$$
散列表技术具有很好的平均性能,优于一些传统的技术;
链地址法优于开地址法;
除留取余法作散列函数优于其它类型函数(取小于等于表长的一个质数)。