数据结构和算法分析：第五章散列

野性酷女 2022-05-15 13:40 230阅读 0赞

散列表的实现常常叫做散列。散列是一种用于以常数平均时间执行插入、删除和查找的技术。

# 5.1 一般想法 #

散列表的数据结构是一个包括一些项(item)的具有固定大小的数组。通常查找是对于项的某个部分（即数据域）来进行的。这部分就叫做**关键字**。

每个关键字被映射到0到TableSize-1这个范围的某个数字中，并且被放到适当的单元中。这个映射函数就叫做散列函数（hash function）。

# 5.2 散列函数 #

*  如果输入的关键字是整形，则一般的合理的方法就是直接返回Key mod TableSize，除非Kye碰巧具有某些不合乎需要的性质。
 *  通常，关键字是字符串。一种选择方法就是把字符串的ASCII 码都加起来。但是这种散列函数，不是一种均匀的分配。
 *  根据Horner法则计算一个（37）的多项式函数。列如计算 hk= k0 + 37\*k1 +sqrt(37)\*k2的方式计算散列值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70]

**解决冲突问题**：如果一个元素被插入时与另一个已经插入的元素散列到同一个位置，那么久产生了一个冲突，这个冲突需要消除。解决冲突的方法主要有两种：一个是分离链接法和开放地址法。

# 5.3 分离链接法 #

分离链接法：其做法就是将散列到同一个值的所有元素保留到一个表中。

为执行一次查找，我们使用散列函数来确定究竟要遍历到哪个链表，然后我们再在被确定的链表中执行一次查找。如果这个元素是一个新元素，那么它将被插入到链表的前端，这不仅方便，还因为常常发生这样的事实：新进插入的元素最有可能不久后就被访问。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 1]

我们定义散列表的**装填因子** λ为散列表中元素的数量对该散列表的大小的比值。链表的平均长度为λ。执行一次查找所需要的时间是计算散列函数值所需要的常数时间加上遍历链表所需要的时间。

分离链接散列法的一般法则是使得表的大小与预料的元素个数大致相当（换句话说λ≈1）。

# 5.4 不用链表的散列表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 2]

## 5.4.1 线性探测表 ##

在线性探测方法中，函数f是i的线性函数，典型情形是f(i)=i。

*  缺点：即使表相对较空，这样占据的单元也会开始形成一些区块，其结果成为**一次聚集**。就是说，散列到区块中的关键字都需要多次试选单元才能解决冲突，安徽关键字被添加到相应的区块中去。

## 5.4.2 平方探测法 ##

平凡探测法是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次的探测方法。流行的选择就是f(i)=sqrt(i)。

*  缺点：对于线性探测，让散列表几乎都填满元素并不是一个好主意，因此标的性能会降低。对于平方探测情况甚至更糟：一旦被填充超过一半，当表大小不是素数的时甚至在表被填充一半之前，就不能保证一次找到空的单元了。这是因为最多有表的一半可以用作解决冲突的备选位置。

## 5.4.3 双散列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 3]

**表的大小最好设置为素数**

# 5.5 再散列 #

对于使用探测散列表来说，如果散列表被填的太满，那么操作的运行时间将开销消耗过大，且插入可能失败。这可能发生有太多的移动和插入混合的场合。此时，一种解决方法就是建立另外一个大约两倍大的表（而且使用一个相关的新散列函数），扫描整个原始表列，计算每一个元素的新的散列值并将其插入到新表中去。

**整个操作就叫做再散列。**

再散列可以用平方探测以多种方式实现。

1.  只要表被填满到一半就再散列。
2.  只有当插入失败的时候再散列。
3.  途中策略：当散列表到达某一个装填因子时进行再散列

# 5.6 标准库中的散列表 #

HashSet和HashMap通常是采用分离链接法实现的。其中HashSet中的项（或者是HashSet中的关键字以及HashMap中的关键字）必须通过equals方法和HashCode方法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70]: /images/20220503/267ca816c8a640d4bff51575529b8def.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 1]: /images/20220503/01e253e776f34d7eb08d4c595c38441d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 2]: /images/20220503/594bdcf152574ab58af171793bec09fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 3]: /images/20220503/e0199cc997b14ff0b4e230339666263e.png