devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++_Hash容器总结_c++ hash

作者：木道寻08 | 2024-07-11 01:28:56

赞

踩

c++ hash

目录

一、Hash基本概念

1.1 散列函数

(1) 除法散列法(除留余数法)

(2) 平方散列法(平方取中法)

(3) 斐波那契（Fibonacci）散列法

1.2 解决hash冲突

二、C++中Hash数据结构引入的发展历史

2.1 下面是摘自《Boost程序库完全开放指南》

2.2 下面一段摘自《C++标准库扩展权威指南》

三、各种库对Hash的实现

3.1 SGI STL中提供提供的与hash相关的数据结构

(1) hash_set 容器

(2) hash_map容器

(3) hash_multiset与hash_multimap

(4) hash函数

3.2 TR1(C++11)中提供的与hash相关的数据结构

(1)  散列集合（各类set）简介

(2) 散列集合（各类set）用法

(3) 散列映射（各类map）简介

(4) 散列映射（各类map）的用法

(5) TR1中提供了一个函数对象hash, 可以进行映射.

(6)  如何支持自定义类型

(7) unordered库的内部结构

一、Hash基本概念

散列表 Hash Table由散列函数所产生的一种数据结构，是一种非常重要的数据结构. 散列函数（或称 Hash函数）是一种特殊的映射函数。

散列表（哈希表、hash表）是用于存储动态集的一种非常有效的数据结构。通过散列函数h(key)的计算结果，直接得到key关键字表示的元素的存储位置。散列技术中，可能会有两个不同的key1和key2，通过h(key)计算得到的地址如果是一样的，就发生了冲突。散列技术中 哈希函数h(key)的设计 和 哈希冲突如何解决是hash中最关键的两个问题。

1.1 散列函数

散列函数要求（1）能快速的计算；（2) 计算结果分布要均匀。(hash function 设计的一条主要原则是：尽量让不同的key算出的结果不同。)

散列函数有如下几种常用的：（1） 除留余数法；（2） 平方取中法；（3） 折叠法；（4） 数字分析法。

(1) 除法散列法(除留余数法)

最直观的一种，上图使用的就是这种散列法，公式：

index = value % 16

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫"除法散列法"。

(2) 平方散列法(平方取中法)

求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：

index = (value * value) >> 28

如果数值分配比较均匀的话这种方法能得到不错的结果，但还有个问题，value如果很大，value * value会溢出的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。

(3) 斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。

(1)，对于16位整数而言，这个乘数是40503

(2)，对于32位整数而言，这个乘数是2654435769

(3)，对于64位整数而言，这个乘数是11400714819323198485

这几个"理想乘数"是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列.

对我们常见的32位整数而言，公式：

index = (value * 2654435769) >> 28

1.2 解决hash冲突

解决冲突的方法有：

  • (1) 拉链法 (开散列法)：采用 linked list, 冲突的时候就在每个位置（数组）上往下挂（链表）。
  • (2) 开地址法 (闭散列法)：有的地方也称 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址；或者说 你占了我的位置，我就去别的(下一个+1 或者 + 10)位置。）

拉链法是通过在各地址构建一个链表来解决多元素同地址的问题。

开地址法根据探查序列的不同，又分为（1）线性探查法；（2） 二次探查法；（3） 双散列法。等，其中线性探查法会发生基本聚集，为解决基本聚集采用二次探查法，不过其也会发生二次聚集，双散列法可消除二次聚集。

二、C++中Hash数据结构引入的发展历史

C++对这种数据结构提供了很好的支持。

现代C++最主要的一个特点就是使用STL. STL是C++标准化时所产生的一个非常好的标准模板库. 模板编程带来了C++编程的一个变革. 但是STL的制定还是花费了很长的时间的. 在制定STL的过程中, 曾经有C++标准委员会的委员提出将Hash数据结构加入到STL中,但是,该提案提出的时间比较晚, C++标准委员会不想再将标准完成的时间拖延下去, 所以没有将Hash加入到最初的STL中去. 所以在最初的STL中, 我们只能看到vector, list, set, map 等容器. 但是之后的hash相关的容器加入到了C++的TR1库中去了。 TR1 库是准备在C++0x标准时转化为新的C++标准. 现在新的C++标准已经制定完毕, 是C++11. Hash相关的数据结构也已经从TR1中加入。

