【C++从0到王者】第三十六站:哈希

本文涉及的产品
简介: 【C++从0到王者】第三十六站:哈希

一、unordered系列容器

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到logN,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到。在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同。

unordered_xxx系列与map和set容器的用法上几乎没有任何区别

他们的区别就是

  1. unordered_xxx系列都是哈希表作为底层的,而map和set是用红黑树作为底层的
  2. unordered_xxx系列不排序,只去重
  3. unordered_xxx系列是单项迭代器

二、unordered_set

如下就是unordered_set的文档

unordered_set是一种容器,它以无特定顺序的方式存储唯一的元素,并允许根据元素的值快速检索各个元素。

在unordered_set中,元素的值同时也是它的键,唯一标识该元素。键是不可变的,因此,unordered_set中的元素一旦放入容器后就不能被修改,不过可以插入和删除。

在内部,unordered_set中的元素不按任何特定顺序排序,而是根据它们的哈希值组织成桶,以便通过它们的值(平均具有恒定的平均时间复杂度)直接快速访问各个元素。

对于通过键访问单个元素,unordered_set容器比set容器更快,尽管对于通过子集范围迭代它们通常效率较低。

容器中的迭代器是单向迭代器

由于接口其实大差不差,所以我们可以直接使用去感受一下

void test1()
{
  unordered_set<int> us;
  us.insert(1);
  us.insert(5);
  us.insert(2);
  us.insert(6);
  us.insert(4);
  us.insert(3);
  unordered_set<int>::iterator usit = us.begin();
  while (usit != us.end())
  {
    cout << *usit << endl;
    usit++;
  }
  cout << endl;
}

三、unordered_map

如下是unordered_map的文档

无序映射是关联容器,存储由键值和映射值组合形成的元素,并允许根据它们的键快速检索各个元素。

在unordered_map中,键值通常用于唯一标识元素,而映射值是与该键关联的对象的内容。键和映射值的类型可以不同。

在内部,unordered_map中的元素不根据它们的键或映射值按任何特定顺序排序,而是根据它们的哈希值组织成桶,以便通过它们的键值直接快速访问各个元素(平均具有恒定的平均时间复杂度)。

对于通过键访问单个元素,unordered_map容器比map容器更快,尽管对于通过子集范围迭代它们通常效率较低。

无序映射实现了直接访问运算符(operator[]),允许使用键值作为参数直接访问映射值。

容器中的迭代器是单向迭代器。

void test2()
{
  unordered_map<string, string> dict;
  dict["insert"] = "插入";
  dict["sort"] = "排序";
  dict["delete"] = "删除";
  dict["string"] = "字符串";
  dict["insert"] = "xxxxx";
  dict.insert(make_pair("iterator", "迭代器"));
  unordered_map<string, string>::iterator umit = dict.begin();
  while (umit != dict.end())
  {
    cout << umit->first << ":" << umit->second << endl;
    umit++;
  }
  cout << endl;
}

四、unordered_set与set的比较

如下所示,我们采用如下代码进行比较

void test3()
{
  const size_t N = 100000;
  unordered_set<int> us;
  set<int> s;
  vector<int> v;
  v.reserve(N);
  srand(time(0));
  for (size_t i = 0; i < N; ++i)
  {
    v.push_back(rand());
    //v.push_back(rand()+rand());  //减少重复数据
    //v.push_back(i);     //有序的时候
  }
  size_t begin1 = clock();
  for (auto e : v)
  {
    s.insert(e);
  }
  size_t end1 = clock();
  cout << "set insert:" << end1 - begin1 << endl;
  size_t begin2 = clock();
  for (auto e : v)
  {
    us.insert(e);
  }
  size_t end2 = clock();
  cout << "unordered_set insert:" << end2 - begin2 << endl;
  size_t begin3 = clock();
  for (auto e : v)
  {
    s.find(e);
  }
  size_t end3 = clock();
  cout << "set find:" << end3 - begin3 << endl;
  size_t begin4 = clock();
  for (auto e : v)
  {
    us.find(e);
  }
  size_t end4 = clock();
  cout << "unordered_set find:" << end4 - begin4 << endl << endl;
  cout <<"插入数据个数:"<< s.size() << endl;
  cout <<"插入数据个数:" << us.size() << endl << endl;;
  size_t begin5 = clock();
  for (auto e : v)
  {
    s.erase(e);
  }
  size_t end5 = clock();
  cout << "set erase:" << end5 - begin5 << endl;
  size_t begin6 = clock();
  for (auto e : v)
  {
    us.erase(e);
  }
  size_t end6 = clock();
  cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
}

