第6篇 C++ 哈希表-概念篇
场景导入
假设我们要设计一个交易系统来存储使用订单号/联系电话作为索引找到对应的交易信息。 我们希望以下查询能够有效执行：
- 插入电话号码/订单号和相应的信息。
- 通过电话号码/订单号并获取相关信息。
- 删除电话号码/订单号和相关信息。
注意，我这里要说的主题跟数据库访问无关，上面的应用场景是从数据库访问后缓存在客户端内存中的数据条目，而这些数据条目我们希望通过电话号码/订单号等和交易记录的其他信息建立一个映射表。因此，可以想得到是使用以下数据结构来维护有关不同电话号码的信息。
- 电话号码/订单号和记录的数组(或链表)
- 平衡的二进制搜索树，其中电话号码/订单号为key。
- 直接访问表。
对于数组和链表，我们知道线性表搜索，这在实践中可能时间开销为O(n)。 如果我们使用数组并保持数据排序，则可以使用Binary Search在O(log n)时间中搜索电话号码，但是由于必须维护排序顺序，因此插入和删除操作的成本很高。
使用平衡的二叉搜索树，我们得到适度的搜索，插入和删除时间。 所有这些操作都可以保证在O（Logn）时间中进行。
可以想到的另一种解决方案是使用直接访问表，其中我们创建了一个大数组，并使用电话号码作为数组中的索引。如果电话号码不存在，则数组中的条目为NULL，否则数组条目存储指向对应于该电话号码的记录的指针。在时间复杂度方面，这个方案是所有方案中最好的，我们可以在O(1)时间内完成所有的运算。例如，要插入电话号码，我们创建一条包含给定电话号码详细信息的记录，使用电话号码作为索引，并将指向创建的记录的指针存储在表中。
这个解决方案有很多实际的局限性。此解决方案的第一个问题是所需的额外空间非常巨大。例如，如果电话号码是n位数字，我们需要O(m*10n)空间来存放一个表，其中m是要记录的指针的大小。另一个问题是编程语言中的整数可能不存储n位。
散列(Hash)是对直接访问表的改进。其思想是使用散列函数，该散列函数将给定的电话号码或任何其他关键字转换为较小的数字，并将该较小的数字用作称为散列表的表中的索引。
Hash函数:将给定的大电话号码转换为小的实用整数值的函数。映射的整数值用作哈希表中的索引。简而言之，哈希函数将一个大数字或字符串映射到一个可用作哈希表中索引的小整数。
一个好的散列函数应该具有以下属性：
- 可有效计算。
- 应均匀分布键(每个密钥的每个表位置的可能性相等)
例如，对于电话号码，错误的散列函数是取前三位数。较好的函数被认为是最后三位数。请注意，这可能不是最好的散列函数。也许还有更好的办法。
存储指向与给定电话号码对应的记录的指针的数组。如果没有现有电话号码具有等于该条目的索引的散列函数值，则哈希表中的条目为零
什么是冲突(Collision)？
由于哈希函数会为一个较大的整数或字符串的键提供一个较小的数字，因此两个键可能会产生相同的值。 新插入的键映射到哈希表中已经占用的插槽的情况称为冲突，必须使用某种冲突处理技术来处理。
在一个大型的表中key冲突的可能性有多大？我们这里举例一个非常典型的例子，例如我们尝试使用生日作为映射表的键，那么在生日悖论(Birthday Paradox)中，23个人，两个人生日相同的概率就高达50%。
冲突处理：由于散列函数为我们提供了一个大键的小数字，因此有可能两个键产生相同的值。新插入的键映射到哈希表中已经占用的槽的情况称为冲突，必须使用某种冲突处理技术来处理。以下是处理冲突的方法：
- 分离链接：其想法是使哈希表的每个单元格指向具有相同哈希函数值的记录的链接列表。链接很简单，但需要表外的额外内存。
- 开放寻址：在开放寻址中，所有元素都存储在哈希表本身中。每个表条目要么包含一条记录，要么包含零。在搜索元素时，我们逐个检查表槽，直到找到所需的元素或明确该元素不在表中。
