加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 百科 > 正文

STL系列之九 探索hash_set

发布时间：2020-12-13 13:45:42 所属栏目：百科 来源：网络整理
导读：STL系列之九 探索hash_set 分类：STL 他山之石 2012-03-08 11:52 17879人阅读 评论(38) 收藏 举报 table class nosql数据库 insert 数据结构 null 目录(?) [+] Title: STL系列之九 探索hash_set Author: MoreWindows Blog: http://blog.csdn.net/MoreWindows

STL系列之九 探索hash_set

分类：STL 他山之石 2012-03-08 11:52 17879人阅读 评论(38) 收藏 举报
table class nosql数据库 insert 数据结构 null

目录(?)[+]

Title: STL系列之九 探索hash_set

Author: MoreWindows

Blog: http://blog.csdn.net/MoreWindows

E-mail: morewindows@126.com

KeyWord: C++ STL set hash_set 哈希表 链地址法

本文将着重探索hash_set比set快速高效的原因，阅读本文前，推荐先阅读本文的姊妹篇《STL系列之六 set与hash_set》

一．hash_set之基石——哈希表

hash_set的底层数据结构是哈希表，因此要深入了解hash_set，必须先分析哈希表。哈希表是根据关键码值(Key-Value)而直接进行访问的数据结构，它用哈希函数处理数据得到关键码值，关键码值对应表中一个特定位置再由应该位置来访问记录，这样可以在时间复杂性度为O(1)内访问到数据。但是很有可能出现多个数据经哈希函数处理后得到同一个关键码——这就产生了冲突，解决冲突的方法也有很多，各大数据结构教材及考研辅导书上都会介绍大把方法。这里采用最方便最有效的一种——链地址法，当有冲突发生时将具同一关键码的数据组成一个链表。下图展示了链地址法的使用：

二．简化版的hash_table

按照上面的分析和图示，并参考《编程珠玑》第15章中哈希表的实现，不难写出一个简单的哈希表，我们称之为简化版hash_table。该哈希表由一个指针数组组成，数组中每个元素都是链表的表头指针，程序分为hash_table.h，hash_table.cpp和main.cpp。

1.hash_table.h