可以看到,在无序的数据的时候,unordered_set更占优势一些。

但是我们会发现有很多的重复数据,于是我们可以对随机值+随机值以此减少重复数据

可以看到,还是unordered_set占据优势

然后我们可以尝试一下有序的数据

此时set占据优势

可见,如果数据是无序的,unordered_set更优,如果是有序的,使用set更好

五、各种查找的比较

  1. 暴力查找

首先就是我们最常见的暴力查找,他的时间复杂度是O(N)

  1. 二分

不过我们可以对其进行一定程度的优化,即先排序,这样的画他的时间复杂度就变为了logN,但是增删还是不方便

  1. 平衡树

再后来就是使用红黑树,他的效率都是很优秀的,增删查改都是logN

  1. 哈希

除此之外还有一种方式就是哈希,即存储的值和存储位置建立出一个对应关系,这样的话时间复杂度直接变为了O(1),哈希我们也称作散列

哈希的方式有点类似于计数排序

这种方式在现实生活中就应用于图书馆中的分区

但是上面这种哈希仅仅只是比较适合于数据比较集中的,像字母只有26个,就很集中比较适合上面这种方式

这种方式也被称为直接定址法

但是如果数据很分散的话,就不适合了。因为会试想一下,在一个数组中,大部分的元素位于0~20之间,但是突然一个数据是9999,那么我们难道就要开这么大的空间,去直接定址吗?显然是不可能的!

于是我们就有了下面一种哈希,除留余数法,即对所有数据对一个数据取模后,在根据这个值进行放入。

不过这种方法会导致一种问题,就是哈希冲突:不同的值,可能会映射到一个位置,值和位置是多对一的关系

为了解决这种方法,我们可以使用很多种方法去解决。

一种方法是线性探测、或者二次探测,即使用某种规则去占用下一个位置,不过这种方式不是很好,因为会影响其他位置

不过还有一种方式是拉链法,即哈希桶的方式去解决。这种方式比较好,不会影响其他位置

六、哈希函数

1.哈希函数概念与哈希冲突

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

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

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

当向该结构中:

  • 插入元素
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置
    取元素比较,若关键码相等,则搜索成功

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

例如在如下的哈希函数中

例如:数据集合{1,7,6,4,5,9};

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

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

不过有时候我们也会遇到一种情况,当我们继续插入44的时候,我们发现原本的4的位置已经被占领了

**不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞 **

**把具有不同关键码而具有相同哈希地址的数据元素称为“同义词” **

2.常见哈希函数

  1. 直接定址法
    取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
    优点:简单、均匀
    缺点:需要事先知道关键字的分布情况
    使用场景:适合查找比较小且连续的情况

比如统计字符串中的字符出现的个数,因为字符的范围比较集中

  1. 除留余数法
    设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,
    按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

不过上述的方法可能会产生哈希冲突

七、解决哈希冲突

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

1.闭散列—开放定址法

所谓的开放定址法:其实就是当前位置被占用了,通过某种规则去找下一个位置(占用别人的位置)

常见的方案有:线性探测,二次探测等…

我们下面主要探讨线性探测

下面是线性探测的插入策略:

如下所示,我们使用这个哈希函数,当我们依次插入1,111,4,5,6,7,44,9的时候,44由于下标为四的状态已经被占用了,所以要向后寻找空位置,进行放入。111也由于1的下标被占用了,也冲突了,所以向后寻找。这就是线性探测,如果我们继续插入一个19,那么他应该放入9下标的位置,但是9已经被占用了,所以会放入0的位置

如下就是已经有9了,继续放入19

下面是线性探测的查找:

在如下所示的表中,如果我们想继续查找44的话,那么就会根据哈希函数计算出下标,从4的位置开始找起来,如果不是直接匹配,那么就继续向后寻找,直到找到。如下就可以在8的位置找到44

