代码随想录算法训练营第八天（1）|哈希表理论基础

文档讲解：代码随想录

难度：有一点

哈希表理论基础

哈希表

首先什么是哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。

哈希表是根据关键码的值而直接进行访问的数据结构。

这么官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

​

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希到底有什么用，为什么用了哈希就能快速检索。

有些基础的同学或许能明白，但对于小白可能不知道在讲什么。

首先要知道数据都存储在内存中，假设有几万条商品价格的数据在内存中，我们想从中找到“苹果”价格，如果你事先不知道商品存储规律，就只能一个个去查找，比如第一个是香蕉、第二个是梨，直到第250个才查到苹果。

而如果我们记得每个商品价格存在那个位置就没必要去查找，比如直接去查250号的苹果价格。在计算机中的表现就是知道每条数据对应的内存地址，直接去取相应地址的数据。

现在的需求是如何在计算机中实现告诉我一个商品描述，瞬间得到该商品信息存储在哪个地址。

于是数学家们设计了一套算法，这套算法能够对数据进行一个简单的摘要，可以简单理解为用不同的整数代表不同的数据，这套算法也就是提到的哈希算法。

在存储数据时，我们先对数据的一些描述信息，比如“苹果”，进行哈希运算，得到一个整数，将该整数做些简单处理，转化为一个内存地址，然后将数据存在这个地址对应的存储空间。

下次取数据时，仍然对描述信息做哈希运算，得到对应的存储地址，然后到该地址直接取到完整的数据。这样就不用一个个去遍历查找了，即便上亿条数据，也可以瞬间得到想要的数据。

还有几个点补充。

这种数据储存的地址依赖哈希运算得到的整数，所以存储是不连续的。

编程中提到的字典、map一般就是这种数据结构，而另一种数据结构“数组”则是连续存储的，这两种数据结构各有优缺点各有用途。

还有哈希具体的算法实现有很多，也可以根据不同的需求进行不断完善改进。哈希可以对任意数据运算，包括文本，电影，图片，这个很容易理解，因为计算机中数据本质都是二进制01。
还有个很重要的点，哈希运算得到的值并不一定唯一，也就是不同数据有可能哈希值相同。这个也很容易理解，比如我们生成一个8位的哈希值，只要正数，最多也就127个数，如果对1000个数据进行运算，生成1-127之间的数，那必然会有重复。当然这个例子比较极端，我们取的位数不可能那么小。一般重复率极低，我们也有其他办法应对重复的问题。

改编自B站codeArt的评论

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

​

如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

​

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

​

（数据规模是dataSize， 哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

拉链法的操作过程

1. ‌插入操作‌：当发生哈希冲突时，新的键值会被插入到对应链表的尾部（通常使用头插法），这样可以保证插入操作的平均时间复杂度为O(1)。
2. ‌查询操作‌：查询时需要遍历整个链表，时间复杂度为O(n)，其中n是链表的长度。
3. ‌删除操作‌：删除操作需要遍历链表找到待删除节点，然后将其从链表中移除。由于链表中的元素是通过指针连接的，删除操作的时间复杂度也为O(1)。

拉链法的优缺点

• ‌优点‌：
  • 处理冲突简单，无堆积现象，非同义词不会发生冲突。
  • 插入、查询和删除操作的时间复杂度均为O(1)。
• ‌缺点‌：
  • 查询操作需要遍历链表，效率较低。
  • 空间开销较大，因为每个哈希值对应一个链表。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

​

线性探测法的工作原理

当插入一个新元素时，如果计算出的哈希地址已经被占用，线性探测法会检查哈希表中的下一个地址。如果下一个地址也被占用，就继续向下检查，直到找到一个空的地址为止。这个过程可以用以下伪代码表示：

def linear_probing(hash_table, key, value):
    index = hash_function(key)
    while hash_table[index] is not None:
        index = (index + 1) % size_of_hash_table
    hash_table[index] = value

线性探测法的优缺点

线性探测法的优点在于其实现简单，且在哈希表的负载因子较低时，即表中空位较多时，这种方法可以快速地找到空位。

然而，当哈希表中的空位不多时，线性探测法可能需要检查多个位置才能找到空位，这会增加插入和查找的时间复杂度。此外，线性探测法还可能导致聚集现象，即连续的位置被占用，从而影响性能。

线性探测法的代码实现

在实际代码实现中，通常会定义一个哈希表类，其中包含插入、查找和删除等方法。以下是使用线性探测法处理哈希冲突的哈希表类的一个简单示例：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
        index = (index + 1) % self.size
        self.table[index] = value

    def hash_function(self, key):
        return key % self.size

在这个示例中，hash_function 方法根据键值计算哈希地址，insert 方法使用线性探测法来解决冲突。如果哈希表的大小是一个质数，这可以帮助减少冲突的可能性。

结论

线性探测法是一种有效的哈希冲突解决策略，尤其适用于哈希表负载因子较低的情况。然而，为了保持高效的性能，需要合理地选择哈希表的大小，并且在哈希表变得过于拥挤时进行扩容。在实际应用中，还需要考虑到聚集问题，并采取措施来避免它。

为了解决聚集现象，可以采用其他解决冲突的方法，如平方探测法或链地址法。平方探测法通过计算冲突位置的平方来寻找下一个位置，从而跳出聚集区域。链地址法则将所有关键字映射到同一个位置上，通过链表来存储发生冲突的元素‌........

其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。

虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std::map也是一样的道理。

这里在说一下，一些C++的经典书籍上 例如STL源码剖析，说到了hash_set hash_map，这个与unordered_set，unordered_map又有什么关系呢？

实际上功能都是一样一样的， 但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。

​

总结

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！