• 售前

  • 售后

热门帖子
入门百科

哈希表、哈希桶的实现

[复制链接]
一品菊花茶酪 显示全部楼层 发表于 2022-1-14 10:47:10 |阅读模式 打印 上一主题 下一主题
文章目录



哈希概念

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数,因此顺序结构中查找的时间复杂度为                              O                      (                      N                      )                          O(N)               O(N),平衡树中查找的时间复杂度为树的高度                              O                      (                      l                      o                      g                      N                      )                          O(logN)               O(logN)。
而最理想的搜索方法是,可以不经过任何比较,一次直接从表中得到要搜索的元素,即查找的时间复杂度为                              O                      (                      1                      )                          O(1)               O(1)。
如果构造一种存储结构,该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时就能通过该函数很快找到该元素。
向该结构当中插入和搜索元素的过程如下:


  • 插入元素: 根据待插入元素的关键码,用此函数计算出该元素的存储位置,并将元素存放到此位置。
  • 搜索元素: 对元素的关键码进行同样的计算,把求得的函数值当作元素的存储位置,在结构中按此位置取元素进行比较,若关键码相等,则搜索成功。
该方式即为哈希(散列)方法, 哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(散列表)。
   例如,集合{1, 7, 6, 4, 5, 9}
哈希函数设置为:                                   h                         a                         s                         h                         (                         k                         e                         y                         )                         =                         k                         e                         y                         %                         c                         a                         p                         a                         c                         i                         t                         y                              hash(key)=key\%capacity                  hash(key)=key%capacity,其中capacity为存储元素底层空间的总大小。
若我们将该集合存储在capacity为10的哈希表中,则各元素存储位置对应如下:

用该方法进行存储,在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素,而不必进行多次关键码的比较,因此搜索的速度比较快。
  哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。
   例如,在上述例子中,再将元素11插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同,都是下标为1的位置
                                    h                         a                         s                         h                         (                         11                         )                         =                         11                         %                         10                         =                         1                              hash(11)=11\%10=1                  hash(11)=11%10=1。

  哈希函数

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

  • 哈希函数的定义域必须包括需要存储的全部关键码,且如果散列表允许有m个地址,其值域必须在0到m-1之间。
  • 哈希函数计算出来的地址能均匀分布在整个空间中。
  • 哈希函数应该比较简单。
  常见的哈希函数如下:
一、直接定址法(常用)
取关键字的某个线性函数为哈希地址:                              H                      a                      s                      h                      (                      K                      e                      y                      )                      =                      A                      ∗                      K                      e                      y                      +                      B                          Hash(Key)=A*Key+B               Hash(Key)=A∗Key+B。
优点:每个值都有一个唯一位置,效率很高,每个都是一次就能找到。
缺点:使用场景比较局限,通常要求数据是整数,范围比较集中。
使用场景:适用于整数,且数据范围比较集中的情况。