如果想要找到54的话,那么也是根据哈希函数,从4开始找起来,一值找到0位置,发现0位置是一个空位置,那么结束查找,因为没有找到。

在这里也侧面反映出一个问题,哈希表不可以太满了,太满了会导致效率极其低下

线性探测的删除:

试想一下,我们删除一个数据是可以直接删除的吗?如果遇到如下的情况,先删除了6,然后查找44。似乎出现了卡bug的行为,因为删除6以后,6的位置已经为空了,而查找是一旦发现为空就停止查找了

所以删除会影响查找

所以为了解决上面的办法,我们删除不应该是将一个位置变为空,而是使用标记。

我们可以对每个数据使用三种状态进行标记:EXIST、EMPTY、DELETE,分别表示存在,空,删除三种状态

这样的话,当我们删除一个数据的时候,直接修改他的状态即可。

而对于查找的时候,遇到DELETE的时候不要停止,遇到空才停止

闭散列的代码实现

首先是闭散列的结构,如下所示。 在哈希表中,虽然vector已经有size函数了,但是这里计算出来的并非有效数据,所以我们还需要一个n来记录哈希表中的有效数据

enum STATE
  {
    EXIST,
    EMPTY,
    DELETE
  };
  template<class K,class V>
  struct HashDate
  {
    pair<K, V> _kv;
    STATE _state = EMPTY;
  };
  template<class K, class V >
  class HashTable
  {
  public:
  private:
    vector<HashDate<K, V>> _table;
    size_t _n = 0;
  };
  • 闭散列的插入实现

考虑到,闭散列是根据线性探测查找的,所以我们可以简单的写出以下代码,因为我是是使用vector作为底层的,所以我们使用size作为模的对象,切记不可以使用capacity,因为capacity虽然开出来了容量,但是这个容量是不可以使用的。size才是可访问的范围。

上面的代码其实还存在一定问题:

那就是哈希表的扩容问题,何时进行扩容,是需要我们去考虑的。而且我们不能让哈希表满了,因为哈希表一旦满了,就会死循环了

对于这个负载因子

负载因子越大,冲突概率越大,空间利用率越高

负载因子越小,冲突概率越小,空间利用率越低

哈希表不能满了在扩容,控制负载因子到一定值就必须扩容

所以我们可能会写出以下代码,但是下面代码还是错的

为什么错了呢?其实是因为,resize以后,导致哈希函数改变了,从而导致映射关系乱了,需要重新映射

我们重新映射的办法就是,在创建一个哈希表,然后依次往新的哈希表中插入数据,最后交换两个哈希表的vector,这样的写法有点类似于赋值运算符重载的现代写法

bool Insert(const pair<K, V>& kv)
    {
      if (10 * _n / _table.size() >= 7)
      {
        size_t newSize = _table.size() * 2;
        //遍历旧表,重新映射到新表
        HashTable<K, V> newHT;
        newHT._table.resize(newSize);
        for (int i = 0; i < _table.size(); i++)
        {
          if (_table[i]._state == EXIST)
          {
            newHT.Insert(_table[i]._kv);
          }
        }
        _table.swap(newHT._table);
      }
      size_t hashi = kv.first % _table.size();  
      while (_table[hashi]._state == EXIST)
      {
        hashi++;
        hashi %= _table.size();
      }
      _table[hashi]._kv = kv;
      _table[hashi]._state = EXIST;
      ++_n;
      return true;
    }

我们可以使用如下的测试用力进行测试:

void test4()
{
  Sim::HashTable<int, int> ht;
  int a[] = { 1,111,4,15,25,7,44,9 };
  for (auto e : a)
  {
    ht.Insert(make_pair(e, e));
  }
}

如下图是扩容之前的

如下是扩容之后的

  • 闭散列查找

闭散列的查找还是比较容易的,这里我们特别注意的是,我们的返回值是一个HashDate<const K,V>*类型的,因为我们要避免哈希表中的第一个元素被修改了,一旦第一个元素被修改了,那么就麻烦了,映射关系乱了,而我们返回的时候,由于我们的底层的第一个参数并不是const类型的,这里也不是权限的缩小,而是两种完全不同的类型,所以我们需要强制类型转换来处理

