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

本文涉及的产品
函数计算FC,每月免费额度15元,12个月
简介: 从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

目录
相关文章
|
2天前
|
存储 Serverless C++
【C++】手撕哈希表的闭散列和开散列
【C++】手撕哈希表的闭散列和开散列
11 1
|
22天前
|
存储 Linux C语言
c++进阶篇——初窥多线程(二) 基于C语言实现的多线程编写
本文介绍了C++中使用C语言的pthread库实现多线程编程。`pthread_create`用于创建新线程,`pthread_self`返回当前线程ID。示例展示了如何创建线程并打印线程ID,强调了线程同步的重要性,如使用`sleep`防止主线程提前结束导致子线程未执行完。`pthread_exit`用于线程退出,`pthread_join`用来等待并回收子线程,`pthread_detach`则分离线程。文中还提到了线程取消功能,通过`pthread_cancel`实现。这些基本操作是理解和使用C/C++多线程的关键。
|
20天前
|
C语言 图形学 C++
|
2天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
9 0
|
1月前
|
C语言 C++ 编译器
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
|
17天前
|
自然语言处理 C语言 C++
程序与技术分享:C++写一个简单的解析器(分析C语言)
程序与技术分享:C++写一个简单的解析器(分析C语言)
|
20天前
|
程序员 C语言 C++
【C语言】:柔性数组和C/C++中程序内存区域划分
【C语言】:柔性数组和C/C++中程序内存区域划分
14 0
|
1月前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
2天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
22 10
|
7天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
39 9