程序员们在北上广你还能买房嗎？

上一章我们讲了hash表的数据结构，并简单实现了hash表的初始化与删除操作这一章我们会讲解Hash函数和实现算法，并手动实现一个Hash函数

夲教程中我们实现的Hash函数将会实现如下操作：

输入一个字符串，然后返回一个0到m(Hash表的大小)的数字为一组平常的输入返回均匀的bucket索引如果Hash函数不是均匀分布的，就会将多个记录插入到相同的bucket中这就回提高冲突的几率，而这个冲突就会影响到我们的Hash表的效率Hash算法

我们将会設计一个普通的字符串Hash函数，在伪代码中表示如下：

这个Hash函数主要分为两步：

将字符串转为大整型通过取余数mod m将整数的大小减小到固定范圍

变量a是一个素数并且要大于英文字母，我们正在散列ASCII字符串其字母大小为128，因此我们应该选择大于此的素数

char_code这个函数会返回字母對应的整数，使用的是ASCII中的字母

如下使用这个Hash函数：

如果改变a我们会得到不同的结果：

理想中的散列函数返回的结果都是均匀分布的，泹是对于任意一个散列函数，总会有一些输入经过散列后得到相同的值。如果要找到这组输入我们就需要测试大量的输入数据。

因為上面提到的有不好的输入存在意味着所有输入都没有完美的散列函数。所以在设计散列函数时针对预期输入，我们的散列函数需要表现最好

不好的输入也存在安全问题，如果某个恶意用户向哈希表提供了一组冲突密钥那么搜索这些密钥将比正常情况（O(1)）花费更长時间（O(n)）。这可以用作针对以哈希表为基础的系统（例如DNS和某些Web服务）的拒绝服务攻击

上一章：Hash table数据结构下一章：冲突处理

(该文章来自詞汇博客其个人观点，不代表本站的观点或立场如有异议请来信告知)