哈希函数

好的哈希函数应该尽可能让计算的过程变得简单, 应该可以快速计算出结果。

好的哈希函数应该具备哪些优点呢？

快速的计算

哈希表的优势在于效率，所以快速获取对应的 hashCode 非常重要。

均匀的分布

哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候，都会影响效率。

所以优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀分布。

因此，我们需要在使用常量的地方，尽量的使用质数

质数的使用

哈希表的长度

N次幂的底数（之前使用的是27）

为什么使用质数可以是哈希表分布均匀？

• 哈希表的长度使用质数:

这个在链地址法中事实上重要性不是特别明显, 明显的是在开放地址法中的再哈希法中。

• 再哈希法中质数的重要性:

假设表的容量不是质数, 例如: 表长为15(下标值0~14)

有一个特定关键字映射到0, 步长为5。探测序列是多少呢?

0 - 5 - 10 - 0 - 5 - 10, 依次类推, 循环下去。

算法只尝试着三个单元, 如果这三个单元已经有了数据, 那么会一直循环下去, 直到程序崩溃。

如果容量是一个质数, 比如13。探测序列是多少呢?

0 - 5 - 10 - 2 - 7 - 12 - 4 - 9 - 1 - 6 - 11 - 3 一直这样下去。

不仅不会产生循环, 而且可以让数据在哈希表中更加均匀的分布。

哈希函数实现

// 哈希函数
// 1.将字符串转成比较大的数字hashCode
// 2.将大的数字hashCode压缩到数组范围之内
function hashFunc (str, size = 7) {
	// 一个质数
	const PRIME = 31;
	// 1.定义hasCode变量
	let hashCode = 0
	// 2.霍纳算法计算 hashCode 的值
	for (let i = 0; i < str.length; i++) {
		hashCode = PRIME * hashCode + str.charCodeAt(i)
	}
	// 3.取余操作
	let index = hashCode % size
	return index
}

console.log(hashFunc('abc', 7)) // 4
console.log(hashFunc('add', 7)) // 2
console.log(hashFunc('aio', 7)) // 2
console.log(hashFunc('acasd', 7)) // 3