(C++ TR1: 全称Technical Report 1，是针对C++标准库的第一次扩展。即将到来的下一个版本的C++标准c++0x会包括它，以及一些语言本身的扩充。tr1包括大家期待已久的smart pointer，正则表达式以及其他一些支持范型编程的内容。草案阶段，新增的类和模板的名字空间是std::tr1)
 

其实在hash相关的容器进入TR1之前, C++编译器的其他厂商就已经实现了自己的hash容器了. 一般这些容器的命名都是hash_set 或hash_map, 这其中最著名的就是SGI 的STL中所实现的hash容器. 其实这也导致了以后C++标准中对hash容器命名的变化. 为了与之前的名称区别开来, C++标准委员会将标准中的容器命名为unordered_set和unordered_map.

C++还有一个比较著名库是boost库, 其实C++标准中的hash容器都是从boost中转化来的.

2.1 下面是摘自《Boost程序库完全开放指南》

2.2 下面一段摘自《C++标准库扩展权威指南》

三、各种库对Hash的实现

3.1 SGI STL中提供提供的与hash相关的数据结构

SGI STL中提供了4个容器: hash_set, hash_map, hash_multiset, hash_multimap

还有一个hash函数:hash

在linux和Windows平台上, 对SGISTL的使用有些差别:

在Linux下g++的形式:

头文件:: #include <ext/hash_map>

命名空间:: using namespace __gnu_cxx;

使用方法上和map没有什么大的区别，

  1. #include <ext/hash_map>
  2. using namespace __gnu_cxx;
  3. hash_map<key_type,value_type> obj;
  4. hash_map<key_type,value_type>::iterator iter = obj.begin();

在Windows下VC++的形式:

和map的使用方法一样，没有命名空间，直接#include <hash_map>就可以使用了，就像直接#include <map>一样。

(1) hash_set 容器

容器声明: hash_set<Key, HashFcn, EqualKey, Alloc>

简单的示例程序如下:

  1. #include <iostream>
  2. #include <ext/hash_set>
  3. #include <cstring>
  4. using namespace std;
  5. using namespace __gnu_cxx;
  6. struct eqstr
  7. {
  8.   bool operator()(const char* s1, const char* s2) const
  9.   {
  10.     return strcmp(s1, s2) == 0;
  11.   }
  12. };
  13. void lookup(const hash_set<const char*, hash<const char*>, eqstr>& Set,      const char* word)
  14. {
  15.   hash_set<const char*, hash<const char*>, eqstr>::const_iterator it
  16.     = Set.find(word);
  17.   cout << word << ": "
  18.        << (it != Set.end() ? "present" : "not present")
  19.        << endl;
  20. }
  21.  
  22. int main()
  23. {
  24.   hash_set<const char*, hash<const char*>, eqstr> Set;
  25.   Set.insert("kiwi");
  26.   Set.insert("plum");
  27.   Set.insert("apple");
  28.   Set.insert("mango");
  29.   Set.insert("apricot");
  30.   Set.insert("banana");
  31.  
  32.   lookup(Set, "mango");
  33.   lookup(Set, "apple");
  34.   lookup(Set, "durian");
  35. }

(2) hash_map容器

容器声明: hash_map<Key, Data, HashFcn, EqualKey, Alloc>

简单的示例程序:

  1. #include <ext/hash_map>                                          
  2.  #include <iostream>
  3.  #include <cstring>
  4.  using namespace std;
  5.  using namespace __gnu_cxx;
  6.  struct eqstr
  7.  {
  8.      bool operator()(const char* s1, const char* s2) const
  9.      {
  10.          return strcmp(s1, s2) == 0;
  11.      }
  12.  };
  13.   int main()
  14.  {
  15.      hash_map<const char*, int, hash<const char*>, eqstr> months;
  16.  
  17.      months["january"] = 31;
  18.      months["february"] = 28;
  19.      months["march"] = 31;
  20.      months["april"] = 30;
  21.      months["may"] = 31;
  22.      months["june"] = 30;
  23.      months["july"] = 31;
  24.      months["august"] = 31;
  25.      months["september"] = 30;
  26.      months["october"] = 31;
  27.      months["november"] = 30;
  28.      months["december"] = 31;
  29.  
  30.      cout << "september -> " << months["september"] << endl;
  31.      cout << "april     -> " << months["april"] << endl;
  32.      cout << "june      -> " << months["june"] << endl;
  33.      cout << "november  -> " << months["november"] << endl;
  34.  }