[cpp] view plain copy
  1. #pragmaonce
  2. #defineNULL0
  3. //简化版hash_table
  4. //byMoreWindows(http://blog.csdn.net/MoreWindows)
  5. structNode
  6. {
  7. intval;
  8. Node*next;
  9. Node(intn)
  10. this->val=n;
  11. this->next=NULL;
  12. }
  13. };
  14. classhash_table
  15. public:
  16. hash_table(constintntablesize);
  17. ~hash_table();
  18. boolinsert(intn);
  19. voidinsert(int*pFirst,int*pLast);
  20. boolfind(intsize();
  21. intHashFun(intm_nTableSize;
  22. intm_nTableDataCount;
  23. Node**m_ppTable;
  24. };

2.hash_table.cpp

copy
    #include"hash_table.h"
  1. #include<malloc.h>
  2. #include<memory.h>
  3. hash_table::hash_table(intntablesize)
  4. {
  5. m_nTableSize=ntablesize;
  6. m_ppTable=(Node**)malloc(sizeof(Node*)*m_nTableSize);
  7. if(m_ppTable==NULL)
  8. return;
  9. m_nTableDataCount=0;
  10. memset(m_ppTable, }
  11. hash_table::~hash_table()
  12. free(m_ppTable);
  13. m_ppTable=NULL;
  14. m_nTableDataCount=0;
  15. m_nTableSize=0;
  16. intinlinehash_table::HashFun(intn)
  17. return(n^0xdeadbeef)%m_nTableSize;
  18. inthash_table::size()
  19. returnm_nTableDataCount;
  20. boolhash_table::insert(intkey=HashFun(n);
  21. //在该链表中查找该数是否已经存在
  22. for(Node*p=m_ppTable[key];p!=NULL;p=p->next)
  23. if(p->val==n)
  24. returntrue;
  25. //在链表的头部插入
  26. Node*pNode=newNode(n);
  27. if(pNode==NULL)
  28. false;
  29. pNode->next=m_ppTable[key];
  30. m_ppTable[key]=pNode;
  31. m_nTableDataCount++;
  32. boolhash_table::find(for(Node*pNode=m_ppTable[key];pNode!=NULL;pNode=pNode->next)
  33. if(pNode->val==n)
  34. true;
  35. voidhash_table::insert(int*pLast)
  36. for(int*p=pFirst;p!=pLast;p++)
  37. this->insert(*p);
  38. }

3．main.cpp

在main.cpp中，对set、hash_set、简化版hash_table作一个性能测试，测试环境为Win7+VS2008的Release设置（下同）。

copy
    //测试set，hash_set及简化版hash_table
  1. #include<set>
  2. #include<hash_set>
  3. #include<iostream>
  4. #include<ctime>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. usingnamespacestd;
  8. namespacestdext;//hash_set
  9. voidPrintfContainerElapseTime(char*pszContainerName,87); background-color:inherit; font-weight:bold">char*pszOperator,87); background-color:inherit; font-weight:bold">longlElapsetime)
  10. printf("%s的%s操作用时%d毫秒n",pszContainerName,pszOperator,lElapsetime);
  11. //MAXN个数据MAXQUERY次查询
  12. intMAXN=5000000,MAXQUERY=5000000;
  13. inta[MAXN],query[MAXQUERY];
  14. intmain()
  15. printf("setVShash_setVShash_table(简化版)性能测试n");
  16. printf("数据容量%d个查询次数%d次n",MAXN,MAXQUERY);
  17. intMAXNUM=MAXN*4;
  18. intMAXQUERYNUM=MAXN*4;
  19. printf("容器中数据范围[0,%d)查询数据范围[0,%d)n",MAXNUM,MAXQUERYNUM);
  20. printf("--byMoreWindows(http://blog.csdn.net/MoreWindows)--nn");
  22. //随机生成在[0,MAXNUM)范围内的MAXN个数
  23. inti;
  24. srand((unsignedint)time(NULL));
  25. for(i=0;i<MAXN;++i)
  26. a[i]=(rand()*rand())%MAXNUM;
  28. for(i=0;i<MAXQUERY;++i)
  29. query[i]=(rand()*rand())%MAXQUERYNUM;
  30. set<int>nset;
  31. hash_set<int>nhashset;
  32. hash_tablenhashtable(MAXN+123);
  33. clock_tclockBegin,clockEnd;
  35. //insert
  36. printf("-----插入数据-----------n");
  37. clockBegin=clock();
  38. nset.insert(a,a+MAXN);
  39. clockEnd=clock();
  40. printf("set中有数据%d个n",nset.size());
  41. PrintfContainerElapseTime("set","insert",clockEnd-clockBegin);
  42. nhashset.insert(a,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> printf("hash_set中有数据%d个n",nhashset.size());
  43. PrintfContainerElapseTime("hash_set",153); background-color:inherit; font-weight:bold">for(i=0;i<MAXN;i++)
  44. nhashtable.insert(a[i]);
  45. clockEnd=clock();
  46. printf("hash_table中有数据%d个n",nhashtable.size());
  47. PrintfContainerElapseTime("Hash_table",clockEnd-clockBegin);
  48. //find
  49. printf("-----查询数据-----------n");
  50. intnFindSucceedCount,nFindFailedCount;
  51. nFindSucceedCount=nFindFailedCount=0;
  52. clockBegin=clock();
  53. if(nset.find(query[i])!=nset.end())
  54. ++nFindSucceedCount;
  55. else
  56. ++nFindFailedCount;
  57. "find",248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> printf("查询成功次数：%d查询失败次数：%dn",nFindSucceedCount,nFindFailedCount);
  58. nFindSucceedCount=nFindFailedCount=0;
  59. for(i=0;i<MAXQUERY;++i)
  60. if(nhashset.find(query[i])!=nhashset.end())
  61. ++nFindSucceedCount;
  62. else
  63. ++nFindFailedCount;
  64. PrintfContainerElapseTime("hash_set",108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> printf("查询成功次数：%d查询失败次数：%dn",nFindFailedCount);
  65. if(nhashtable.find(query[i]))
  66. PrintfContainerElapseTime("hash_table",153); background-color:inherit; font-weight:bold">return0;
  67. }

在数据量为500万时测试结果如下：

从程序运行结果可以发现，我们自己实现的hash_table（简化版）在插入和查找的效率要远高于set。为了进一步分析，最好能统计hash_table中的各个链表的长度情况，这样可以有效的了解平均每次查找要访问多少个数据。写出统计hash_table各链表长度的函数如下：

copy
    //byMoreWindows(http://blog.csdn.net/MoreWindows)
  1. voidStatisticHashTable(hash_table&ht)
  2. intMAXLISTLINE=100;
  3. inti,a[MAXLISTLINE],nExtendListNum;
  4. nExtendListNum=0;
  5. memset(a,153); background-color:inherit; font-weight:bold">sizeof(a[0])*MAXLISTLINE);
  6. for(i=0;i<ht.m_nTableSize;i++)
  7. intsum=0;
  8. for(Node*p=ht.m_ppTable[i];p!=NULL;p=p->next)
  9. ++sum;
  10. if(sum>=MAXLISTLINE)
  11. nExtendListNum++;
  12. a[sum]++;
  13. printf("hash_table中链表长度统计：n");
  14. for(i=0;i<MAXLISTLINE;i++)
  15. if(a[i]>0)
  16. printf("长度为%d的链表有%d个这些链表中数据占总数据的%.2lf%%n",i,a[i],(a[i]*i*100.0)/ht.size());
  17. printf("长度超过%d的链表有%d个n",MAXLISTLINE,nExtendListNum);
  18. }

用此段代码得到链表长度的统计结果：

可以发现在hash_table中最长的链表也只有5个元素，长度为1和长度为2的链表中的数据占全部数据的89%以上。因此绝大数查询将仅仅访问哈希表1次到2次。这样的查询效率当然会比set（内部使用红黑树——类似于二叉平衡树）高的多。有了这个图示，无疑已经可以证明hash_set会比set快速高效了。但hash_set还可以动态的增加表的大小，因此我们再实现一个表大小可增加的hash_table。

三．强化版hash_table

首先来看看VS2008中hash_set是如何实现动态的增加表的大小，hash_set是在hash_set.h中声明的，在hash_set.h中可以发现hash_set是继承_Hash类的，hash_set本身并没有太多的代码，只是对_Hash作了进一步的封装，这种做法在STL中非常常见，如stack栈和queue单向队列都是以deque双向队列作底层数据结构再加一层封装。

_Hash类的定义和实现都在xhash.h类中，微软对_Hash类的第一句注释如下——

hash table -- list with vector of iterators for quick access。

哈哈，这句话说的非常明白。这说明_Hash实际上就是由vector和list组成哈希表。再阅读下代码可以发现_Hash类增加空间由_Grow()函数完成，当空间不足时就倍增，并且表中原有数据都要重新计算hash值以确定新的位置。

知道了_Hash类是如何运作的，下面就来考虑如何实现强化版的hash_table。当然有二个地方还可以改进：

1．_Hash类使用的list为双向链表，但在在哈希表中使用普通的单链表就可以了。因此使用STL中的vector再加入《STL系列之八 slist单链表》一文中的slist来实现强化版的hash_table。

2．在空间分配上使用了一个近似于倍增的素数表，最开始取第一个素数，当空间不足时就使用下一个素数。经过实际测试这种效果要比倍增法高效一些。

在这二个改进之上的强化版的hash_table代码如下：

copy
    //使用vector<slist<T>>为容器的hash_table
  1. template<classT,classcontainer=vector<slist<T>>>
  2. classhash_table
  3. public:
  4. hash_table();
  5. voidclear();
  6. boolinsert(T&n);
  7. voidinsert(T*pFirst,T*pLast);
  8. boolerase(T&n);
  9. voidresize(intnNewTableSize);
  10. boolfind(T&n);
  11. intsize();
  12. intHashFun(T&n);
  13. private:
  14. staticintfindNextPrime(intcurPrime);
  15. intm_nDataCount;
  16. containerm_Table;
  17. staticconstunsignedintm_primes[50];
  18. };
  19. //素数表
  20. classcontainer>
  21. inthash_table<T,container>::m_primes[50]={
  22. 53,97,193,389,769,1453,3079,6151,1289,24593,49157,98317,
  23. 196613,393241,786433,1572869,3145739,6291469,12582917,
  24. 25165843,50331653,100663319,201326611,-1
  25. inlinehash_table<T,container>::HashFun(T&n)
  26. classcontainer>
  27. hash_table<T,container>::hash_table()
  28. m_nDataCount=0;
  29. m_nTableSize=m_primes[0];
  30. m_Table.resize(m_nTableSize);
  31. hash_table<T,container>::hash_table( m_nDataCount=0;
  32. m_nTableSize=ntablesize;
  33. m_Table.resize(m_nTableSize);
  34. clear();
  35. voidhash_table<T,container>::clear()
  36. inti=0;i<m_nTableSize;i++)
  37. m_Table[i].clear();
  38. boolhash_table<T,container>::insert(T&n)
  39. intkey=HashFun(n);
  40. if(!m_Table[key].find(n))
  41. m_nDataCount++;
  42. m_Table[key].push_front(n);
  43. if(m_nDataCount>=m_nTableSize)
  44. resize(findNextPrime(m_nTableSize));
  45. if(m_Table[key].remove(n))
  46. m_nDataCount--;
  47. for(T*p=pFirst;p!=pLast;p++)
  48. intnNewTableSize)
  49. if(nNewTableSize<=m_nTableSize)
  50. intnOldTableSize=m_nTableSize;
  51. m_nTableSize=nNewTableSize;
  52. containertempTable(m_nTableSize);//创建一个更大的表
  53. inti=0;i<nOldTableSize;i++)//将原表中数据重新插入到新表中
  54. Node<T>*cur=m_Table[i].m_head;
  55. while(cur!=NULL)
  56. intkey=HashFun(cur->val);
  57. Node<T>*pNext=cur->next;
  58. cur->next=tempTable[key].m_head;
  59. tempTable[key].m_head=cur;
  60. cur=pNext;
  61. m_Table[i].m_head=NULL;
  62. m_Table.swap(tempTable);
  63. returnm_nDataCount;
  64. returnm_Table[key].find(n);
  65. //在素数表中找到比当前数大的最小数
  66. intcurPrime)
  67. unsignedint*pStart=(unsignedint*)m_primes;
  68. while(*pStart<=curPrime)
  69. ++pStart;
  70. return*pStart;
  71. }

下面再对set、hash_set、强化版hash_table的性能测试：

测试结果一（数据量500万）：

测试结果二（数据量1千万）：

测试结果三（数据量1千万）：

可以看出，由于强化版hash_table的哈希表在增加表空间大小时会花费额外的一些时间，所以插入数据的用时与STL提供的hash_set用时相差不多了。但查找还是比hash_set要快的一些。

四．结语

从简化版到强化版的hash_table，我们不仅知道了hash_set底层数据结构——哈希表的运作机制，还知道了如何实现大小动态变化的哈希表。达到了本文让读者了解hash_set快速高效的原因。当然本文所给hash_table距真正的hash_set还有不小的距离，有兴趣的读者可以进一步改进。

此外，本文所示范的哈希表也与最近流行的NoSql数据库颇有渊源， NoSql数据库也是通过Key-Value方式来访问数据的（访问数据的方式上非常类似哈希表），其查找效率与传统的数据库相比也正如本文中hast_set与set的比较。正因为NoSql数据库在基础数据结构上的天然优势，所以它完全可以支持海量数据的查询修改且对操作性能要求很高场合如微博等。

转载请标明出处，原文地址：http://www.52php.cn/article/p-vhcartng-yt.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同