二、除留余数法(常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:                              H                      a                      s                      h                      (                      K                      e                      y                      )                      =                      K                      e                      y                      %                      p                      (                      p                      <                      =                      m                      )                          Hash(Key)=Key\%p(p_state = DELETE;                //3、哈希表中的有效元素个数减一                _n--;                return true;        }        return false;}[/code] 哈希表的开散列实现(哈希桶)

哈希表的结构

在开散列的哈希表中,哈希表的每个位置存储的实际上是某个单链表的头结点,即每个哈希桶中存储的数据实际上是一个结点类型,该结点类型除了存储所给数据之外,还需要存储一个结点指针用于指向下一个结点。
  1. //枚举:标识每个位置的状态
  2. enum State
  3. {
  4.         EMPTY,
  5.         EXIST,
  6.         DELETE
  7. };
复制代码
为了让代码看起来更加清晰,在实现哈希表时,我们最好将结点的类型进行typedef。
  1. //哈希表每个位置存储的结构
  2. template<class K, class V>
  3. struct HashData
  4. {
  5.         pair<K, V> _kv;
  6.         State _state = EMPTY; //状态
  7. };
复制代码
与闭散列的哈希表不同的是,在实现开散列的哈希表时,我们不用为哈希表中的每个位置设置一个状态字段,因为在开散列的哈希表中,我们将哈希地址相同的元素都放到了同一个哈希桶中,并不需要经过探测寻找所谓的“下一个位置”。
哈希表的插入

向哈希表中插入数据的步骤如下:

  • 查看哈希表中是否存在该键值的键值对,若已存在则插入失败。
  • 判断是否需要调整哈希表的大小,若哈希表的大小为0,或负载因子过大都需要对哈希表的大小进行调整。
  • 将键值对插入哈希表。
  • 哈希表中的有效元素个数加一。
其中,哈希表的调整方式如下:


  • 若哈希表的大小为0,则将哈希表的初始大小设置为10。
  • 若哈希表的负载因子已经等于1了,则先创建一个新的哈希表,该哈希表的大小为原哈希表的两倍,之后遍历原哈希表,将原哈希表中的数据插入到新哈希表,最后将原哈希表与新哈希表交换即可。
   重点: 在将原哈希表的数据插入到新哈希表的过程中,不要通过复用插入函数将原哈希表中的数据插入到新哈希表,因为在这个过程中我们需要创建相同数据的结点插入到新哈希表,在插入完毕后还需要将原哈希表中的结点进行释放,多此一举。
  实际上,我们只需要遍历原哈希表的每个哈希桶,通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可,不用进行结点的创建与释放。

说明一下: 下面代码中为了降低时间复杂度,在增容时取结点都是从单链表的表头开始向后依次取的,在插入结点时也是直接将结点头插到对应单链表,作图时不方便头取头插,于是图中都是尾取尾插。
将键值对插入哈希表的具体步骤如下:

  • 通过哈希函数计算出对应的哈希地址。
  • 若产生哈希冲突,则直接将该结点头插到对应单链表即可。
  1. //哈希表
  2. template<class K, class V>
  3. class HashTable
  4. {
  5. public:
  6.         //...
  7. private:
  8.         vector<HashData<K, V>> _table; //哈希表
  9.         size_t _n = 0; //哈希表中的有效元素个数
  10. };
复制代码
哈希表的查找

在哈希表中查找数据的步骤如下:

  • 先判断哈希表的大小是否为0,若为0则查找失败。
  • 通过哈希函数计算出对应的哈希地址。
  • 通过哈希地址找到对应的哈希桶中的单链表,遍历单链表进行查找即可。
  1. //插入函数
  2. bool Insert(const pair<K, V>& kv)
  3. {
  4.         //1、查看哈希表中是否存在该键值的键值对
  5.         HashData<K, V>* ret = Find(kv.first);
  6.         if (ret) //哈希表中已经存在该键值的键值对(不允许数据冗余)
  7.         {
  8.                 return false; //插入失败
  9.         }
  10.         //2、判断是否需要调整哈希表的大小
  11.         if (_table.size() == 0) //哈希表大小为0
  12.         {
  13.                 _table.resize(10); //设置哈希表初始空间大小
  14.         }
  15.         else if ((double)_n / (double)_table.size() > 0.7) //负载因子大于0.7需要增容
  16.         {
  17.                 //增容
  18.                 //a、创建一个新的哈希表,新哈希表的大小设置为原哈希表的2倍
  19.                 HashTable<K, V> newHT;
  20.                 newHT._table.resize(2 * _table.size());
  21.                 //b、将原哈希表当中的数据插入到新哈希表
  22.                 for (auto& e : _table)
  23.                 {
  24.                         if (e._state == EXIST)
  25.                         {
  26.                                 newHT.Insert(e._kv);
  27.                         }
  28.                 }
  29.                 //c、交换这两个哈希表
  30.                 _table.swap(newHT._table);
  31.         }
  32.         //3、将键值对插入哈希表
  33.         //a、通过哈希函数计算哈希地址
  34.         size_t start = kv.first%_table.size(); //除数不能是capacity
  35.         size_t index = start;
  36.         size_t i = 1;
  37.         int base = index;
  38.         //b、找到一个状态为EMPTY或DELETE的位置
  39.         while (_table[index]._state == EXIST)
  40.         {
  41.                 index = start + i; //线性探测
  42.                 //index = start + i*i; //二次探测
  43.                 index %= _table.size(); //防止下标超出哈希表范围
  44.                 i++;
  45.         }
  46.         //c、将数据插入该位置,并将该位置的状态设置为EXIST
  47.         _table[index]._kv = kv;
  48.         _table[index]._state = EXIST;
  49.        
  50.         //4、哈希表中的有效元素个数加一
  51.         _n++;
  52.         return true;
  53. }
复制代码
哈希表的删除

在哈希表中删除数据的步骤如下:

  • 通过哈希函数计算出对应的哈希桶编号。
  • 遍历对应的哈希桶,寻找待删除结点。
  • 若找到了待删除结点,则将该结点从单链表中移除并释放。
  • 删除结点后,将哈希表中的有效元素个数减一。
注意: 不要先调用查找函数判断待删除结点是否存在,这样做如果待删除不在哈希表中那还好,但如果待删除结点在哈希表,那我们还需要重新在哈希表中找到该结点并删除,还不如一开始就直接在哈希表中找,找到了就删除。
  1. //查找函数
  2. HashData<K, V>* Find(const K& key)
  3. {
  4.         if (_table.size() == 0) //哈希表大小为0,查找失败
  5.         {
  6.                 return nullptr;
  7.         }
  8.         size_t start = key % _table.size(); //通过哈希函数计算哈希地址(除数不能是capacity)
  9.         size_t index = start;
  10.         size_t i = 1;
  11.         //直到找到空位置为止
  12.         while (_table[index]._state != EMPTY)
  13.         {
  14.                 //若该位置的状态为EXIST,并且key值匹配,则查找成功
  15.                 if (_table[index]._state == EXIST&&_table[index]._kv.first == key)
  16.                 {
  17.                         return &_table[index];
  18.                 }
  19.                 index = start + i; //线性探测
  20.                 //index = start + i*i; //二次探测
  21.                 index %= _table.size(); //防止下标超出哈希表范围
  22.                 i++;
  23.         }
  24.         return nullptr; //直到找到空位置还没有找到目标元素,查找失败
  25. }
复制代码
哈希表的大小为什么建议是素数

   都说使用除留余数法时,哈希表的大小最好是素数,这样能够减少哈希冲突产生的次数。
  下面用合数(非素数)10和素数11来进行说明。


  • 合数10的因子有:1,2,5,10。
  • 素数11的因子有:1,11。
我们选取下面这五个序列:

  • 间隔为1的序列:s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  • 间隔为2的序列:s2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
  • 间隔为5的序列:s3 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
  • 间隔为10的序列:s4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
  • 间隔为11的序列:s5 = {11, 22, 33, 44, 55, 66, 77, 88, 99, 110}
   实验一:将s1插入表长为10的哈希表,即模10:
  哈希表012345678910123456789  实验二:将s1插入表长为11的哈希表,即模11:
  哈希表01234567891012345678910  实验三:将s2插入表长为10的哈希表,即模10:
  哈希表01234567891024682012141618  实验四:将s2插入表长为11的哈希表,即模11:
  哈希表0123456789101221441661882010  实验五:将s3插入表长为10的哈希表,即模10:
  哈希表01234567891052015302540355045  实验六:将s3插入表长为11的哈希表,即模11:
  哈希表0123456789104535251555040302010  实验七:将s4插入表长为10的哈希表,即模10:
  哈希表0123456789102030405060708090100  实验八:将s4插入表长为11的哈希表,即模11:
  哈希表012345678910100908070605040302010  实验九:将s5插入表长为10的哈希表,即模10:
  哈希表0123456789110112233445566778899  实验十:将s5插入表长为11的哈希表,即模11:
  哈希表012345678910112233445566778899110根据上述实验,我们可以得出以下结论:


  • 如果一个序列中,每个元素之间的间隔为1,那么不管哈希表的大小为几,该序列插入哈希表后都是均匀分布的(实验一、实验二)。
  • 如果一个序列中,每个元素之间的间隔刚好是哈希表大小或哈希表的倍数,那么该序列插入哈希表时,将全部产生冲突(实验七、实验十)。
  • 哈希表中的分布按照序列的间隔进行分隔,如果序列的间隔恰好是哈希表大小的因子,那么哈希表的分布就会产生间隔(实验三、实验五、),反之则不会(实验三、实验四、实验五、实验六、实验八、实验九)。
某个随机序列当中,每个元素之间的间隔是不定的。因此,为了尽量减少冲突,我们就需要让哈希表的大小的因子最少,这样才能最大可能避免让某两个元素之间的间隔是哈希表的因子,所以哈希表的大小最好是素数。
   如何实现?
  我们如果每次增容时让哈希表的大小增大两倍,那么增容后哈希表的大小就不是素数了。因此我们可以将需要用到的素数序列提前用一个数组存储起来,当我们需要增容时就从该数组当中进行获取就行了。
例如,下面这些都是素数,且它们近似以2倍的形式进行增长,我们就可以将它们用一个数组存储起来。
  1. //删除函数
  2. bool Erase(const K& key)
  3. {
  4.         //1、查看哈希表中是否存在该键值的键值对
  5.         HashData<K, V>* ret = Find(key);
  6.         if (ret)
  7.         {
  8.                 //2、若存在,则将该键值对所在位置的状态改为DELETE即可
  9.                 ret->_state = DELETE;
  10.                 //3、哈希表中的有效元素个数减一
  11.                 _n--;
  12.                 return true;
  13.         }
  14.         return false;
  15. }
复制代码
当我们需要增容时,就在该素数数组中找到下一个素数作为哈希表增容后的大小即可。
  1. //每个哈希桶中存储数据的结构
  2. template<class K, class V>
  3. struct HashNode
  4. {
  5.         pair<K, V> _kv;
  6.         HashNode<K, V>* _next;
  7.         //构造函数
  8.         HashNode(const pair<K, V>& kv)
  9.                 :_kv(kv)
  10.                 , _next(nullptr)
  11.         {}
  12. };
复制代码
来源:https://blog.caogenba.net/chenlong_cxy/article/details/122390863
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作