本文共 7389 字，大约阅读时间需要 24 分钟。
一，set和hash_set简介
在STL中，set是以红黑树（RB-Tree）作为底层数据结构的，hash_set是以哈希表（Hash table）作为底层数据结构的。set可以在时间复杂度为O（logN）的情况下插入，删除和查找数据。hash_set操作的时间度则比较复杂，取决于哈希函数和哈希表的负载情况。
二，SET使用范例（hash_set类似）
1 #include2 #include 3 #include 4 using namespace std; 5 6 int main() 7 { 8 const int MAXN = 15; 9 int a[MAXN];10 int i;11 srand(time(NULL));12 for (i = 0; i < MAXN; ++i)13 a[i] = rand() % (MAXN * 2);14 15 set iset; 16 set ::iterator pos; 17 18 //插入数据 insert()有三种重载19 iset.insert(a, a + MAXN);20 21 //当前集合中个数 最大容纳数据量22 printf("当前集合中个数: %d 最大容纳数据量: %d\n", iset.size(), iset.max_size());23 24 //依次输出25 printf("依次输出集合中所有元素-------\n");26 for (pos = iset.begin(); pos != iset.end(); ++pos)27 printf("%d ", *pos);28 putchar('\n');29 30 //查找31 int findNum = MAXN;32 printf("查找 %d是否存在-----------------------\n", findNum);33 pos = iset.find(findNum);34 if (pos != iset.end())35 printf("%d 存在\n", findNum);36 else37 printf("%d 不存在\n", findNum);38 39 //在最后位置插入数据，如果给定的位置不正确，会重新找个正确的位置并返回该位置40 pos = iset.insert(--iset.end(), MAXN * 2); 41 printf("已经插入%d\n", *pos);42 43 //删除44 iset.erase(MAXN);45 printf("已经删除%d\n", MAXN);46 47 //依次输出48 printf("依次输出集合中所有元素-------\n");49 for (pos = iset.begin(); pos != iset.end(); ++pos)50 printf("%d ", *pos);51 putchar('\n');52 return 0;53 }
运行结果
三，SET与HASH_SET性能对比
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 using namespace stdext; //hash_set 9 10 // MAXN个数据 MAXQUERY次查询11 const int MAXN = 10000, MAXQUERY = 5000000;12 int a[MAXN], query[MAXQUERY];13 14 void PrintfContainertElapseTime(char *pszContainerName, char *pszOperator, long lElapsetime)15 {16 printf("%s 的%s操作 用时 %d毫秒\n", pszContainerName, pszOperator, lElapsetime);17 }18 19 int main()20 {21 printf("set VS hash_set 性能测试 数据容量 %d个 查询次数 %d次\n", MAXN, MAXQUERY);22 const int MAXNUM = MAXN * 4;23 const int MAXQUERYNUM = MAXN * 4;24 printf("容器中数据范围 [0, %d) 查询数据范围[0, %d)\n", MAXNUM, MAXQUERYNUM);25 26 //随机生成在[0, MAXNUM)范围内的MAXN个数27 int i;28 srand(time(NULL));29 for (i = 0; i < MAXN; ++i)30 a[i] = (rand() * rand()) % MAXNUM;31 //随机生成在[0, MAXQUERYNUM)范围内的MAXQUERY个数32 srand(time(NULL));33 for (i = 0; i < MAXQUERY; ++i)34 query[i] = (rand() * rand()) % MAXQUERYNUM;35 36 set nset;37 hash_set nhashset;38 clock_t clockBegin, clockEnd;39 40 41 //insert42 printf("-----插入数据-----------\n");43 44 clockBegin = clock(); 45 nset.insert(a, a + MAXN); 46 clockEnd = clock();47 printf("set中有数据%d个\n", nset.size());48 PrintfContainertElapseTime("set", "insert", clockEnd - clockBegin);49 50 clockBegin = clock(); 51 nhashset.insert(a, a + MAXN); 52 clockEnd = clock();53 printf("hash_set中有数据%d个\n", nhashset.size());54 PrintfContainertElapseTime("hase_set", "insert", clockEnd - clockBegin);55 56 57 //find58 printf("-----查询数据-----------\n");59 60 int nFindSucceedCount, nFindFailedCount; 61 nFindSucceedCount = nFindFailedCount = 0;62 clockBegin = clock(); 63 for (i = 0; i < MAXQUERY; ++i)64 if (nset.find(query[i]) != nset.end())65 ++nFindSucceedCount;66 else67 ++nFindFailedCount;68 clockEnd = clock();69 PrintfContainertElapseTime("set", "find", clockEnd - clockBegin);70 printf("查询成功次数： %d 查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);71 72 nFindSucceedCount = nFindFailedCount = 0;73 clockBegin = clock(); 74 for (i = 0; i < MAXQUERY; ++i)75 if (nhashset.find(query[i]) != nhashset.end())76 ++nFindSucceedCount;77 else78 ++nFindFailedCount;79 clockEnd = clock();80 PrintfContainertElapseTime("hash_set", "find", clockEnd - clockBegin);81 printf("查询成功次数： %d 查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);82 return 0;83 }
运行结果如下：
由于查询的失败次数太多，这次将查询范围变小使用再测试下：
由于结点过多，80多万个结点，set的红黑树树高约为19(2^19=524288，2^20=1048576)，查询起来还是比较费时的。hash_set在时间性能上比set要好一些，并且如果查询成功的几率比较大的话，hash_set会有更好的表现。
四，深入分析hash_set
1. hash table
hash_set的底层数据结构是哈希表，因此要深入了解hash_set，必须先分析哈希表。 hash表的出现主要是为了对内存中数据的快速、随机的访问。它主要有三个关键点：Hash表的大小、Hash函数、冲突的解决。哈希表是根据关键码值(Key-Value)而直接进行访问的数据结构，它用哈希函数处理数据得到关键码值，关键码值对应表中一个特定位置再由应该位置来访问记录，这样可以在时间复杂性度为O(1)内访问到数据。但是很有可能出现多个数据经哈希函数处理后得到同一个关键码——这就产生了冲突，解决冲突的方法也有很多，各大数据结构教材及考研辅导书上都会介绍大把方法。这里采用最方便最有效的一种——链地址法，当有冲突发生时将具同一关键码的数据组成一个链表。下图展示了链地址法的使用：
2. 关于Hash表的大小
Hash表的大小一般是定长的，如果太大，则浪费空间，如果太小，冲突发生的概率变大，体现不出效率。所以，选择合适的Hash表的大小是Hash表性能的关键。
对于Hash表大小的选择通常会考虑两点：
第一，确保Hash表的大小是一个素数。常识告诉我们，当除以一个素数时，会产生最分散的余数，可能最糟糕的除法是除以2的倍数，因为这只会屏蔽被除数中的位。由于我们通常使用表的大小对hash函数的结果进行模运算，如果表的大小是一个素数，就可以获得最佳的结果。
第二，创建大小合理的hash表。这就涉及到hash表的一个概念：装填因子。设装填因子为a，则：
a=表中记录数/hash表表长
通常，我们关注的是使hash表的平均查找长度最小，而平均查找长度是装填因子的函数，而不是表长n的函数。a的取值越小，产生冲突的机会就越小，但如果a取值过小，则会造成较大的空间浪费，通常，只要a的取值合适，hash表的平均查找长度就是一个常数，即hash表的平均查找长度为O(1)。
当然，根据不同的数据量，会有不同的哈希表的大小。对于数据量时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。
下面是哈希表尺寸大小的可能取值（素数，后边是前边的2倍左右）： 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899,701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, 359339171, 718678369, 1437356741, 2147483647那么C++的STL中hash_set是如何实现动态增加哈希表长度的呢？
首先来看看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()函数完成，当空间不足时就倍增（或者近2被的素数），并且表中原有数据都要重新计算hash值以确定新的位置。也就是重新申请一个更大的空间，同时将原来hash_set中的值逐个放到新的hash_set中。
3. 哈希函数
| 关键字 | 内部编码 | 内部编码的平方值 | H(k)关键字的哈希地址 |
| KEYA | 11050201 | 122157778355001 | 778 |
| KYAB | 11250102 | 126564795010404 | 795 |
| AKEY | 01110525 | 001233265775625 | 265 |
| BKEY | 02110525 | 004454315775625 | 315 |