从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（上）-阿里云开发者社区

1. 哈希结构

写OJ时经常看到用到哈希的概念的话，效率就会比较高

1.1 哈希的概念

（以前也学了和哈希相关的概念，绝对映射，相对映射等等）

比如写过的这题：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution {
public:
  int firstUniqChar(string s) {
    int countArr[26] = { 0 };
    for (auto e : s)
    {
      countArr[e-'a']++;//相对映射到数组里++
    }
    for (int i = 0;i < s.size(); i++)
    {
      if (countArr[(s[i]-'a')] == 1)//从原字符串遍历字符的相对映射
      {
        return i;//第一个相对映射为1的就返回其下标
      }
    }
    return -1;//没有出现一次的，输出-1
  }
};

哈希的概念：

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，

因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O（N），

平衡树中为树的高度，即O（logN），搜索的效率取决于搜索过程中元素的比较次数。

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

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立

一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

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

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置

取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，

构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：数据集合 {1，7，6，4，5，9}；设哈希函数为：hash(key) = key % capacity;

capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

1.2 哈希冲突(碰撞)

（上面的问题，插入44的话应该插入到4的位置，但是4的位置被占用了，这就是哈希冲突(碰撞)）

不同的元素，在往哈希表中存储时，通过哈希函数计算出了相同的位置，

即多个元素要插在同一个位置，（不同关键字通过相同哈希哈数计算出相同的哈希地址）

该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢？

1.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

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

其值域必须在0到m - 1之间哈希函数计算出来的地址能均匀分布在整个空间中。

哈希函数应该比较简单，常见哈希函数：

1. 直接定址法(常用)

取关键字的某个线性函数为散列地址：Hash（Key） = A * Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

下面这种不连续的就不适用，因为浪费了很多空间：（存6个数开了1000个空间）

2. 除留余数法(常用)

（上面的问题用除留余数法就能很好解决，把999存到下标9的位置...）

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

按照哈希函数：Hash(key) = key % p(p <= m), 将关键码转换成哈希地址。

3. 平方取中法(了解)

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

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

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这

几部分叠加求和，并按散列表表长，取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法(了解)

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

random为随机数函数。

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

6. 数学分析法(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定

相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只

有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散

列地址。例如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

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

2. 闭散列/开散列解决哈希冲突

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

2.1 闭散列概念和代码

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，

说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

那如何寻找下一个空位置呢？

2.1.1 闭散列线性探测（实现）

比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，哈希地址为4，

因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

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

插入

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

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，

使用线性探测找到下一个空位置，插入新元素

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素

会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。

因此线性探测采用标记的伪删除法来删除一个元素。哈希表每个空间给个标记

EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除，这里用枚举：

enum State { EMPTY, EXIST, DELETE };

扩容

如果哈希表满了呢，此时新插入的数据就没有位置放了，所以必须进行扩容。

哈希表是否扩容是根据负载/载荷因子来决定的，一般情况当负载因子约为0.7~0.8时进行扩容。

负载/载荷因子 = 哈希表中有效数据的个数 / 哈希表的大小。

之所以按照负载因子来扩容，是为了减轻哈希碰撞。

负载因子越小，冲突概率越小，消耗空间越多。
负载因子越大，冲突概率越大，空间利用率越高。

到这先写闭散列线性探测的一部分：

哈希表的底层使用vector，这样可以非常方便的进行扩容，获取哈希表大小等操作。

为了方便实例化vector，使用typedef将存放的数据重命名为Data。

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
enum State
{
  EMPTY,
  EXIST,
  DELETE
};
 
template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY;
};
 
template<class K, class V>
class HashTable
{
public:
  bool Insert(const pair<K, V>& kv)
  {
    //if (Find(kv.first)) // 查找后面写
    //{
    //  return false;
    //}
 
    //if (_table.size() == 0 || 10 * _size / _table.size() >= 7) // 负载因子到了就扩容
    //{
    //  size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
    //  vector<HashData<K, V>> newTables; //创建一个vector，很麻烦，所以用下面的方法(复用了)
    //  newTables.resize(newSize);
    //  
    //  for () // 旧表的数据映射到新表
    //  {
    //  }
    //}
 
    if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 负载因子到了就扩容
    {
      size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      HashTable<K, V> newHT;
      newHT._tables.resize(newSize);
 
      for (const auto& e : _tables) // 旧表的数据映射到新表
      {
        if (e._state == EXIST)
        {
          newHT.Insert(e._kv);
        }
      }
 
      _tables.swap(newHT._tables);
    }
 
    size_t hashi = kv.first % _tables.size(); // 如果是负数会整形提升成无符号再取模，没问题
 
    while (_tables[hashi]._state == EXIST) // 线性探测
    {
      hashi++;
      hashi %= _tables.size();
    }
 
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_size;
 
    return true;
  }
protected:
  //vector<pair<K, V>> _tables; 为了弄标志位，弄成下一行
  vector<HashData<K, V>> _tables;
  size_t _size = 0; // 存储有效数据的个数
};