(3) hash_multiset与hash_multimap

其他的hash_multiset和hash_multimap与上面的两个类似.

(4) hash函数

这里所提供的hash函数是用函数对象的方式提供的: hash<T>

注意,这里的实例化类型是有限制的,即T只能采用下面的类型:

char*,const char*, char,signed char,unsigned char,short,unsigned short,int,unsigned int,long,unsigned long

下面的一个例子是对char*型字符串进行hash:

  1. #include <iostream>
  2. #include <ext/hash_set>                               
  3. #include <cstdlib>
  4. #include <string>
  5. using namespace std;
  6. using namespace __gnu_cxx;
  7. int main(){
  8.     const string alpha="abcdefghijklmnopqrstuvwxyz";
  9.     const int N=10;
  10.     string s(N,' ');
  11.     hash<const char*> H;
  12.     for(int i=0;i<30;i++){
  13.         for(int j=0;j<N;j++){
  14.             s[j]=alpha[rand()%26];
  15.         }
  16.         cout<<s<<" -> "<<H(s.c_str())<<endl;
  17.     }
  18. }

3.2 TR1(C++11)中提供的与hash相关的数据结构

因为新的C++标注还没有普及开来, 所以我们现在是采用TR1库.

(1)  散列集合（各类set）简介

成员类型如下:

成员函数如下:

(2) 散列集合（各类set）用法

unordered_set的一个示例程序如下:

  1. #include <iostream>
  2.  #include <tr1/unordered_set>
  3.  #include <string>
  4.  using namespace std;
  5.  using namespace std::tr1;
  6.  
  7.  int main ()
  8.  {
  9.     const char* arr[] = {"Mercury","Venus","Earth","Mars","Jupiter"," Saturn","Uranus","Neptune"};
  10.     int sz=sizeof(arr)/sizeof(char*);
  11.  unordered_set<string> myset(arr,arr+sz);
  12.      unsigned n = myset.bucket_count();
  13.  
  14.      cout << "myset has " << n << " buckets.\n";
  15.      unordered_set<string>::const_iterator it;
  16.      for(it=myset.begin();it!=myset.end();++it)
  17.          cout<<*it<<' ';
  18.      cout<<endl;
  19.  
  20.      for (unsigned i=0; i<n; ++i) {
  21.          cout << "bucket #" << i << " contains:";
  22.          unordered_set<string>::const_local_iterator it;
  23.          for (it=myset.begin(i); it!=myset.end(i); ++it)
  24.              std::cout << " " << *it;                                
  25.          cout<<endl;
  26.      }
  27.     
  28.      return 0;
  29.  }

程序输出:

从这儿可以知道, unordered_set中可以对其内部结构bucket进行操作. 并且begin(i)的返回值是一个const_local_iterator

(3) 散列映射（各类map）简介

成员类型如下:

成员函数如下:

(4) 散列映射（各类map）的用法

下面是一个简单的例子:

  1. ​
  2. #include <iostream>
  3. #include <string>
  4. #include <tr1/unordered_map>
  5. using namespace std;
  6. using namespace std::tr1;
  7.  
  8. int main ()
  9. {
  10.     const char* mm[][2]={
  11.             {"house","maison"},
  12.             {"apple","pomme"},
  13.             {"tree","arbre"},
  14.             {"book","livre"},
  15.             {"door","porte"},
  16.             {"grapefruit","pamplemousse"}
  17.     };
  18.     int sz=6;
  19.   unordered_map<string,string> mymap;
  20.   for(int i=0;i<sz;i++)
  21.       mymap.insert(unordered_map<string,string>::value_type(mm[i][0],mm[i][1]));
  22.  
  23.   unsigned n = mymap.bucket_count();
  24.   cout << "mymap has " << n << " buckets.\n";
  25.   unordered_map<string,string>::const_iterator it;
  26.   for(it=mymap.begin();it!=mymap.end();++it)
  27.       cout << "[" << it->first << ":" << it->second << "] ";
  28.   cout<<endl;
  29.  
  30.   for (unsigned i=0; i<n; ++i) {
  31.     cout << "bucket #" << i << " contains: ";
  32.   unordered_map<string,string>::const_local_iterator it;
  33.     for (it = mymap.begin(i); it!=mymap.end(i); ++it)
  34.       cout << "[" << it->first << ":" << it->second << "] ";
  35.     cout << "\n";
  36.   }
  37.  
  38.   return 0;
  39. }
  40.  
  41.  
  42.  
  43. ​

