哈希 | 系列 1（简介）
原文：https://www.geeksforgeeks.org/hashing-set-1-introduction/
假设我们要设计一个系统来存储使用电话号码键控的员工记录。 我们希望以下查询能够有效执行：
-
插入电话号码和相应的信息。
-
搜索电话号码并获取信息。
-
删除电话号码和相关信息。
我们可以考虑使用以下数据结构来维护有关不同电话号码的信息。
-
电话号码和记录的数组。
-
电话号码和记录的链表。
-
平衡的二分搜索树，其中电话号码为键。
-
直接访问表。
对于数组和链表，我们需要以线性方式搜索，这在实践中可能会很昂贵。 如果我们使用数组并保持数据排序，则可以使用二分搜索在O(Logn)时间中搜索电话号码，但是插入和删除操作的成本很高，因为我们必须保持排序顺序。
使用平衡二叉搜索树，我们得到了适度的搜索，插入和删除时间。 所有这些操作都可以保证在O(Logn)时间内进行。
可以想到的另一种解决方案是使用直接访问表，在其中创建一个大数组，并使用电话号码作为数组中的索引。 如果不存在电话号码，则数组中的条目为NULL，否则数组条目存储指向与电话号码对应的记录的指针。 在时间复杂度方面，这种解决方案是最好的，我们可以在O(1)时间内完成所有操作。 例如，要插入一个电话号码，我们将创建一条记录，其中包含给定电话号码的详细信息，将电话号码用作索引，并将指向创建的记录的指针存储在表中。
此解决方案有许多实际限制。 该解决方案的第一个问题是所需的额外空间很大。 例如，如果电话号码是n位数字，则表的空间为 O(m * 10 ^ n)，其中m是要记录的指针的大小。 另一个问题是编程语言中的整数可能不存储n位数字。
由于上述限制，不能始终使用直接访问表。 散列是几乎可以在所有此类情况下使用的解决方案，与实际上的上述数据结构（如数组，链表，平衡 BST）相比，其性能非常好。 通过散列，我们平均获得O(1)搜索时间（在合理的假设下），在最坏的情况下获得O(n)。
哈希是对直接访问表的改进。 想法是使用哈希函数，该函数将给定的电话号码或任何其他键转换为较小的数字，并使用该较小的数字作为称为哈希表的表的索引。
哈希函数：一种将给定的大电话号码转换为较小的实用整数值的函数。 映射的整数值用作哈希表中的索引。 简而言之，哈希函数将一个大数字或字符串映射为一个小的整数，可用作哈希表中的索引。
良好的哈希函数应具有以下属性：
-
可高效计算。
-
应该均匀分配键（每个表在每个键上的位置可能性均等）
例如，对于电话号码，无效的哈希函数是采用前三位数字。 更好的函数是考虑最后三位数字。 请注意，这可能不是最好的哈希函数。 可能有更好的方法。
哈希表：一个数组，用于存储指向与给定电话号码对应的记录的指针。 如果没有现有电话号码的哈希函数值等于该条目的索引，则哈希表中的条目为NULL。
冲突处理：由于哈希函数使我们获得大键的数量较少，因此两个键可能会产生相同的值。 新插入的键映射到哈希表中已经占用的插槽的情况称为冲突，必须使用某种冲突处理技术来处理。 以下是处理冲突的方法：
-
链接：想法是使哈希表的每个单元指向具有相同哈希函数值的记录的链表。 链接很简单，但是需要在表外增加内存。
-
开放寻址：在打开寻址中，所有元素都存储在哈希表本身中。 每个表条目都包含一条记录或
NULL。 在搜索元素时，我们将逐个检查表插槽，直到找到所需的元素，或者很明显该元素不在表中。
**下一篇文章：
参考：
http://www.cs.princeton.edu/~rs/AlgsDS07/10Hashing.pdf
http://www.martinbroadhurst.com/articles/hash-table.html
如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
