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

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

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

2.1.2 闭散列二次探测(了解)

线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,

因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题。

  • 线性探测:start + i,i = 0,1,2,3…
  • 二次探测:start + i^2,i = 0,1,2,3…

使用二次探测,查找时也是按照二次探测的方式去查找。

研究表明:

当表的长度为质数且表装载因子不超过0.5时,新的表项一定能够插入,

而且任何一个位置都不会被探查两次。

因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子不超过0.5,如果超出必须考虑增容。

无论是线性探测还是二次探测,闭散列方式的最大缺陷就是空间利用率较低。

所以就引出了下面开散列(哈希桶)的概念。

2.2 开散列(哈希桶)概念和代码

开散列:又叫拉链法(链地址法),首先对key值集合用哈希函数计算映射下标,

具有相同下标的key值归于同一子集合,每一个子集合称为一个桶,

各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

如上图所示,此时的哈希表中存放的是一个单链表的头指针。

  • 不同的数据,根据哈希函数算出的映射位置发生哈希碰撞时,这些碰撞的数据会挂在哈希表对应位置指向的单链表中。这些单链表被形象称为
  • 每个桶中放的都是发生哈希冲突的元素。
  • 当有新数据插入时,进行头插。

如上图中所示,7,27,57,根据哈希函数都映射到哈希表下标为7的位置,这几个数据按照头插的顺序以单链表的形式挂在哈希表下标为7的位置。

新插入的数据如果尾插的话,在找单链表的尾部时,会有效率损失,由于没有排序要求,所以头插是效率最高的。

开散列的方法,通常被称为哈希桶,使用的也最广泛,能够解决闭散列中空间利用率不高的问题。


哈希桶会不会出现时间复杂度为O(N)的情况?极端情况是会的,但是概率极低,像前面十个空间,扩容了还会把数据分散,开了很多空间的时候,几乎不会出现极端情况,有些库还有一些备案,比如Java库:挂的桶大于8的话(这里也表明挂的桶基本是很少的),就改成挂红黑树。

基于以上原因,哈希桶和快排一样,可以不看最坏时间复杂度,而看平均复杂度:O(1)。

数据类型定义和框架(这里用HashBucket命名空间包起来,把前面的用CloseHash包起来)

namespace HashBucket
{
  template<class K, class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode* _next; // 不用存状态栏了,存下一个结点指针
  };
 
  template<class K>
  struct HashFunc // 可以把闭散列的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:
    typedef HashData<K, V> Node;
 
  protected:
    vector<Node*> _tables; // 指针数组
    size_t _size;
  };
}

采用哈希桶的方式来解决哈希碰撞时,哈希表中存放的数据是单链表的头节点,

链表节点中有键值对,还有下一个节点的指针。仍然使用闭散列中转换整形的仿函数。

插入:

插入首先要去重(用查找),然后检查是否要扩容,最后再插入

