一篇文章让你学会什么是哈希（上）-阿里云开发者社区

哈希概念

哈希在C++中有广泛的应用，它是一种用于快速查找和存储数据的数据结构和算法。以下是一些常见的哈希在C++中的应用：

哈希表（Hash Table）：哈希表是一种高效的数据结构，用于存储键值对。在C++中，std::unordered_map 和 std::unordered_set 是标准库提供的哈希表实现。这些容器提供了常数时间复杂度的查找、插入和删除操作，使它们非常适用于快速查找和存储数据。

#include <unordered_map>
#include <unordered_set>
std::unordered_map<std::string, int> hashMap;
hashMap["apple"] = 3;
int value = hashMap["apple"];
std::unordered_set<int> hashSet;
hashSet.insert(42);
bool exists = hashSet.count(42) > 0;

哈希函数（Hash Function）：哈希函数将输入数据映射到一个固定大小的哈希码（哈希值），通常是一个整数。C++标准库提供了多个哈希函数，也允许用户自定义哈希函数。

std::hash<int> intHash;
size_t hashCode = intHash(42);

哈希集合和哈希映射：除了标准库的哈希表，C++还提供了其他第三方库和实现，例如Google的absl::flat_hash_map和absl::flat_hash_set，它们提供了类似的功能但具有更低的内存开销。
哈希集合用于去重：通过将元素插入哈希集合，可以快速去除重复项。

std::unordered_set<int> uniqueValues;
uniqueValues.insert(1);
uniqueValues.insert(2);
uniqueValues.insert(1); // 重复元素将被自动去重

哈希在密码学中的应用：哈希函数在密码学中用于存储和验证密码，常用的密码哈希函数包括SHA-256和bcrypt等。
缓存实现：哈希表可用于实现缓存，通过将键值对存储在哈希表中，可以在常数时间内查找缓存中的数据。
数据唯一性检查：哈希函数和哈希表可用于检查数据的唯一性，确保不会存储重复的数据。

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

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

搜索元素

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

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

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但随之而来的问题是，取余数时如果两个数余数相同该怎么办？

哈希冲突

在散列表（Hash Table）形式的存储中，哈希冲突指的是当不同的键（或数据）经过哈希函数计算后，它们得到了相同的哈希值，并且尝试存储到相同的散列表桶（或哈希表位置）时发生的情况。由于哈希函数将输入数据映射到有限数量的桶中，而输入数据的数量可能远远大于桶的数量，因此哈希冲突是在散列表中常见的问题。

哈希冲突可能会导致以下问题：

数据覆盖：如果两个不同的键映射到相同的桶位置，一个键的数据将覆盖另一个键的数据，导致数据丢失。
查找效率下降：当多个键映射到同一个桶位置时，查找特定键的效率可能会降低，因为必须在该桶内搜索以找到正确的键。

为了解决哈希冲突，散列表通常使用以下方法之一：

链地址法（Chaining）：在这种方法中，每个桶都存储一个链表、数组或其他数据结构，用于存储映射到相同哈希值的多个元素。当哈希冲突发生时，新元素被添加到桶内的链表或数组中，而不会覆盖已存在的元素。
开放寻址法（Open Addressing）：在这种方法中，当发生哈希冲突时，算法会寻找散列表中的下一个可用桶，并将数据插入到该桶中，直到找到一个空闲桶。这个过程通常涉及一系列的探测方法，如线性探测、二次探测等。
好的哈希函数：选择合适的哈希函数可以减少哈希冲突的发生。好的哈希函数应该尽量均匀地将数据映射到桶中，从而降低冲突的概率。

处理哈希冲突是设计和实现散列表时需要考虑的重要问题，不同的应用场景可能需要选择不同的冲突解决策略。合理的冲突处理方法可以提高散列表的性能和效率。

哈希函数

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间

哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

1. 直接定址法

“直接定址法”（Direct Addressing）是一种简单且有效的散列（哈希）技术，通常用于解决键-值对的存储和检索问题。在直接定址法中，每个可能的键都对应着一个桶（或槽位），而这些桶按照键的范围来分配，通常作为一个数组来实现。

这种方法的核心思想是，每个键都被直接映射到一个特定的桶，因此在理想情况下，没有哈希冲突，因为每个键都有唯一的桶索引。

以下是直接定址法的主要特点和限制：