输出如下:

这儿需要注意是如何进行元素的插入的.

(5) TR1中提供了一个函数对象hash, 可以进行映射.

其定义如下:

  1.   template<typename _Tp>
  2.     struct hash : public std::unary_function<_Tp, size_t>
  3.     {
  4.       size_t
  5.       operator()(_Tp __val) const;
  6.     };
  7.  
  8.   /// Partial specializations for pointer types.
  9.   template<typename _Tp>
  10.     struct hash<_Tp*> : public std::unary_function<_Tp*, size_t>
  11.     {
  12.       size_t
  13.       operator()(_Tp* __p) const
  14.       { return reinterpret_cast<size_t>(__p); }
  15.     };
  16.  
  17.   /// Explicit specializations for integer types.
  18. #define _TR1_hashtable_define_trivial_hash(_Tp)     \
  19.   template<>                        \
  20.     inline size_t                    \
  21.     hash<_Tp>::operator()(_Tp __val) const        \
  22.     { return static_cast<size_t>(__val); }
  23.  
  24.   _TR1_hashtable_define_trivial_hash(bool);
  25.   _TR1_hashtable_define_trivial_hash(char);
  26.   _TR1_hashtable_define_trivial_hash(signed char);
  27.   _TR1_hashtable_define_trivial_hash(unsigned char);
  28.   _TR1_hashtable_define_trivial_hash(wchar_t);
  29.   _TR1_hashtable_define_trivial_hash(short);
  30.   _TR1_hashtable_define_trivial_hash(int);
  31.   _TR1_hashtable_define_trivial_hash(long);
  32.   _TR1_hashtable_define_trivial_hash(long long);
  33.   _TR1_hashtable_define_trivial_hash(unsigned short);
  34.   _TR1_hashtable_define_trivial_hash(unsigned int);
  35.   _TR1_hashtable_define_trivial_hash(unsigned long);
  36.   _TR1_hashtable_define_trivial_hash(unsigned long long);
  37.  
  38. #undef _TR1_hashtable_define_trivial_hash
  39.  
  40.   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
  41.   // (Used by the next specializations of std::tr1::hash.)
  42.  
  43.   /// Dummy generic implementation (for sizeof(size_t) != 4, 8).
  44.   template<size_t>
  45.     struct _Fnv_hash_base
  46.     {
  47.       template<typename _Tp>
  48.         static size_t
  49.         hash(const _Tp* __ptr, size_t __clength)
  50.         {
  51.       size_t __result = 0;
  52.       const char* __cptr = reinterpret_cast<const char*>(__ptr);
  53.       for (; __clength; --__clength)
  54.         __result = (__result * 131) + *__cptr++;
  55.       return __result;
  56.     }
  57.     };
  58.  
  59.   template<>
  60.     struct _Fnv_hash_base<4>
  61.     {
  62.       template<typename _Tp>
  63.         static size_t
  64.         hash(const _Tp* __ptr, size_t __clength)
  65.         {
  66.       size_t __result = static_cast<size_t>(2166136261UL);
  67.       const char* __cptr = reinterpret_cast<const char*>(__ptr);
  68.       for (; __clength; --__clength)
  69.         {
  70.           __result ^= static_cast<size_t>(*__cptr++);
  71.           __result *= static_cast<size_t>(16777619UL);
  72.         }
  73.       return __result;
  74.     }
  75.     };
  76.   
  77.   template<>
  78.     struct _Fnv_hash_base<8>
  79.     {
  80.       template<typename _Tp>
  81.         static size_t
  82.         hash(const _Tp* __ptr, size_t __clength)
  83.         {
  84.       size_t __result
  85.         = static_cast<size_t>(14695981039346656037ULL);
  86.       const char* __cptr = reinterpret_cast<const char*>(__ptr);
  87.       for (; __clength; --__clength)
  88.         {
  89.           __result ^= static_cast<size_t>(*__cptr++);
  90.           __result *= static_cast<size_t>(1099511628211ULL);
  91.         }
  92.       return __result;
  93.     }
  94.     };
  95.  
  96.   struct _Fnv_hash
  97.   : public _Fnv_hash_base<sizeof(size_t)>
  98.   {
  99.     using _Fnv_hash_base<sizeof(size_t)>::hash;
  100.  
  101.     template<typename _Tp>
  102.       static size_t
  103.       hash(const _Tp& __val)
  104.       { return hash(&__val, sizeof(__val)); }
  105.   };
  106.  
  107.   /// Explicit specializations for float.
  108.   template<>
  109.     inline size_t
  110.     hash<float>::operator()(float __val) const
  111.     {
  112.       // 0 and -0 both hash to zero.
  113.       return __val != 0.0f ? std::tr1::_Fnv_hash::hash(__val) : 0;
  114.     }
  115.  
  116.   /// Explicit specializations for double.
  117.   template<>
  118.     inline size_t
  119.     hash<double>::operator()(double __val) const
  120.     {
  121.       // 0 and -0 both hash to zero.
  122.       return __val != 0.0 ? std::tr1::_Fnv_hash::hash(__val) : 0;
  123.     }