先写查找:

    Node* Find(const K& key)
    {
      if (_tables.size() == 0)
      {
        return nullptr;
      }
 
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* cur = _tables[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }

根据哈希函数的映射关系,直接找到key值哈希表中的存放位置。

然后在该位置挂的桶中寻找key值。

哈希桶结构,查找的效率高就高在这里,可以直接根据key值定位哈希表,时间复杂度是O(1)。


现在写插入,哈希桶的方式中也会扩容,否则桶就会越挂越长,违背了哈希桶设计的初衷。


一般情况下,当哈希表的负载因子等于1的时候,发生扩容。

当负载因子等于1时,也就是数据个数和哈希表大小相等的时候进行扩容。


扩容和闭散列类似,将旧的哈希表中的数据插入到新哈希表中,


复用Insert函数,然后旧表被释放,新表留下来。


但是这种方式不是很好,有很大的开销,效率有所损失:


在将旧表中的数据插入新表的时候,每插入一个,新表就需要new一个节点,


旧表中的所有节点都会被new一遍。然后将旧表中的所有节点再释放,


这里做了没必要的工作。相同的一个节点,会先在新表中new一个,再释放旧表的。


新表中完全可以不再new新的节点,直接使用旧表中的节点。


旧表中可以直接复用的节点是:改变了哈希表容量以后,映射关系不变的节点。


比如节点27,哈希表的容量从10变成20,但是映射后的下标仍然是7,这样的节点就可以复用。


那些映射关系变了的节点就不可以直接复用了,需要改变所在桶的位置。


如节点18,哈希表的容量从10变成20,映射后的下标从8变成18,此时就需要改变18所在的桶了。

    bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
      {
        return false;
      }
 
      Hash hs;
      if (_size == _tables.size()) // 负载因子到1就扩容
      {
        size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
        vector<Node*> newTables;
        newTables.resize(newSize, nullptr);
 
        for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
        {
          Node* cur = _tables[i];
          while (cur)
          {
            Node* next = cur->_next;
 
            size_t hashi = hs(cur->_kv.first) % newTables.size();
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;
 
            cur = next;
          }
 
          _tables[i] = nullptr;
        }
 
        _tables.swap(newTables);
      }
 
      size_t hashi = hs(kv.first) % _tables.size(); // 哈希映射
      Node* newnode = new Node(kv); // 头插
      newnode->_next = _tables[hashi];
      _tables[hashi] = newnode;
      ++_size;
    }

写完插入和查找,现在写写删除:

这里的删除就类似链表的删除,哈希表挂的桶是单链表,只指定要删除节点是无法进行删除的,

必须指定前一个节点,否则无法再链接。所以不能直接复用Find删除:

    bool Erase(const K& key)
    {
      if (_tables.size() == 0) // 防止除零错误
      {
        return false;
      }
 
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* cur = _tables[hashi];
      Node* prev = nullptr;
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          if (prev == nullptr) // 头插,先把指针数组存的指针指向cur的下一个
          {
            _tables[hashi] = cur->_next;
          }
          else // 中间删
          {
            prev->_next = cur->_next;
          }
          delete cur; // 统一在这delete
          return true;
        }
 
        prev = cur; // 往后走
        cur = cur->_next;
      }
      return false; // 没找到
    }

根据哈希函数的映射关系,定位到对应哈希表中挂的某个桶上。

如果key是单链表的头节点,直接让它的下一个节点当头节点就可以。

如果key不是头节点,则在删除的时候,需要prev指针的辅助来链接单链表。

由于哈希映射的存在,在寻找key时的时间复杂度同样是O(1),所以删除的效率也很高。


写到这并且想测试,我们应该意识到写个析构函数了,哈希桶必须有析构函数,闭散列的方式,


默认生成的析构函数就能满足要求,但是哈希桶不可以。如果只使用默认生成的析构函数,


在哈希桶销毁的时候,默认的析构函数会调用vector的析构函数。


vector的析构函数只会释放vector的本身,而不会释放vector上挂着的桶。


所以需要显示定义析构函数,在析构函数中将vector挂的桶进行释放。


在释放的时候,需要将单链表的下一个节点记录下来,再释放当前节点,


否则会找不到下一个节点。

    ~HashTable()
    {
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
          delete cur;
          cur = next;
        }
        _tables[i] = nullptr;
      }
    }

测试:

void TestHash3() // 哈希桶测试统计次数的可以用TestHash2改下命名空间
{
  int arr[] = {1, 11, 4, 15, 26, 7, 44, 55, 99, 78};
  HashBucket::HashTable<int, int> ht;
  for (const auto& e : arr)
  {
    ht.Insert(make_pair(e, e));
  }
 
  ht.Insert(make_pair(22, 22)); // 刚好扩容
}

2.2.1 除留余数法获取素数

有研究表面,哈希表的大小最好是一个素数,这样的话能够提供哈希结构的效率,