判断负载因子时，如果用_n/size()的话，得到的值始终都是0，因为是两个整数相除，

所以将使用扩大十倍的方式来判断负载因子大于0.7。

扩容后，并不是简单的将旧表中的数据复制到新表中，

还需要按照新容量得到的映射关系来存放数据。

这里巧妙地进行了复用，创建一个新哈希表，容量设置为原本的二倍，

然后复用Insert将旧表中的数据插入到新表中。

现在动手写查找：

根据key值在哈希表中进行查找时，必须根据哈希函数的映射方式去查找，

这样才能符合哈希表设计的初衷。

拿着key值，按照哈希函数的映射关系直接定位到哈希表的位置，

这一步是让哈希表查找效率是O(1)的关键。

在查找过程中，不仅要比较key值，还要看位置的状态，有可能key值相同，

但是状态是DELETE，此时就不能算作找到，只有key相同，并且状态是TSIST才算是找到。

查找到状态是EMPTY即可，否则就成了遍历了，这样仍然能保证查找的此时是常数次。

删除上面讲了，现在随便把删除写了，然后写个打印函数，HashTable.h：

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
enum State
{
  EMPTY,
  EXIST,
  DELETE
};
 
template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY;
};
 
template<class K, class V>
class HashTable
{
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (Find(kv.first))
    {
      return false;
    }
 
    //if (_table.size() == 0 || 10 * _size / _table.size() >= 7) // 负载因子到了就扩容
    //{
    //  size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
    //  vector<HashData<K, V>> newTables; //创建一个vector，很麻烦，所以用下面的方法(复用了)
    //  newTables.resize(newSize);
    //  
    //  for () // 旧表的数据映射到新表
    //  {
    //  }
    //}
 
    if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 负载因子到了就扩容
    {
      size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      HashTable<K, V> newHT;
      newHT._tables.resize(newSize);
 
      for (const auto& e : _tables) // 旧表的数据映射到新表
      {
        if (e._state == EXIST)
        {
          newHT.Insert(e._kv);
        }
      }
 
      _tables.swap(newHT._tables);
    }
 
    size_t hashi = kv.first % _tables.size(); // 如果是负数会整形提升成无符号再取模，没问题
 
    while (_tables[hashi]._state == EXIST) // 线性探测
    {
      hashi++;
      hashi %= _tables.size();
    }
 
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_size;
 
    return true;
  }
 
  HashData<K, V>* Find(const K& key)
  {
    if (_size == 0)
    {
      return nullptr;
    }
 
    size_t start = 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 (start == hashi) // 防止极端情况：状态全是删除，当hashi回到初始时就跳出
      {
        break;
      }
    }
    return nullptr;
  }
 
  bool Erase(const K& key)
  {
    HashData<K, V>* ret = Find(key);
    if (ret)
    {
      ret->_state = DELETE;
      --_size;
      return true;
    }
    else
    {
      return false;
    }
  }
 
  void Print()
  {
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      if (_tables[i]._state == EXIST)
      {
        printf("[%d:%d] ", i, _tables[i]._kv.first);
      }
      else
      {
        printf("[%d:*] ", i); // 星号代表存储的是无效数据
      }
    }
    cout << endl;
  }
protected:
  //vector<pair<K, V>> _tables; 为了弄标志位，弄成下一行
  vector<HashData<K, V>> _tables;
  size_t _size = 0; // 存储有效数据的个数
};

测试一下，Test.cpp：

#include "HashTable.h"
 
void TestHash1()
{
  int arr[] = { 1, 11, 4, 15, 26, 7, 44 }; // 在加一个数据就会扩容
  HashTable<int, int> ht;
  for (const auto& e : arr)
  {
    ht.Insert(make_pair(e, e));
  }
  ht.Print();
 
  ht.Erase(4);
  cout << ht.Find(44) << endl; // ht.Find(44)->_kv.first就能取出数据
  cout << ht.Find(100) << endl; // 不过要先判断是否为空，否则会崩
  cout << ht.Find(4) << endl;
  ht.Print();
 
  ht.Insert(make_pair(-2, -2));
  ht.Print();
 
  cout << ht.Find(-2) << endl;
}
 
int main()
{
  TestHash1();
 
  return 0;
}

现在还有一个问题，如果想测试下面这组测试用例呢？

void TestHash2()
{
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
 
  HashTable<string, int> countHT;
  for (const auto& str : arr)
  {
    auto ptr = countHT.Find(str);
    if (ptr)
    {
      ptr->_kv.second++;
    }
    else
    {
      countHT.Insert(make_pair(str, 1));
    }
  }
}

上面我们写的插入，都是针对int类型的数据，也只有整形数据才能使用除留余数法，

才能进行取模，从而得到映射关系，如果插入的数据不是整形，

而是string呢？又或者是其他自定义类型呢？此时就使用仿函数的方法，

“将任何类型都转换成整形”，这里的转换只是为了除留余数法能够使用。