从上面的类可以看到类hash是一个模板函数,并且进行了模板特化.

对于整型(包括char, short, int和long等)是直接使用其自己的值(使用了static_cast强制转换), 对于浮点型(float, double等)是进行了一些变化得到映射值.

(6)  如何支持自定义类型

一个自定义的例子:

  1. #include <iostream>
  2. #include <tr1/unordered_set>
  3. #include <string>
  4. #include <cstdlib>
  5. using namespace std;
  6. using namespace std::tr1;
  7. struct demo{
  8.     int a;
  9.     demo(int i):a(i){}
  10. };
  11. bool operator==(const demo& lhs,const demo& rhs){
  12.     return lhs.a==rhs.a;
  13. }
  14. ostream& operator<<(ostream& os,const demo& s){
  15.     os<<"<"<<s.a<<">";
  16. }
  17. size_t hash_value(demo& s){
  18.     return hash<int>()(s.a);
  19. }
  20. namespace std{
  21.     namespace tr1{
  22.         template<>
  23.             struct hash<demo>{
  24.                 size_t operator()(const demo&s)const{
  25.                     return hash<int>()(s.a);
  26.                 }
  27.             };
  28.     }
  29. }
  30. int main(){
  31.     int a[]={3,7,5,-3,-4};
  32.     int sz=sizeof(a)/sizeof(int);
  33.     cout<<sz<<endl;
  34.     unordered_set<demo,hash<demo> > us(a,a+sz);
  35.     unordered_set<demo,hash<demo> >::const_iterator it;
  36.     for(it=us.begin();it!=us.end();++it)
  37.         cout<<*it<<' ';
  38.     cout<<endl;
  39.     unsigned n = us.bucket_count();
  40.     for (unsigned i=0; i<n; ++i) {
  41.         cout << "bucket #" << i << " contains:";
  42.         unordered_set<demo,hash<demo> >::const_local_iterator it;
  43.         for (it=us.begin(i); it!=us.end(i); ++it)
  44.             cout << " " << *it;
  45.         cout<<endl;
  46.     }
  47.     cout<<"======================================"<<endl;
  48.     us.clear();
  49.     int N=20;
  50.     for(int i=0;i<N;i++){
  51.         int val=rand()%1000;
  52.         us.insert(val);
  53.     }
  54.     for(it=us.begin();it!=us.end();++it)
  55.         cout<<*it<<' ';
  56.     cout<<endl;
  57.     n = us.bucket_count();
  58.     for (unsigned i=0; i<n; ++i) {
  59.         cout << "bucket #" << i << " contains:";
  60.         unordered_set<demo,hash<demo> >::const_local_iterator it;
  61.         for (it=us.begin(i); it!=us.end(i); ++it)
  62.             cout << " " << *it;
  63.         cout<<endl;
  64.     }
  65.     
  66. }

输出结果如下:

(7) unordered库的内部结构

参考 :  C++中的Hash容器总结

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/808334
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号