那么如何快速获取一个类似两倍关系的素数呢?

    inline size_t __stl_next_prime(size_t n)
    {
      static const size_t __stl_num_primes = 28;
      static const size_t __stl_prime_list[__stl_num_primes] =
      {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
      };
 
      for (size_t i = 0; i < __stl_num_primes; ++i)
      {
        if (__stl_prime_list[i] > n)
        {
          return __stl_prime_list[i];
        }
      }
 
      return -1; // 不会走到这,随便返回一个值
    }

上面代码是STL库中获取素数的方式。


将素数放在一个数组中,两个素数之间的关系接近二倍,但是又要符合是一个素数。

当需要进行扩容时,就从数组中寻找一个比当前素数大的素数作为新的容量。

上面数组中虽然只有28个素数,但是完全够用了,最大的素数意味着哈希表有4GB个数据,每个数据是一个指针(32位),也就是4B大小,这样来看已经有16GB的数据量了,再考虑上挂的桶中的数据,数据量是非常大,正常情况下根本没有这么大量的数据。


如果不信讲的复杂度为O(1)的那个,因为这取决于最大桶的长度,


这里可以写几个获取桶个数,最大桶个数,数据个数,表长度来验证验证:


    size_t Size() // 存的数据个数
    {
      return _size;
    }
 
    size_t TablesSize() // 表的长度
    {
      return _tables.size();
    }
 
    size_t BucketNum() // 桶的个数
    {
      size_t num = 0;
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        if (_tables[i]) // 如果不是空就有桶
        {
          ++num;
        }
      }
      return num;
    }
 
    size_t MaxBucketLenth() // 最长桶的长度
    {
      size_t maxLen = 0;
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        size_t len = 0;
        Node* cur = _tables[i];
        while (cur)
        {
          ++len;
          cur = cur->_next;
        }
        if (len > maxLen)
        {
          maxLen = len;
        }
      }
      return maxLen;
    }

2.2.2 开散列(哈希桶)完整代码

HashTable.h:(把上面写的闭散列CloseHash命名空间的删了)

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
namespace HashBucket
{
  template<class K, class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode* _next; // 不用存状态栏了,存下一个结点指针
 
    HashNode(const pair<K, V>& kv)
      :_kv(kv)
      , _next(nullptr)
    {}
  };
 
  template<class K>
  struct HashFunc // 可以把闭散列的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:
    typedef HashNode<K, V> Node;
 
    ~HashTable()
    {
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
          delete cur;
          cur = next;
        }
        _tables[i] = nullptr;
      }
    }
 
    Node* Find(const K& key)
    {
      if (_tables.size() == 0)
      {
        return nullptr;
      }
 
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* cur = _tables[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }
 
    inline size_t __stl_next_prime(size_t n)
    {
      static const size_t __stl_num_primes = 28;
      static const size_t __stl_prime_list[__stl_num_primes] =
      {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
      };
 
      for (size_t i = 0; i < __stl_num_primes; ++i)
      {
        if (__stl_prime_list[i] > n)
        {
          return __stl_prime_list[i];
        }
      }
 
      return -1; // 不会走到这,随便返回一个值
    }
 
    bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
      {
        return false;
      }
 
      Hash hs;
      if (_size == _tables.size()) // 负载因子到1就扩容
      {
        //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
        vector<Node*> newTables;
        //newTables.resize(newSize, nullptr);
        newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数,前两注释改成这一条
 
        for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
        {
          Node* cur = _tables[i];
          while (cur)
          {
            Node* next = cur->_next;
 
            size_t hashi = hs(cur->_kv.first) % newTables.size();
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;
 
            cur = next;
          }
 
          _tables[i] = nullptr;
        }
 
        _tables.swap(newTables);
      }
 
      size_t hashi = hs(kv.first) % _tables.size(); // 哈希映射
      Node* newnode = new Node(kv); // 头插
      newnode->_next = _tables[hashi];
      _tables[hashi] = newnode;
      ++_size;
      return true;
    }
 
    bool Erase(const K& key)
    {
      if (_tables.size() == 0) // 防止除零错误
      {
        return false;
      }
 
      Hash hs;
      size_t hashi = hs(key) % _tables.size();
      Node* cur = _tables[hashi];
      Node* prev = nullptr;
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          if (prev == nullptr) // 头插,先把指针数组存的指针指向cur的下一个
          {
            _tables[hashi] = cur->_next;
          }
          else // 中间删
          {
            prev->_next = cur->_next;
          }
          delete cur; // 统一在这delete
          return true;
        }
 
        prev = cur; // 往后走
        cur = cur->_next;
      }
      return false; // 没找到
    }
 
    size_t Size() // 存的数据个数
    {
      return _size;
    }
 
    size_t TablesSize() // 表的长度
    {
      return _tables.size();
    }
 
    size_t BucketNum() // 桶的个数
    {
      size_t num = 0;
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        if (_tables[i]) // 如果不是空就有桶
        {
          ++num;
        }
      }
      return num;
    }
 
    size_t MaxBucketLenth() // 最长桶的长度
    {
      size_t maxLen = 0;
      for (size_t i = 0; i < _tables.size(); ++i)
      {
        size_t len = 0;
        Node* cur = _tables[i];
        while (cur)
        {
          ++len;
          cur = cur->_next;
        }
        if (len > maxLen)
        {
          maxLen = len;
        }
      }
      return maxLen;
    }
 
  protected:
    vector<Node*> _tables; // 指针数组
    size_t _size;
  };
}