HashDate<const K, V>* Find(const K& key)
    {
      size_t hashi = key % _table.size();
      while (_table[hashi]._state != EMPTY)
      {
        if (_table[hashi]._state == EXIST
          && _table[hashi]._kv.first == key)
        { 
          return (HashDate<const K, V>*) & _table[hashi];
        }
        hashi++;
        hashi %= _table.size();
      }
      return nullptr;
    }
  • 闭散列删除

如下所示,哈希表的删除是少数删除比插入还简单的容器,因为只需要改一个状态即可。

bool Erase(const K& key)
    {
      HashDate<const K, V>* ret = Find(key);
      if (ret)
      {
        ret->_state = DELETE;
        --_n;
        return true;
      }
      return false;
    }
  • 特殊类型的量化

上面的代码其实还是不够完善的,因为当我们的哈希表中的元素是字符串类型的时候,就麻烦了,字符串类型无法进行取模运算,所以我们需要有一个办法对字符串进行量化,让他转化为整型,有了整型以后,才能去建立映射关系。甚至于这个key都一定是字符串,如果不是字符串,那么又该如何进行量化,这才是插入中最麻烦的地方。

为了解决这个问题,我们可以使用仿函数。利用仿函数去量化,那么仿函数该如何去写呢?首先就是默认的,可以直接转为size_t类型的

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

如果遇到特殊类型的,我们可以自己写一个仿函数去量化,比如string类型

struct StringHashFunc
  {
    size_t operator()(const string& key)
    {
      return (size_t)key[0];
    }
  };

这样我们只需要传参的时候使用这个仿函数即可

但是对于string其实使用是很高频的,所以我们不妨使用模板的特化

template<>
  struct DefaultHashFunc<string>
  {
    size_t operator()(const string& key)
    {
      return (size_t)key[0];
    }
  };

接下来,我们可以使用如下测试用例进行测试

void test5()
{
  //Sim::HashTable<string, string, Sim::StringHashFunc> dict;
  Sim::HashTable<string, string> dict;
  dict.Insert(make_pair("sort", "排序"));
  dict.Insert(make_pair("insert", "插入"));
  dict.Insert(make_pair("delete", "删除"));
  //Sim::HashDate<const string, string>* ret = dict.Find("sort");
  Sim::HashDate<const string, string>* ret = dict.Find("sort");
  ret->_kv.second = "xxxx";
}

虽然解决了特殊类型的问题,但是对于string类型而言,上面的处理其实并不是很好,因为太单一了,随便两个首字母相同的就冲突了,所以我们可以考虑所有字母相加

template<>
  struct DefaultHashFunc<string>
  {
    size_t operator()(const string& key)
    {
      size_t hash = 0;
      for (auto ch : key)
      {
        hash += ch;
      }
      return hash;
    }
  };

但是上面还是无法规避一些特殊情况,比如两个字符串里面的字母都相同,仅仅只是交换了某些字母的顺序

其实对于字符串转整型有很多种方法

如旁边所示,是字符串转整型的一些方法:字符串转整型

我们可以使用第一种方法

template<>
  struct DefaultHashFunc<string>
  {
    size_t operator()(const string& key)
    {
      size_t hash = 0;
      for (auto ch : key)
      {
        hash = hash * 131 + ch;
      }
      return hash;
    }
  };

这样的话,确实不是那么容易冲突了

上面就是线性探测的方法了。

线性探测所存在的问题就是,容易发生拥堵踩踏事件

线性探测的基本思路就是

hashi = key % n;
hashi = hashi + i;
i>=0;

为了防止过于频繁的拥堵踩踏事件,我们可以使用二次探测。

二次探测与线性探测的唯一不同就是,二次探测每次是探测平方的,这样就会导致每个数据都会间隔开。使得数据不是那么集中拥堵,可以一定程度缓解拥堵踩踏

hashi = key % n;
hashi = hashi + pow(i,2);
i>=0;

但是无论如何,无论是线性探测也好,二次探测也好,他们都会导致拥堵踩踏,产生冲突,冲突的值会相互影响,这是开放定址法自身的缺陷

