哈希表的知识总结

曾经终败给现在 2023-07-25 08:45 56阅读 0赞

**哈希表**

1.特点：

*  内部数据结构是数组
 *  关键字经过变换（Hash函数）得到int类型的值
 *  int类型的值变成一个合法的数组下标
 *  把关键字放入数组的该下标位置

2.当向该结构中：

*  **插入元素**

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

*  **搜索元素**

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若 关键码相等，则搜索成功

该方式即为哈希 ( 散列 ) 方法， **哈希方法中使用的转换函数称为哈希** **(** **散列** **)** **函数，构造出来的结构称为哈希表** **(Hash**  **Table)(** **或者称散列表** **)。**

\*\*\*哈希函数：

![20200413165146549.png][]

![20200413165146525.png][]

3.哈希冲突/哈希碰撞：对于不同的key,经过哈希后，得到的下标是相同的。

哈希的问题都是围绕着哈希冲突展开的：

哈希冲突是越少越好

理论：没可能，数组的容量的n,要放的数据m个

m>>n

引出：

1.如何尽可能减少哈希冲突的次数

2.真的冲突了怎么办

--------------------

1.避免哈希冲突

*  哈希函数的设计（尽可能的让出来的下标符合均匀分布）
 *  负载因子的调节

负载因子 = 哈希表中的数据个数/数组的长度

1.  负载因子越少，冲突率越低
2.  数据个数不能动，所以把数组长度变大
3.  事先规定好一个阈值，来控制resize

2.解决冲突的办法

*  闭散列： 也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。 那如何寻找下一个空位置呢？

1.  线性探测法： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

★ 插入：

通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到 下一个空位置，插入新元素。

插入44：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70][]

★ 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他 元素的搜索。比如删除元素 4 ，如果直接删除掉， 44 查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素。

1.  二次探测法

*  哈希桶（拉链法/开散列） **重点：** 开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70 1][]

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

**开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了（链表）。**

如果冲突还是很高（恶意构造冲突），则用另一个搜索结构解决冲突，Java使用的是红黑树（阈值8）。

3.性能分析

哈希表的插入 / 删除 / 查找时间复杂度是 O(1)；极端情况下，冲突到O(n)。

4.和Java类集的关系

*  HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
 *  java 中使用的是哈希桶方式解决冲突的
 *  java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
 *  java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方 法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值， **必须覆写** **hashCode** **和** **equals** **方** **法** ，而且要做到 equals 相等的对象， hashCode 一定是一致的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70 2][]

[20200413165146549.png]: /images/20230528/58e83ee5013e478780851fe9c9b90624.png
[20200413165146525.png]: /images/20230528/771b31517b954c11b8a17547c5334f12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70]: /images/20230528/0961850b63f448c09690aed1b597584f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70 1]: /images/20230528/7aa2349966604981aa596a7fd12047d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzMwMDUw_size_16_color_FFFFFF_t_70 2]: /images/20230528/a751bc5b33f844729b0b198f821d2108.png