提高字符串为键的哈希表的性能

女爷i 2022-03-20 08:38 227阅读 0赞

## ext/hash\_map:进一步提高字符串为键的哈希表的性能 ##

当我们在ext/hash\_map使用string或const char\*为键的时候，通常需要使用一个HASH函数将字符串转换为一个32位的整型值，然后再与一个大质数取模，最终将节点分布到不同的桶里面去。  
可是，当我们作为键的字符串很长时，每次进行插入、查找和删除操作的时候，字符串都要调用一次HASH函数。于是可以想到，如果我们预先计算出字符串的HASH值，每次都通过HASH值来查找，就省去了使用HASH函数的开销。  
首先，在设计的时候，字符串的哈希表应看成 string -> struct ，就是通过字符串去索引一个节点。而字符串本身需要存储空间，所以可以把字符串需要的空间存储在节点上。可以这样设计这个节点：  
struct HashNode  
\{  
char Key\[100\]; //索引这个节点的字符串，唯一的  
size\_t HashCode; //通过上面的字符串和哈希函数计算出来的hash值  
short KeyLength; //除了缓存HASH值，把字符串的长度也缓存了  
//其他的信息放在后面  
\};  
  
在想好如何存储后，下面就需要考虑如何用节点中的HASH值代替字符串HASH函数计算出来的HASH值。其实，ext/hash\_map有五个模板参数，分别是：  
hash\_map<键的类型，值的类型，HASH函数，比较函数，分配器>  
我们只需要写一个函数对象来产生HASH值就行了：  
struct NodeHasher  
\{  
size\_t operator()(const HashNode\* node) const  
\{  
return node->HashCode; //直接返回计算好的HASH值就行，避免使用HASH函数  
\}  
\};  
有了HASH函数，我们还必须写一个节点比较的函数对象，用于判断两个节点是否是相等：  
struct NodeCompare  
\{  
bool operator()(const HashNode\* lsh, const HashNode\* rsh) const  
\{  
return lsh->HashCode == rsh->HashCode && //为什么不只比较HASH值就可以了呢？  
lsh->KeyLength == rsh->KeyLength && //因为两个不同的字符串可能产生同样的HASH值  
0==strcmp(lsh->Key, rsh->Key); //所以在发生HASH冲突的时候一定要比较内容  
\}  
\};  
  
OK, 下面就可以这样建立哈希表了：  
hash\_map<HashNode\*, HashNode\*, NodeHasher, NodeCompare> hash;  
要注意使用预先计算HASH值的方法，一定要在添加、查找和删除前预先计算好节点的HASH值，计算字符串的HASH值可以这样计算：  
size\_t hash\_code = \_\_gnu\_cxx::\_\_stl\_hash\_string("string");  
  
预先计算HASH值真的能提高HASH表的性能吗？请看下面的测试代码：  
  
\#include <stdio.h>  
\#include <ext/hash\_map>  
using namespace \_\_gnu\_cxx;  
\#include <utility>  
\#include <functional>  
using namespace std;  
\#include <string.h>  
\#include <assert.h>  
  
\#define MAX\_USERNAME\_LEN 40  
\#define P(format, ...) printf("%s %s %d " format "\\n", \_\_FILE\_\_, \_\_FUNCTION\_\_, \_\_LINE\_\_, \#\#\_\_VA\_ARGS\_\_)  
  
//调用INTEL CPU指令RDTSC来获得时间计数，便于得到代码段的性能指标  
unsigned long long rdtsc()  
\{  
\#ifdef \_MSC\_VER /\* msvc compiler \*/  
\_\_asm \_emit 0x0F  
\_\_asm \_emit 0x31  
\#else /\* gcc compiler \*/  
unsigned long long temp;  
unsigned int low, high;  
\_\_asm\_\_ \_\_volatile\_\_("rdtsc" : "=a" (low), "=d" (high));  
temp = high;  
temp <<= 32;  
temp += low;  
return temp;  
\#endif  
\}  
  
struct UserInfo  
\{  
char UserName\[MAX\_USERNAME\_LEN\];  
short Length;  
unsigned int HashCode;  
\};  
  
\#define MAX\_USERS 600000  
UserInfo\* pUsers = NULL;  
int UserCount = 0;  
  
void make\_hash(UserInfo\* Users, int UserCount);  
void make\_char\_hash(UserInfo\* Users, int UserCount);  
void make\_CachedHash(UserInfo\* Users, int UserCount);  
  
void test()  
\{  
//读入用户  
FILE\* fp = fopen("users.txt", "r");  
if (NULL==fp)  
\{  
P("open file error");  
return;  
\}  
pUsers = new UserInfo\[MAX\_USERS\];  
char temp\_username\[MAX\_USERNAME\_LEN\];  
while (NULL!=fgets(temp\_username, sizeof(temp\_username), fp))  
\{  
strncpy(pUsers\[UserCount\].UserName, temp\_username, sizeof(pUsers\[0\].UserName)-1);  
pUsers\[UserCount\].Length = strlen(pUsers\[UserCount\].UserName);  
pUsers\[UserCount\].HashCode = \_\_gnu\_cxx::\_\_stl\_hash\_string(pUsers\[UserCount\].UserName);  
UserCount++;  
\}  
fclose(fp);  
fp = NULL;  
P("user count=%d", UserCount);  
//  
make\_hash(pUsers, UserCount);  
make\_char\_hash(pUsers, UserCount);  
make\_CachedHash(pUsers, UserCount);  
delete\[\] pUsers;  
pUsers = NULL;  
\}  
  