如下是闭散列/开放地址法的完整代码

namespace open_address
{
  enum STATE
  {
    EXIST,
    EMPTY,
    DELETE
  };
  template<class K,class V>
  struct HashDate
  {
    pair<K, V> _kv;
    STATE _state = EMPTY;
  };
  template<class K>
  struct DefaultHashFunc
  {
    size_t operator()(const K& key)
    {
      return (size_t)key;
    }
  };
  template<>
  struct DefaultHashFunc<string>
  {
    size_t operator()(const string& key)
    {
      size_t hash = 0;
      for (auto ch : key)
      {
        hash = hash * 131 + ch;
      }
      return hash;
    }
  };
  //template<>
  //struct DefaultHashFunc<string>
  //{
  //  size_t operator()(const string& key)
  //  {
  //    size_t hash = 0;
  //    for (auto ch : key)
  //    {
  //      hash += ch;
  //    }
  //    return hash;
  //  }
  //};
  //template<>
  //struct DefaultHashFunc<string>
  //{
  //  size_t operator()(const string& key)
  //  {
  //    return (size_t)key[0];
  //  }
  //};
  //struct StringHashFunc
  //{
  //  size_t operator()(const string& key)
  //  {
  //    return (size_t)key[0];
  //  }
  //};
  template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
  public:
    HashTable()
    {
      _table.resize(10);
    }
    bool Insert(const pair<K, V>& kv)
    {
            //去重
            if(Find(kv.first))
            {
                return false;
            }
      if (10 * _n / _table.size() >= 7)
      {
        size_t newSize = _table.size() * 2;
        //遍历旧表,重新映射到新表
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);
        for (int i = 0; i < _table.size(); i++)
        {
          if (_table[i]._state == EXIST)
          {
            newHT.Insert(_table[i]._kv);
          }
        }
        _table.swap(newHT._table);
      }
      HashFunc hf;
      size_t hashi = hf(kv.first) % _table.size();  
      while (_table[hashi]._state == EXIST)
      {
        hashi++;
        hashi %= _table.size();
      }
      _table[hashi]._kv = kv;
      _table[hashi]._state = EXIST;
      ++_n;
      return true;
    }
    HashDate<const K, V>* Find(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      while (_table[hashi]._state != EMPTY)
      {
        if (_table[hashi]._state == EXIST
          && _table[hashi]._kv.first == key)
        { 
          return (HashDate<const K, V>*) & _table[hashi];
        }
        hashi++;
        hashi %= _table.size();
      }
      return nullptr;
    }
    bool Erase(const K& key)
    {
      HashDate<const K, V>* ret = Find(key);
      if (ret)
      {
        ret->_state = DELETE;
        --_n;
        return true;
      }
      return false;
    }
  private:
    vector<HashDate<K, V>> _table;
    size_t _n = 0;
  };
}

2.开散列—拉链法/哈希桶

  • 开散列概念:
    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中

所以开散列其实就是一个指针数组,关键码对应的值直接挂在对应的下标下面

开散列的基本思路

如下所示,是开散列的基本思路,我们使用一个指针数组来将每个结点给链接上去

namespace hash_bucket
{
  template<class K,class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode<K, V>* _next = nullptr;
    HashNode(const pair<K, V>& kv)
      :_kv(kv)
    {}
  };
  template<class K, class V>
  class HashTable
  {
    typedef HashNode<K,V> Node;
  public:
    HashTable()
      :_n(0)
    {
      _table.resize(10, nullptr);
    }
  private:
    vector<Node*> _table;
    size_t _n;
  };
}
  • 开散列的插入

如下所示,是我们一开始的基本思路,我们先不考虑特殊类型无法取模的问题,我们直接使用头插法,便可以很轻松的完成插入

bool Insert(const pair<K, V>& kv)
    {
      size_t hashi = kv.first % _table.size();
      Node* newnode = new Node(kv);
      newnode->_next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return true;
    }

但是这段代码还存在的问题就是扩容问题。因为我们不可能让这个桶上一直挂数据。

