ch6-Hash

哈希

哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合是集合数据结构的实现之一，用于存储非重覆值，比如python的set。
• 哈希映射是映射数据结构的实现之一，用于存储key-value键值对，比如python的dict。

哈希表的原理

哈希表的关键思想是使用哈希函数将键映射到存储桶，更确切说，

1. 当我们插入一个新的建时，哈希函数将决定该键该分配到哪个桶中，并将该键存储到相应桶中。
2. 当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

• 设计哈希集合
• 设计哈希映射

哈希函数

哈希函数是哈希表中最重要的组件，该哈希表用于键值映射到特定的桶中。例如使用y = x % 5 作为散列函数，其中x是键值，y是分配的桶的索引。

理想情况下，完美的哈希函数将是键和桶之间的一对一映射。然而，在大多数情况下哈希函数并不完美，他需要在桶的数量和桶的容量之间进行权衡。

冲突解决

大多数情况下，冲突是不可避免的。例如，在我们之前的哈希函数(y= x % 5)中，2和7都分配给了桶2，这是一个冲突。

冲突解决算法应该解决一下几个问题：

1. 如何组织在同一个桶中的值？
2. 如果为同一个桶分配了太多的值，该怎么办？
3. 如何在特定的桶中搜索目标值？

根据哈希函数，这些问题与桶的容量和可能映射到同一个桶的键的数目有关。

让我们假设存储最大键数的桶有N个键。

通常，如果N是常数且很小，我们可以简单的使用一个数组将键存储到同一个桶中。如果N是可变的或很大，我们可能需要使用高度平衡的二叉数来代替。

复杂度分析

如果总共有M个键，那么在使用哈希表时，可以很容易地达到O(M)的空间复杂度。

但是对于时间复杂度和设计有大关系。

一般情况下在每个桶中使用数组来将值存储到同一个桶中，理想情况下，桶的大小足够小时，可以看做是一个常数。插入和搜索的时间复杂度都是O(1)。

但在最坏情况下，桶的大小最大值将为N，插入时间复杂度为O(1)，搜索为O(N)。

内置哈希表的原理

内置哈希表的典型设计是：

1. 键值可以是任何可哈希化的类型，并且属于可哈希类型的值将具有哈希码。此哈希码将用于映射函数以获取存储区索引。
2. 每个桶包含一个数组，用于在初始化时将所有值存储在同一个桶中。
3. 如果在同一个桶中存有太多的值，这些值将被保留在一个高度平衡的二叉搜索树中。

插入和搜索的平均之间复杂度仍为O(1)，最坏情况下插入和搜索的时间复杂度是O(logN)，使用高度平衡的BST，这是在插入和搜索之间的一种平衡。