上一章，我们讲了hash表的数据结构，并简单实现了hash表的初始化与删除操作，这一章我们会讲解Hash函数和实现算法，并手动实现一个Hash函数。Hash函数本教程中我们实现的Hash函数将会实现如下操作：输入一个字符串，然后返回一个0到m(Hash表的大小)的数字为一组平常的输入返回均匀的bucket索引。如果Hash函数不是均匀分布的，就会将多个记录插入到相同的bucket中，这就回提高冲突的几率，而这个冲突就会影响到我们的Hash表的效率。Hash算法我们将会设计一个普通的字符串Hash函数，在伪代码中表示如下：function hash(string, a, num_buckets): hash = 0 string_len = length(string) for i = 0, 1, …, string_len: hash += (a ** (string_len - (i+1))) * char_code(string[i]) hash = hash % num_buckets return hash这个Hash函数主要分为两步：将字符串转为大整型通过取余数mod m将整数的大小减小到固定范围变量a是一个素数，并且要大于英文字母，我们正在散列ASCII字符串，其字母大小为128，因此我们应该选择大于此的素数。char_code这个函数会返回字母对应的整数，使用的是ASCII中的字母。如下使用这个Hash函数：hash(“cat”, 151, 53)// 函数拆解hash = (1512 * 99 + 1511 * 97 + 151**0 * 116) % 53hash = (2257299 + 14647 + 116) % 53hash = (2272062) % 53hash = 5如果改变a我们会得到不同的结果：hash(“cat”, 163, 53) = 3代码实现// hash_table.cstatic int ht_hash(const char* s, const int a, const int m) { long hash = 0; const int len_s = strlen(s); for (int i = 0; i < len_s; i++) { hash += (long)pow(a, len_s - (i+1)) * s[i]; hash = hash % m; } return (int)hash;}什么是冲突？理想中的散列函数返回的结果都是均匀分布的，但是，对于任意一个散列函数，总会有一些输入经过散列后，得到相同的值。如果要找到这组输入，我们就需要测试大量的输入数据。因为上面提到的有不好的输入存在，意味着所有输入都没有完美的散列函数。所以在设计散列函数时，针对预期输入，我们的散列函数需要表现最好。不好的输入也存在安全问题，如果某个恶意用户向哈希表提供了一组冲突密钥，那么搜索这些密钥将比正常情况（O(1)）花费更长时间（O(n)）。这可以用作针对以哈希表为基础的系统（例如DNS和某些Web服务）的拒绝服务攻击。上一章：Hash table数据结构下一章：冲突处理