也就是说,不扩容,不断插入,某些桶越来越长,效率得不到保障,但是这里的负载因子可以适当放大一些,一般负载因子在1,平均下俩每个桶一个数据

如果按照我们上面闭散列的逻辑的话,那么就是这样扩容的

一个一个的将值给放进去,但是这样的话,存在一个问题,那就是我们还需要new一些新结点,而原来的结点还需要再释放一下

这样做其实是不太好的,效率比较低。而前面闭散列敢这样做的原因,就是因为不需要new新节点,所以可以这样玩。而这里不能这样做就是需要开新节点了

所以我们最好的策略就是直接把原来的结点给挪用即可

如下就是最终代码,这里我们已经添加了仿函数进行处理特殊类型了。

bool Insert(const pair<K, V>& kv)
    {
            //去重
      if (Find(kv.first))
      {
        return false;
      }
      HashFunc hf;
      if (_n == _table.size())
      {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable(newSize, nullptr);
        for (int i = 0; i < _table.size(); i++)
        {
          Node* cur = _table[i];
          while (cur)
          {
            Node* next = cur->_next;
            size_t hashi = hf(cur->_kv.first) % newTable.size();
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _table[i] = nullptr;
        }
        _table.swap(newTable);
      }
      size_t hashi = hf(kv.first) % _table.size();
      Node* newnode = new Node(kv);
      newnode->_next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return true;
    }

我们使用如下测试用例

void test6()
{
  hash_bucket::HashTable<int, int> ht;
  int a[] = { 1,111,4,15,25,7,44,9 };
  for (auto e : a)
  {
    ht.Insert(make_pair(e, e));
  }
}

监视窗口如下所示

我们也可以写一个print用来展示

void Print()
    {
      for (int i = 0; i < _table.size(); i++)
      {
        Node* cur = _table[i];
        printf("[%d]->", i);
        while (cur)
        {
          cout << cur->_kv.first << "->";
          cur = cur->_next;
        }
        cout << "NULL" << endl;
      }
    }

然后我们的测用例改为如下,可以更加直观的感受扩容

void test6()
{
  hash_bucket::HashTable<int, int> ht;
  int a[] = { 1,111,4,15,25,7,44,9 };
  for (auto e : a)
  {
    ht.Insert(make_pair(e, e));
  }
  ht.Print();
  cout << endl;
  ht.Insert(make_pair(24, 24));
  ht.Insert(make_pair(34, 34));
  ht.Insert(make_pair(54, 54));
  ht.Print();
}

运行结果如下:

  • 开散列的查找
Node* Find(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }
  • 开散列的删除
bool Erase(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      Node* prev = nullptr;
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          if (prev)
          {
            prev->_next = cur->_next;
          }
          else
          {
            _table[hashi] = cur->_next;
          }
          delete cur;
          cur = nullptr;
          _n--;
          return true;
        }
        else
        {
          prev = cur;
          cur = cur->_next;
        }
      }
      return false;
    }

接下来我们来测试一下

void test6()
{
  hash_bucket::HashTable<int, int> ht;
  int a[] = { 1,111,4,15,25,7,44,9 };
  for (auto e : a)
  {
    ht.Insert(make_pair(e, e));
  }
  ht.Print();
  cout << endl;
  ht.Insert(make_pair(24, 24));
  ht.Insert(make_pair(34, 34));
  ht.Insert(make_pair(54, 54));
  ht.Print();
  cout << endl;
  ht.Erase(44);
  ht.Erase(4);
  ht.Erase(24);
  ht.Print();
}

运行结果为

  • 开散列的析构

开散列与闭散列的不同之处在于,他需要写一个析构函数,因为闭散列的数组上都是自定义类型,所以可以不用写析构函数,而开散列的数组上都是一些指针,这些指针都是内置类型,他们指向一段空间, 就需要写上析构函数了

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

我们可以用如下代码来进行测试

void test7()
{
  hash_bucket::HashTable<string, string> dict;
  dict.Insert(make_pair("sort", "排序"));
  dict.Insert(make_pair("insert", "插入"));
  dict.Insert(make_pair("delete", "删除"));
  dict.Insert(make_pair("process", "进程"));
  dict.Insert(make_pair("right", "xxxx"));
  hash_bucket::HashNode<string, string>* ret = dict.Find("right");
  ret->_kv.second = "右边";
  dict.Print();
  cout << endl;
  dict.Erase("sort");
  dict.Print();
}