负数，浮点数，指针等可以直接强制转，string要怎么转呢？

可以用首字母的ASCII码比较，但是重复的太多，可以把全部字母的ASCII码加起来，

这样重复还是挺多的，比如abcd，bacd，cabd ... ，eat，ate等等，

就有人研究了一种方法：把全部字母的ASCII码乘以一个数再加起来：

template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
  }
};
 
template<>
struct HashFunc<string> // 上面的特化
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (const auto& ch : key)
    {
      val *= 131;
      val += ch;
    }
 
    return val;
  }
};

上面代码是一个仿函数，用来将string转换成int，去进行除留余数法进行映射。

string中的每个字符的ASCII码乘以131，然后再加起来。

相乘的数字可以是31，131，1313等等，这是专门经过研究的，比随意相乘一个数字好很多。

最后再哈希表加上一个模板，再把对key取模的地方改一下，闭散列线性探测代码就出来了：

闭散列线性探测完整代码

HashTable.h：

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
enum State
{
  EMPTY,
  EXIST,
  DELETE
};
 
template<class K, class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY;
};
 
template<class K>
struct HashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
  }
};
 
template<>
struct HashFunc<string> // 上面的特化
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (const auto& ch : key)
    {
      val *= 131;
      val += ch;
    }
 
    return val;
  }
};
 
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (Find(kv.first))
    {
      return false;
    }
 
    //if (_table.size() == 0 || 10 * _size / _table.size() >= 7) // 负载因子到了就扩容
    //{
    //  size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
    //  vector<HashData<K, V>> newTables; //创建一个vector，很麻烦，所以用下面的方法(复用了)
    //  newTables.resize(newSize);
    //  
    //  for () // 旧表的数据映射到新表
    //  {
    //  }
    //}
 
    if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 负载因子到了就扩容
    {
      size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      HashTable<K, V> newHT;
      newHT._tables.resize(newSize);
 
      for (const auto& e : _tables) // 旧表的数据映射到新表
      {
        if (e._state == EXIST)
        {
          newHT.Insert(e._kv);
        }
      }
 
      _tables.swap(newHT._tables);
    }
 
    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size(); // 如果是负数会整形提升成无符号再取模，没问题
 
    while (_tables[hashi]._state == EXIST) // 线性探测
    {
      hashi++;
      hashi %= _tables.size();
    }
 
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_size;
 
    return true;
  }
 
  HashData<K, V>* Find(const K& key)
  {
    if (_size == 0)
    {
      return nullptr;
    }
 
    Hash hs;
    size_t start = hs(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 (start == hashi) // 防止极端情况：状态全是删除，当hashi回到初始时就跳出
      {
        break;
      }
    }
    return nullptr;
  }
 
  bool Erase(const K& key)
  {
    HashData<K, V>* ret = Find(key);
    if (ret)
    {
      ret->_state = DELETE;
      --_size;
      return true;
    }
    else
    {
      return false;
    }
  }
 
  void Print()
  {
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      if (_tables[i]._state == EXIST)
      {
        printf("[%d:%d] ", i, _tables[i]._kv.first);
      }
      else
      {
        printf("[%d:*] ", i); // 星号代表存储的是无效数据
      }
    }
    cout << endl;
  }
protected:
  //vector<pair<K, V>> _tables; 为了弄标志位，弄成下一行
  vector<HashData<K, V>> _tables;
  size_t _size = 0; // 存储有效数据的个数
};

Test.cpp:

#include "HashTable.h"
 
void TestHash1()
{
  int arr[] = { 1, 11, 4, 15, 26, 7, 44 }; // 在加一个数据就会扩容
  HashTable<int, int> ht;
  for (const auto& e : arr)
  {
    ht.Insert(make_pair(e, e));
  }
  ht.Print();
 
  ht.Erase(4);
  cout << ht.Find(44) << endl; // ht.Find(44)->_kv.first就能取出数据
  cout << ht.Find(100) << endl; // 不过要先判断是否为空，否则会崩
  cout << ht.Find(4) << endl;
  ht.Print();
 
  ht.Insert(make_pair(-2, -2));
  ht.Print();
 
  cout << ht.Find(-2) << endl;
}
 
void TestHash2()
{
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
 
  HashTable<string, int> countHT;
  for (const auto& str : arr)
  {
    auto ptr = countHT.Find(str);
    if (ptr)
    {
      ptr->_kv.second++;
    }
    else
    {
      countHT.Insert(make_pair(str, 1));
    }
  }
}
 
int main()
{
  TestHash2();
 
  return 0;
}

平平无奇的仿函数又发挥了关键的作用，监视里看：

从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（中）：https://developer.aliyun.com/article/1522314

从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（上）

1. 哈希结构

1.1 哈希的概念

1.2 哈希冲突(碰撞)

1.3 哈希函数

2. 闭散列/开散列解决哈希冲突

2.1 闭散列概念和代码

2.1.1 闭散列线性探测（实现）

闭散列线性探测完整代码

热门文章

最新文章

相关课程

相关电子书