Title: STL系列之九 探索hash_set
Author: MoreWindows
Blog:
二．简化版的hash_table
按照上面的分析和图示，并参考《编程珠玑》第15章中哈希表的实现，不难写出一个简单的哈希表，我们称之为简化版hash_table。该哈希表由一个指针数组组成，数组中每个元素都是链表的表头指针，程序分为hash_table.h，hash_table.cpp和main.cpp。
1.hash_table.h
#pragma once#define NULL 0//简化版hash_table //by MoreWindows( )struct Node{int val;Node *next;Node(int n){this->val = n;this->next = NULL;}};class hash_table{public:hash_table(const int ntablesize);~hash_table();bool insert(int n);void insert(int *pFirst, int *pLast);bool find(int n);int size();int HashFun(int n);public:intm_nTableSize;intm_nTableDataCount;Node** m_ppTable;};
2.hash_table.cpp
//简化版hash_table//by MoreWindows( )#include "hash_table.h"#include <malloc.h>#include <memory.h>hash_table::hash_table(const int ntablesize){m_nTableSize = ntablesize;m_ppTable = (Node**)malloc(sizeof(Node*) * m_nTableSize);if (m_ppTable == NULL)return ;m_nTableDataCount = 0;memset(m_ppTable, 0, sizeof(Node*) * m_nTableSize);}hash_table::~hash_table(){free(m_ppTable);m_ppTable = NULL;m_nTableDataCount = 0;m_nTableSize = 0;}int inline hash_table::HashFun(int n) {return (n ^ 0xdeadbeef) % m_nTableSize;}int hash_table::size(){return m_nTableDataCount;}bool hash_table::insert(int n){int key = HashFun(n);//在该链表中查找该数是否已经存在for (Node *p = m_ppTable[key]; p != NULL; p = p->next)if (p->val == n)return true;//在链表的头部插入Node *pNode = new Node(n);if (pNode == NULL)return false;pNode->next = m_ppTable[key];m_ppTable[key] = pNode;m_nTableDataCount++;return true;}bool hash_table::find(int n){int key = HashFun(n);for (Node *pNode = m_ppTable[key]; pNode != NULL; pNode = pNode->next)if (pNode->val == n)return true;return false;}void hash_table::insert(int *pFirst, int *pLast){for (int *p = pFirst; p != pLast; p++)this->insert(*p);}
3．main.cpp
在main.cpp中，对set、hash_set、简化版hash_table作一个性能测试，测试环境为Win7+VS2008的Release设置（下同）。
//测试set，hash_set及简化版hash_table// by MoreWindows( )#include <set>#include <hash_set>#include "hash_table.h"#include <iostream>#include <ctime>#include <cstdio>#include <cstdlib>using namespace std;using namespace stdext; //hash_setvoid PrintfContainerElapseTime(char *pszContainerName, char *pszOperator, long lElapsetime){printf("%s 的 %s操作 用时 %d毫秒\n", pszContainerName, pszOperator, lElapsetime);}// MAXN个数据 MAXQUERY次查询const int MAXN = 5000000, MAXQUERY = 5000000;int a[MAXN], query[MAXQUERY];int main(){printf("set VS hash_set VS hash_table(简化版) 性能测试\n");printf("数据容量 %d个 查询次数 %d次\n", MAXN, MAXQUERY);const int MAXNUM = MAXN * 4;const int MAXQUERYNUM = MAXN * 4;printf("容器中数据范围 [0, %d) 查询数据范围[0, %d)\n", MAXNUM, MAXQUERYNUM);printf("–by MoreWindows( ) –\n\n");//随机生成在[0, MAXNUM)范围内的MAXN个数int i;srand((unsigned int)time(NULL));for (i = 0; i < MAXN; ++i)a[i] = (rand() * rand()) % MAXNUM;//随机生成在[0, MAXQUERYNUM)范围内的MAXQUERY个数srand((unsigned int)time(NULL));for (i = 0; i < MAXQUERY; ++i)query[i] = (rand() * rand()) % MAXQUERYNUM;set<int>nset;hash_set<int> nhashset;hash_table nhashtable(MAXN + 123);clock_t clockBegin, clockEnd;//insertprintf("—–插入数据———–\n");clockBegin = clock();nset.insert(a, a + MAXN); clockEnd = clock();printf("set中有数据%d个\n", nset.size());PrintfContainerElapseTime("set", "insert", clockEnd – clockBegin);clockBegin = clock();nhashset.insert(a, a + MAXN); clockEnd = clock();printf("hash_set中有数据%d个\n", nhashset.size());PrintfContainerElapseTime("hash_set", "insert", clockEnd – clockBegin);clockBegin = clock();for (i = 0; i < MAXN; i++)nhashtable.insert(a[i]); clockEnd = clock();printf("hash_table中有数据%d个\n", nhashtable.size());PrintfContainerElapseTime("Hash_table", "insert", clockEnd – clockBegin);//findprintf("—–查询数据———–\n");int nFindSucceedCount, nFindFailedCount; nFindSucceedCount = nFindFailedCount = 0;clockBegin = clock(); for (i = 0; i < MAXQUERY; ++i)if (nset.find(query[i]) != nset.end())++nFindSucceedCount;else++nFindFailedCount;clockEnd = clock();PrintfContainerElapseTime("set", "find", clockEnd – clockBegin);printf("查询成功次数： %d 查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);nFindSucceedCount = nFindFailedCount = 0;clockBegin = clock();for (i = 0; i < MAXQUERY; ++i)if (nhashset.find(query[i]) != nhashset.end())++nFindSucceedCount;else++nFindFailedCount;clockEnd = clock();PrintfContainerElapseTime("hash_set", "find", clockEnd – clockBegin);printf("查询成功次数： %d 查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);nFindSucceedCount = nFindFailedCount = 0;clockBegin = clock();for (i = 0; i < MAXQUERY; ++i)if (nhashtable.find(query[i]))++nFindSucceedCount;else++nFindFailedCount;clockEnd = clock();PrintfContainerElapseTime("hash_table", "find", clockEnd – clockBegin);printf("查询成功次数： %d 查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);return 0;}
在数据量为500万时测试结果如下：
如若今生再相见，哪怕流离百世，迷途千年，也愿。