运行结果为

下面是哈希桶的完整代码:

namespace hash_bucket
{
  template<class K,class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode<K, V>* _next = nullptr;
    HashNode(const pair<K, V>& kv)
      :_kv(kv)
    {}
  };
  template<class K>
  struct DefaultHashFunc
  {
    size_t operator()(const K& key)
    {
      return (size_t)key;
    }
  };
  template<>
  struct DefaultHashFunc<string>
  {
    size_t operator()(const string& str)
    {
      size_t hashi = 0;
      for (auto ch : str)
      {
        hashi = hashi * 131 + ch;
      }
      return hashi;
    }
  };
  template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
    typedef HashNode<K,V> Node;
  public:
    HashTable()
      :_n(0)
    {
      _table.resize(10, nullptr);
    }
    bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
      {
        return false;
      }
      HashFunc hf;
      if (_n == _table.size())
      {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable(newSize, nullptr);
        for (int i = 0; i < _table.size(); i++)
        {
          Node* cur = _table[i];
          while (cur)
          {
            Node* next = cur->_next;
            size_t hashi = hf(cur->_kv.first) % newTable.size();
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _table[i] = nullptr;
        }
        _table.swap(newTable);
      }
      size_t hashi = hf(kv.first) % _table.size();
      Node* newnode = new Node(kv);
      newnode->_next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return true;
    }
    void Print()
    {
      for (int i = 0; i < _table.size(); i++)
      {
        Node* cur = _table[i];
        printf("[%d]->", i);
        while (cur)
        {
          cout << cur->_kv.first << ":" << cur->_kv.second << "->";
          cur = cur->_next;
        }
        cout << "NULL" << endl;
      }
    }
    Node* Find(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }
    bool Erase(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      Node* prev = nullptr;
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          if (prev)
          {
            prev->_next = cur->_next;
          }
          else
          {
            _table[hashi] = cur->_next;
          }
          delete cur;
          cur = nullptr;
          _n--;
          return true;
        }
        else
        {
          prev = cur;
          cur = cur->_next;
        }
      }
      return false;
    }
    ~HashTable()
    {
      for (int i = 0; i < _table.size(); i++)
      {
        Node* cur = _table[i];
        while (cur)
        {
          Node* next = cur->_next;
          delete cur;
          cur = next;
        }
        _table[i] = nullptr;
      }
    }
  private:
    vector<Node*> _table;
    size_t _n;
  };
}
相关文章
|
2月前
|
存储 C++
【C++初阶】第三站:类和对象(中) -- 日期计算器
【C++初阶】第三站:类和对象(中) -- 日期计算器
|
5月前
|
存储 算法 搜索推荐
《探秘C++》No.22 哈希
《探秘C++》No.22 哈希
46 0
|
6月前
|
存储 算法 编译器
【C++从0到王者】第三十九站:C++11(全文三万字,超详解)(上)
【C++从0到王者】第三十九站:C++11(全文三万字,超详解)
71 0
|
5天前
|
存储 算法 数据安全/隐私保护
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
7 0
|
5天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
8 1
|
19天前
|
存储 算法 C++
【C++高阶(六)】哈希的应用--位图&布隆过滤器
【C++高阶(六)】哈希的应用--位图&布隆过滤器
|
19天前
|
存储 Serverless C++
【C++高阶(五)】哈希思想--哈希表&哈希桶
【C++高阶(五)】哈希思想--哈希表&哈希桶
|
2月前
|
存储 编译器 C语言
【C++初阶】第三站:类和对象(中) -- 类的6个默认成员函数-2
【C++初阶】第三站:类和对象(中) -- 类的6个默认成员函数-2
|
2月前
|
编译器 C语言 C++
【C++初阶】第三站:类和对象(中) -- 类的6个默认成员函数-1
【C++初阶】第三站:类和对象(中) -- 类的6个默认成员函数-1
|
2月前
|
存储 C++
哈希的开放定址法的实现【C++】
哈希的开放定址法的实现【C++】