空间复杂度：这种方法需要分配足够大的存储空间以容纳所有可能的键，因此空间复杂度取决于键的范围大小。如果键的范围很大，将导致高内存消耗。
冲突解决：直接定址法通常不需要冲突解决策略，因为每个键都有唯一的桶索引。这使得存储和检索操作都是O(1)的常数时间复杂度，非常高效。
适用性：直接定址法通常在键的范围相对较小且连续的情况下有效。如果键的范围非常大或不连续，这种方法可能不太适用，因为需要分配大量的存储空间。
示例：一个常见的示例是使用直接定址法来实现一个包含整数键的数据结构，例如计数器。如果你有一个计数器，需要跟踪大量整数值的出现次数，你可以使用一个数组，其中数组的索引是整数值，数组的值是该整数值出现的次数。

// 使用直接定址法实现计数器
const int MAX_RANGE = 1000; // 假设整数范围在0到999之间
int counter[MAX_RANGE] = {0};
// 增加某个整数值的计数
int key = 42;
counter[key]++;

总之，直接定址法是一种简单但有效的散列方法，适用于键的范围相对较小且连续的情况。它提供了常数时间复杂度的存储和检索操作，但需要注意键的范围和内存消耗，适合查找比较小且连续的情况。

2. 除留余数法

“除留余数法”（Division Method）是一种常见的散列（哈希）技术，用于将键映射到散列表的桶（槽位）或数组索引中。它的基本思想是，通过对键除以一个合适的数并取余数来计算哈希值，然后将哈希值作为桶的索引。这个余数应该是一个较小的正整数，通常是质数，以确保较好的分布性。

除留余数法的步骤如下：

选择一个合适的除数（通常是质数），记作M。
对键K进行哈希计算：哈希值 = K % M。
使用哈希值作为桶的索引，将数据存储在对应的桶中。

这种方法的优点是简单且容易实现。然而，它也有一些限制和注意事项：

选择合适的除数：选择一个合适的除数M对于除留余数法至关重要。一个好的选择可以确保较好的哈希分布，避免哈希冲突。通常，选择质数可以帮助减少冲突的可能性。
均匀分布：为了获得良好的哈希分布，键应该均匀地分布在整个键空间。如果键分布不均匀，可能会导致某些桶过度拥挤，而其他桶几乎没有数据。
处理负数：除留余数法通常要求键是正整数。如果需要哈希负数，可以考虑采用一些调整方法，如将负数转换为正数。
处理哈希冲突：虽然除留余数法可以减少冲突的可能性，但仍然可能发生冲突。在实际应用中，通常需要使用冲突解决策略，如**链接法（Chaining）或开放寻址法（Open Addressing）**来处理冲突。

3. 平方取中法

“平方取中法”（Mid-Square Method）是一种简单的伪随机数生成方法，通常用于产生伪随机整数序列。它的基本思想是通过对一个整数进行平方运算，然后取中间的数字作为下一个整数，不断迭代生成伪随机数。尽管它简单，但它的质量通常不如更复杂的伪随机数生成算法。

以下是平方取中法的基本步骤：

选择一个初始种子（或起始数值），通常是一个正整数。
将种子平方，并得到一个更大的整数。
从这个平方的结果中，取出中间的若干位数作为下一个伪随机数。
将这个新的伪随机数作为下一轮的种子，然后重复上述步骤

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址

再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

这个方法的核心思想是通过反复平方和取中间数字的操作来生成伪随机数。然而，平方取中法的质量和均匀性通常不如更复杂的伪随机数生成算法，因此它主要用于教学或一些简单的模拟问题。

平方取中法的性能和均匀性取决于初始种子的选择和提取的位数。如果选择的种子不好或者提取的位数不适当，可能会导致周期性或不均匀的伪随机数序列。因此，在实际应用中，通常会使用更先进和更可靠的伪随机数生成器，如线性同余法（Linear Congruential Generator）或梅森旋转法（Mersenne Twister）等，以获得更高质量的伪随机数，平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况 。

4. 折叠法

“折叠法”（Folding Method）是一种散列（哈希）技术，通常用于将大整数或长字符串键映射到较小的哈希值，以便将它们存储在散列表或哈希表中。折叠法的基本思想是将输入键分割成固定长度的部分，然后将这些部分相加或进行其他数学操作以生成哈希值。

以下是折叠法的一般步骤：

选择一个适当的分割大小，通常是一个正整数。这个大小可以根据应用的需要选择，通常是使输入键能够均匀分割的值。
将输入键分割成固定大小的部分（分割块），可以是连续的字符、数字或其他适当的单位。如果输入是数字，通常将它们分割成相等数量的部分。
对这些部分执行数学操作，通常是求和。可以选择不同的数学操作，如加法、位操作等，以根据具体情况来生成哈希值。
最终得到的结果就是哈希值，可以将其用作散列表或哈希表中的桶索引。