Test.cpp:

#include "HashTable.h"
 
void TestHash1()
{
  int arr[] = { 1, 11, 4, 15, 26, 7, 44 }; // 在加一个数据就会扩容
  CloseHash::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[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
 
  //CloseHash::HashTable<string, int> countHT;
  HashBucket::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));
    }
  }
}
 
void TestHash3() // 哈希桶测试统计次数的可以用TestHash2改下命名空间
{
  int arr[] = {1, 11, 4, 15, 26, 7, 44, 55, 99, 78};
  HashBucket::HashTable<int, int> ht;
  for (const auto& e : arr)
  {
    ht.Insert(make_pair(e, e));
  }
 
  ht.Insert(make_pair(22, 22));
}
 
void TestHash4()
{
  int n = 10000;
  vector<int> v;
  v.reserve(n);
  srand(time(0));
  for (int i = 0; i < n; ++i)
  {
    //v.push_back(i);
    v.push_back(rand() + i);  // 重复少
    //v.push_back(rand());  // 重复多
  }
 
  size_t begin1 = clock();
  HashBucket::HashTable<int, int> ht;
  for (auto e : v)
  {
    ht.Insert(make_pair(e, e));
  }
  size_t end1 = clock();
 
  cout << "数据个数:" << ht.Size() << endl;
  cout << "表的长度:" << ht.TablesSize() << endl;
  cout << "桶的个数:" << ht.BucketNum() << endl;
  cout << "平均每个桶的长度:" << (double)ht.Size() / (double)ht.BucketNum() << endl;
  cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl;
  cout << "负载因子:" << (double)ht.Size() / (double)ht.TablesSize() << endl;
}
 
int main()
{
  TestHash2();
  TestHash3();
  TestHash4();
 
  return 0;
}

没测TestHash4的:

测TestHash4的:

这是测了几次的结果:(随着负载因子的变大,桶最长也就2或3,因为桶的个数太多了)


多测了几个数量级的n,发现最长的桶的长度也就4:

从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现(下):https://developer.aliyun.com/article/1522315?spm=a2c6h.13148508.setting.17.50c04f0emsc6o6

目录
相关文章
|
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++
|
1月前
|
C语言 C++ 编译器
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
|
17天前
|
自然语言处理 C语言 C++
程序与技术分享:C++写一个简单的解析器(分析C语言)
程序与技术分享:C++写一个简单的解析器(分析C语言)
|
19天前
|
程序员 C语言 C++
【C语言】:柔性数组和C/C++中程序内存区域划分
【C语言】:柔性数组和C/C++中程序内存区域划分
14 0
|
2天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
22 10
|
7天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
39 9
|
2天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
10天前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。