预计2025.03.07，完成优化/完善该内容，敬请期待！！！

（以下为学习过程中的粗略知识点，还未经过优化/完善，后续会变成更有条理的形式！！！）

8.7 哈希表

散列表 填装因子 散列函数 哈希冲突

散列表（Hash Table）、填装因子（Load Factor）、散列函数（Hash Function）是散列技术中几个关键的概念。以下是这些概念的详细解释：

### 散列表（Hash Table）

在哈希表中，寻找一次的时间复杂度为O(1)

散列表是一种数据结构，它将键值映射到存储位置以便快速查找、插入和删除。散列表的核心思想是利用散列函数将键转化为表中的索引。它通常用于实现关联数组和数据库索引。

简单地说，它是通过哈希函数(也叫散列函数) H 和处理冲突的方法(下面会讲)将一组关键字映象到一个有限的连续的地址空间(通常这个地址空间就是数组)，并以关键字在地址集中(也就是数组中)的“像”作为记录在表中的存储位置，这种表便称为哈希表或散列表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址

哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。f（）是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。

### 散列函数（Hash Function）

散列函数是一种将输入数据（通常是字符串或数字）转化为固定大小的整数（散列值）的函数。这些整数用作散列表中的索引。一个好的散列函数应当具备以下特点：

### 填装因子（Load Factor）

填装因子是散列表中已使用的存储位置与总存储位置的比率。它反映了散列表的装填程度，是衡量散列表性能的重要指标。填装因子的计算公式如下：

填装因子的选择对散列表的性能有很大影响：

- **较低的填装因子**：意味着较多的空闲空间，冲突较少，查找、插入和删除操作更快，但浪费空间。

- **较高的填装因子**：意味着空间利用率高，但冲突增加，操作效率下降。

一般情况下，填装因子超过一定值（如0.75）时，需要对散列表进行扩展和重散列（rehashing）。

### 散列冲突（Hash Collision）

当不同的键通过散列函数映射到相同的散列值时，就会发生冲突。就是多个关键码通过散列函数(或者叫哈希函数)映射到了数组的同一个位置上

处理冲突的常用方法有：

### 整体概述

1. **散列表**：一种数据结构，用于快速查找、插入和删除操作。

2. **散列函数**：将输入数据转化为固定大小整数索引的函数，影响散列表的均匀性和性能。

3. **填装因子**：反映散列表装填程度的比率，影响操作性能。

4. **散列冲突**：多个键映射到相同散列值的情况，需要冲突处理方法。

这些概念在一起构成了散列表技术的基础，确保高效的数据存储和检索。

哈希函数的构造

常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

常用的哈希函数构造方法各有其适用的情况：

1. **直接定址法（Direct Addressing Method）**：

- **适用情况**：当关键字的取值范围较小且比较集中时。例如，如果关键字是整数且范围在0到100之间，可以直接使用关键字作为哈希地址。

- **优点**：实现简单，查找速度快。

- **缺点**：当关键字范围大且稀疏时，存储空间浪费严重。

2. **数字分析法（Digit Analysis Method）**：

- **适用情况**：适用于已知所有关键字的情况下，可以事先对关键字进行分析，选取分布均匀的部分来构造哈希函数。

- **优点**：通过对关键字的分析，可以设计出分布较均匀的哈希函数。

- **缺点**：需要事先了解所有关键字，适用范围有限。

3. **平方取中法（Square Mid Method）**：

- **适用情况**：适用于关键字较为随机、无明显规律的情况。将关键字平方后取中间若干位作为哈希地址，能较好地避免冲突。

- **优点**：平方后的中间位通常具有较好的随机性，冲突概率较低。

- **缺点**：计算平方和取中间位的过程稍复杂，计算时间较长。

4. **折叠法（Folding Method）**：

- **适用情况**：适用于关键字位数较多的情况，通过将关键字分段相加或其他方式折叠，来降低关键字的位数。

- **优点**：能较好地利用关键字的全部信息，分布较为均匀。

- **缺点**：需要对关键字进行分段和运算，复杂度较高。

5. **除留余数法（Division Remainder Method）**：

- **适用情况**：广泛适用于各种情况，通过对关键字取余数来得到哈希地址，常用于哈希表的构造。

- **优点**：实现简单，适用范围广泛。

- **缺点**：需要选取一个合适的模数，模数选择不当可能导致冲突较多。

6. **随机数法（Random Number Method）**：

- **适用情况**：适用于关键字随机性较大且无规律可循的情况，通过随机数生成哈希地址。

- **优点**：理论上能较好地避免冲突。

- **缺点**：需要一个好的随机数生成器，且随机数生成的过程较复杂，速度可能较慢。

总结来说，不同的哈希函数构造方法适用于不同的数据特点和需求，选择合适的方法可以提高哈希表的效率和性能。

哈希冲突的解决方法

- **链地址法（Separate Chaining）**：在每个散列表的存储位置维护一个链表，所有散列值相同的元素都存储在这个链表中。

它的优点很显然，一方面，它解决了开放地址法存在的缺点；另一方面，它便于插入和删除。

当然了，它也有缺点，就是它比较占用空间。如果某个位置的链表很长，甚至有可能在链表上挂一个红黑树（就是用红黑树替代链表）。

- **开放地址法（Open Addressing）**：当冲突发生时，通过探测（如线性探测、二次探测或双重散列）寻找下一个空闲位置存储冲突元素。

它的优点：只要哈希表未满，保证能找到一个空单元存放冲突元素；

但是缺点也很明显：

1、可能出现非同义词之间争夺同一个散列地址的现象

2、可能会有很多元素在相邻的哈希地址上“堆积”（也称二次聚集）起来，大大降低了查找效率。

可采用二次探测法，以改善“堆积”问题。

哈希表的性能分析

如果不采用哈希表这样的方法，那么就是在一整个数组中去找。那就是O(N)；好一点对于有序的数组那就是O(logN)（用二分查找）。那么如果采用哈希表，并且采用链地址法去解决哈希冲突，当我将一个元素映射到一个地址身上时，就是经过一个哈希函数的变换，所经过的时间就是O(1)，然后如果没有冲突，那么我就找到了。如果冲突了，那我就从很短的链表中去查。

如果链表很长，那链表就会变成一棵红黑树了。那红黑树我们前面学过查找的最坏情况就是O(logN)。所以说，一个哈希表的查找，最坏最坏最坏的情况，时间复杂度也是O(logN)。

但是我们可以通过调整哈希函数的除数和装填因子（下面会说这个是什么东西），去尽可能避免这种最坏的情况发生。为什么呢？

我们需要考虑，上面那种情况在什么情况下会发生？答：1）数据堆叠严重的情况，就是很多的数据都映射到了数组中的一个位置；2）数据过多的情况。

针对 1），我们会想，是什么原因引起的数据堆叠情况严重呢？如果说数据不多的情况下，数据堆叠严重，那必然是我们的哈希函数的选择不当。那我们就需要通过调整哈希函数，来使得整个哈希表中的数据分布地更加地均匀；从而可以尽量避免最坏情况的发生。

针对2），就是数据很多，而哈希表太小了。这个时候，我们就应当给哈希表（实际上就是那个数组）扩容。其中装填因子指的就是哈希表的实际元素数目(n)/ 哈希表的容量