哈希表与哈希函数

哈希表（Hash Table）

例如开发一个学生管理系统，需要有通过输入学号快速查出对应学生的姓名的功能。这里不必每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以提高查询效率。

学生名单

再例如需要统计一本英文书里某些单词出现的频率，就需要遍历整本书的内容，把这些单词出现的次数记录在内存中。

词频统计

因为这些需要，一个重要的数据结构诞生了，这个数据结构就是哈希表。哈希表也称散列表，哈希表提供了键（key）和值（value）的映射关系，只要给出一个key，就可以高效地查找到它所匹配的value。

在哈希函数分布均匀且装填因子受控时，哈希表查找的期望时间复杂度为$O(1)$；最坏情况下可达$O(n)$。

哈希表的两项基本工作：

1. 计算位置：构造哈希函数确定关键字的存储位置。

2. 解决冲突：应用某种策略解决多个关键字位置相同的问题。

哈希函数（Hash Function）

哈希的基本思想是将键key通过一个确定的函数，计算出对应的函数值作为数据对象的存储地址，这个函数就是哈希函数。

哈希函数

哈希表通常基于数组实现，可是数组只能根据下标来访问，而哈希表的key则可以是整数、字符串等类型。

在不同的语言中，哈希函数的实现方式是不一样的。假设需要存储整型变量，转化为数组的下标就不难实现了。最简单的转化方式就是按照数组长度进行取模运算。

一个好的哈希函数应该考虑两个因素：

1. 计算简单，以便提高转换速度。

2. 关键字对应的地址空间分布均匀，以尽量减少冲突。