STL系列之九 探索hash_set

NoSQL 前端之家
前端之家收集整理的这篇文章主要介绍了STL系列之九 探索hash_set，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

STL系列之九 探索hash_set

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

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)--\n\n");
  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查询失败次数：%d\n",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查询失败次数：%d\n",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.jb51.cc/article/p-vhcartng-yt.html

猜你在找的NoSQL相关文章

Redis进阶实践之十八 使用管道模式提高Redis查询的速度
一、引言 学习redis 也有一段时间了，该接触的也差不多了。后来有一天，以前的同事问我，如...
MongoDb进阶实践之二 如何在Windows上安装和配置MongoDB
一、引言 上一篇文章，我介绍了如何在Linux系统上安装和配置MongoDB，其实都不是很难，不需...
Redis进阶实践之十七 Redis协议的规范
一、介绍 Redis客户端使用RESP（Redis的序列化协议）协议与Redis的服务器端进行通信。 虽然...
Redis进阶实践之十九 Redis如何使用lua脚本
一、引言 redis学了一段时间了，基本的东西都没问题了。从今天开始讲写一些redis和lua脚本...
Redis进阶实践之十五 Redis-cli命令行工具使用详解第二部分（结束）
一、介绍 今天继续redis-cli使用的介绍，上一篇文章写了一部分，写到第9个小节，今天就来完...
Redis进阶实践之十四 Redis-cli命令行工具使用详解第一部分
一、介绍 redis学了有一段时间了，以前都是看视频，看教程，很少看官方的东西。现在redis的...
MongoDb进阶实践之七 MongoDB的索引入门
一、引言 好久没有写东西了，MongoDB系列的文章也丢下好长时间了。今天终于有时间了，就写...
Memcached在Linux环境下的使用详解
一、引言 写有关NoSQL数据库有关的文章已经有一段时间了，可以高兴的说，Redis暂时就算写完...
Redis进阶实践之二十 Redis的配置文件使用详解
一、引言 写完上一篇有关redis使用lua脚本的文章，就有意结束Redis这个系列的文章了，当然...
Redis进阶实践之十二 Redis的Cluster集群动态扩容
一、引言 上一篇文章我们一步一步的教大家搭建了Redis的Cluster集群环境，形成了3个主节点...
MySQLMsSQLOracleSqlitePostgre SQLMariadbMongoDBNoSQLHBaseJDBC
undo日志persistent-cmysql-error-postal-codesql-match-almysql-5.6mysql-8.0database-tri安装路径系统错误data_dir丢失文件主从同步sql_mode数据库目录匿名用户character_seID归零数据库位置查询表重复字段查询字段截断日志SUSPECT7391Remote ServeLinked Serve玄学问题登录不上开启远程访问