以下是一个简单的示例，说明如何使用折叠法将一个整数键映射到哈希值：

假设输入键是1234567890，我们选择分割块大小为3，然后将这个整数分割成 1, 234, 567, 和 890。接下来，我们对这些部分进行求和操作，得到哈希值：1 + 234 + 567 + 890 = 1692。这个哈希值可以用于存储和检索数据。

折叠法的性能和均匀性取决于分割大小和数学操作的选择。如果选择得当，它可以提供较好的哈希分布，但也需要谨慎选择参数以避免潜在的问题，如冲突或不均匀的哈希分布，折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况 。

5. 随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。

通常应用于关键字长度不等时采用此法

6. 数学分析法

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

1. 闭散列

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

1.1 线性探测

比如上面概念中提到的的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

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

插入

通过哈希函数获取待插入元素在哈希表中的位置

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

删除

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

哈希表每个空间给个标记

EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除

enum State{EMPTY, EXIST, DELETE};

线性探测实现

template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY;
};

定义模板结构体 HashData，用于表示哈希表中的数据项。它包含两个主要成员：

_kv：这是一个键值对（pair<K, V>），用于存储键值对应的数据。
_state：这是一个枚举类型State，表示数据项的状态，可能是以下三种之一：

EMPTY：表示槽位为空，即没有数据。
EXIST：表示槽位包含有效的数据。
DELETE：表示槽位包含已删除的数据。

这种结构的设计是为了在哈希表中存储键值对并跟踪每个槽位的状态。状态 _state 的存在使得哈希表可以处理删除操作，而不仅仅是插入和查找。

template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};

定义通用的哈希函数模板 HashFunc，它可以用于任何类型的键 K。该哈希函数的实现非常简单，它将输入键 key 直接转换为 size_t 类型并返回。

具体来说，这个哈希函数的操作步骤是：

接受一个类型为 K 的键 key 作为输入参数。
将键 key 强制类型转换为 size_t，即将不同类型的键映射到一个无符号整数。
返回转换后的 size_t 值作为哈希结果。

需要注意的是，它可能不适用于所有类型的键，特别是对于自定义的数据类型，可能需要更复杂的哈希函数来确保良好的哈希性能和均匀性。

template<>
struct HashFunc<string>//对字符型特化给定值乘以固定质数131降低冲突
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (auto ch : key)
    {
      val *= 131;
      val += ch;
    }
    return val;
  }
};

定义特化版本的哈希函数 HashFunc，用于处理字符串类型（string）的键。这个哈希函数将字符串的每个字符转换成对应的整数值，并将它们组合在一起生成一个哈希值。

以下是这个特化版本的哈希函数的工作原理：

遍历字符串中的每个字符。
对于每个字符，将当前哈希值乘以一个固定的质数（131），然后加上字符的整数值。
重复步骤1和步骤2，直到遍历完整个字符串。
返回最终的哈希值作为字符串的哈希结果。

这个哈希函数的特点是简单而有效，它将字符串中的每个字符都考虑到了哈希值中，并且使用质数131来进行混合（参考STL源码中的实现），以增加哈希的均匀性。这种方法在许多情况下可以产生良好的哈希结果。

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
  vector<HashData<K, V>> _tables;
  size_t _size = 0; // 存储多少个有效数据
};

定义模板类 HashTable，用于实现哈希表数据结构。这个哈希表可以存储键值对，其中键的类型为 K，值的类型为 V，并且可以选择性地指定哈希函数的类型，默认使用 HashFunc<K> 作为哈希函数。

以下是这个哈希表类的主要成员和特点：

_tables：这是一个存储 HashData<K, V> 数据项的向量（vector），表示哈希表的存储空间。每个元素对应哈希表的一个槽位，可以存储一个键值对。哈希表的大小由向量的大小决定。
_size：这是一个记录有效数据项数量的计数器，表示当前哈希表中存储了多少个有效的键值对。在插入和删除操作时，会更新 _size。
默认哈希函数：通过模板参数 Hash，可以选择性地指定自定义的哈希函数。如果未提供自定义的哈希函数类型，将使用默认的 HashFunc<K> 作为哈希函数。这允许在不同类型的键上使用不同的哈希函数。

以下成员函数均为public

插入函数

插入函数需要考虑扩容问题，在散列表存储形式的扩容中，我们需要考虑负载因子问题

散列表的负载因子定义为：α=填入表中的元素个数/散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。

对于开放定址法，负载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