int main()  
\{  
test();  
return 1;  
\}  
  
//=============================================================================  
  
\#include <string>  
using namespace std;  
  
struct str\_hash  
\{  
size\_t operator()(const string& str) const  
\{  
return \_\_stl\_hash\_string(str.c\_str());  
\}  
\};  
  
typedef hash\_map<string, UserInfo\*, str\_hash> StringHash;  
typedef StringHash::iterator StringHashIterator;  
  
void test\_string\_find(StringHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
StringHashIterator it;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
it = hash.find(Users\[i\].UserName);  
if (it == hash.end())  
\{  
P("not found %s", Users\[i\].UserName);  
\}  
\}  
end = rdtsc();  
end -= start;  
P("string find \\t= %llu", end);  
\}  
  
void test\_string\_erase(StringHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hash.erase(Users\[i\].UserName);  
\}  
end = rdtsc();  
end -= start;  
P("string erase \\t= %llu", end);  
assert(hash.size()==0);  
\}  
  
void make\_hash(UserInfo\* Users, int UserCount)  
\{  
hash\_map<string, UserInfo\*, str\_hash> hh;  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hh.insert(make\_pair(Users\[i\].UserName, Users+i));  
\}  
end = rdtsc();  
end -= start;  
P("string spend\\t= %llu", end);  
test\_string\_find(hh, Users, UserCount);  
test\_string\_erase(hh, Users, UserCount);  
\}  
//=============================================================================  
namespace std  
\{  
template <>  
struct equal\_to<const char\*> : public binary\_function<const char\*, const char\*, bool>  
\{  
bool operator()(const char\* str1, const char\* str2) const  
\{  
return 0==strcmp(str1, str2);  
\}  
\};  
\};  
  
struct char\_hash  
\{  
size\_t operator()(const char\* str) const  
\{  
return \_\_stl\_hash\_string(str);  
\}  
\};  
  
typedef hash\_map<const char\*, UserInfo\*, hash<const char\*> > CharHash;  
typedef CharHash::iterator CharHashIterator;  
  
void test\_char\_find(CharHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
CharHashIterator it;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
it = hash.find(Users\[i\].UserName);  
if (it == hash.end())  
\{  
P("not found %s", Users\[i\].UserName);  
\}  
\}  
end = rdtsc();  
end -= start;  
P("char hash find \\t= %llu", end);  
\}  
  
void test\_char\_erase(CharHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hash.erase(Users\[i\].UserName);  
\}  
end = rdtsc();  
end -= start;  
P("char erase \\t= %llu", end);  
assert(hash.size()==0);  
\}  
  
void make\_char\_hash(UserInfo\* Users, int UserCount)  
\{  
//hash\_map<const char\*, UserInfo\*, char\_hash, std::equal\_to<const char\*> > hh;  
CharHash hh;  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hh.insert(make\_pair(Users\[i\].UserName, Users+i));  
\}  
end = rdtsc();  
end -= start;  
P("char spend\\t= %llu", end);  
test\_char\_find(hh, Users, UserCount);  
test\_char\_erase(hh, Users, UserCount);  
\}  
  
//=============================================================================  
//预先缓存HASH值  
struct UserInfoHasher  
\{  
size\_t operator()(const UserInfo\* node) const  
\{  
return node->HashCode;  
\}  
\};  
  
struct UserInfoCompare  
\{  
bool operator()(const UserInfo\* lsh, const UserInfo\* rsh) const  
\{  
return lsh->HashCode == rsh->HashCode &&  
lsh->Length == rsh->Length &&  
strcmp(lsh->UserName, rsh->UserName)==0;  
\}  
\};  
  
typedef hash\_map<UserInfo\*, UserInfo\*, UserInfoHasher, UserInfoCompare> CachedHash;  
typedef hash\_map<UserInfo\*, UserInfo\*, UserInfoHasher, UserInfoCompare>::iterator CachedHashIterator;  
  
void test\_cached\_find(CachedHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
CachedHashIterator it;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
it = hash.find(Users+i);  
if (it == hash.end())  
\{  
P("not found %s", Users\[i\].UserName);  
\}  
\}  
end = rdtsc();  
end -= start;  
P("cached find \\t= %llu", end);  
\}  
  
void test\_cached\_erase(CachedHash& hash, UserInfo\* Users, int UserCount)  
\{  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hash.erase(Users+i);  
\}  
end = rdtsc();  
end -= start;  
P("cached erase \\t= %llu", end);  
assert(hash.size()==0);  
\}  
  
void make\_CachedHash(UserInfo\* Users, int UserCount)  
\{  
CachedHash hh;  
int i;  
unsigned long long start, end;  
start = rdtsc();  
for (i=0; i<UserCount; i++)  
\{  
hh.insert(make\_pair(Users+i, Users+i));  
\}  
end = rdtsc();  
end -= start;  
P("cached spend\\t= %llu", end);  
test\_cached\_find(hh, Users, UserCount);  
test\_cached\_erase(hh, Users, UserCount);  
\}  
  
/\*  
g++ -o string\_hash.o -c string\_hash.cpp -g -Wall  
g++ -o string\_hash.exe string\_hash.o  
\*/  
  
下面是几种HASH的性能对比：数值是rdtsc指令得到的时钟数，可以明显地发现预先计算HASH值后，并能有提升，而且字符串越长，提升的效果越明显。  
方式 插入 查找 删除 string 2635731072 1263602970 1847298339 const char\* 2198134872 807559812 1156917744 cache\_hash 2015849286 740948535 1109622195