bool Insert(const pair<K, V>& kv)
{
  if (Find(kv.first))
    return false;
  // 负载因子到了就扩容
  if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 扩容
  {
    size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    HashTable<K, V, Hash> newHT;
    newHT._tables.resize(newSize);
    // 旧表的数据映射到新表
    for (auto e : _tables)
    {
      if (e._state == EXIST)
      {
        newHT.Insert(e._kv);
      }
    }
    _tables.swap(newHT._tables);
  }
  Hash hash;
  size_t hashi = hash(kv.first) % _tables.size();
  while (_tables[hashi]._state == EXIST)
  {
    hashi++;
    hashi %= _tables.size();
  }
  _tables[hashi]._kv = kv;
  _tables[hashi]._state = EXIST;
  ++_size;
  return true;
}

Insert 方法的实现，用于向哈希表中插入新的键值对。以下是该方法的主要步骤和逻辑：

首先，通过调用 Find 方法检查是否已经存在具有相同键的数据项。如果存在相同的键，插入失败，直接返回 false。
接下来，检查哈希表的负载因子（load factor）。负载因子是当前存储的有效数据项数量 _size 与哈希表槽位数目 _tables.size() 的比值。如果负载因子超过了指定的阈值（7/10），则表示哈希表负载过重，需要进行扩容。扩容的目的是保持哈希表的性能和均匀性。
如果需要扩容，创建一个新的哈希表 newHT，其大小为当前哈希表的两倍（或初始化大小为10，如果当前哈希表为空）。然后，将旧哈希表 _tables 中的数据映射到新哈希表 newHT 中，通过调用 newHT.Insert(e._kv) 将每个有效数据项插入到新哈希表中。
一旦数据映射完成，通过调用 swap 函数交换旧哈希表 _tables 和新哈希表 newHT，以便使新的哈希表成为当前哈希表。
接下来，计算要插入的键的哈希值。通过调用哈希函数 hash 对键 kv.first 进行哈希运算，然后取模运算来确定要插入的槽位索引 hashi。
使用线性探测法来查找可用的槽位。如果当前槽位 _tables[hashi] 的状态为 EXIST，则继续查找下一个槽位，直到找到一个空槽位。
一旦找到空槽位，将键值对 kv 存储在该槽位，并将状态标记为 EXIST，表示该槽位包含有效数据。然后，递增有效数据项数量 _size。
最后，返回 true 表示插入成功。

查找函数

HashData<K, V>* Find(const K& key)
{
    if (_tables.size() == 0)
    {
        return nullptr;
    }
    Hash hash;
    size_t start = hash(key) % _tables.size();
    size_t hashi = start;
    while (_tables[hashi]._state != EMPTY)
    {
        if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
        {
            return &_tables[hashi];
        }
        hashi++;
        hashi %= _tables.size();
        if (hashi == start)
        {
            break;
        }
    }
    return nullptr;
}

Find 方法的实现，用于查找指定键的数据项并返回对应的 HashData<K, V> 指针。以下是该方法的主要步骤和逻辑：

首先，检查当前哈希表的大小，如果哈希表为空（即 _tables.size() 为0），则无法进行查找，直接返回 nullptr 表示未找到。
创建哈希函数对象 hash，并使用哈希函数计算给定键 key 的哈希值。哈希值通过取模运算 % _tables.size() 得到槽位索引 start，表示开始查找的位置。
初始化一个哈希索引 hashi，开始从槽位 start 开始查找。进入循环。
在循环中，首先检查当前槽位 _tables[hashi] 的状态。如果状态是 EMPTY，表示当前槽位为空，说明没有找到指定键，继续查找下一个槽位。
如果状态不是 EMPTY，则继续检查数据项的状态 _tables[hashi]._state。如果状态是 DELETE，表示当前槽位的数据已删除，也继续查找下一个槽位。
如果状态不是 EMPTY 且不是 DELETE，则表示当前槽位包含有效数据。继续检查数据项的键 _tables[hashi]._kv.first 是否等于目标键 key。如果相等，表示找到了指定的键，返回指向该数据项的指针 &_tables[hashi]。
如果上述条件都不满足，表示当前槽位的数据不匹配目标键，继续查找下一个槽位。通过递增 hashi 并取模 _tables.size() 来实现循环查找。
循环继续，直到再次回到起始位置 start，表明已经遍历了整个哈希表一次，但未找到匹配的键。此时退出循环。
最后，如果整个循环结束而未找到匹配的键，返回 nullptr 表示未找到。

一篇文章让你学会什么是哈希（上）