免费给Felix发短信
本来面试前应该看的：字节对齐, #pragma pack
May
16
早上参加了腾讯的笔试，做完以后自我感觉良好，但是后来和sandy讨论了一下，发现还是挫了，因为没用上Hash。
于是中午回去狠查了一些资料，看到了一点东西，充实了些。
下载文件 (已下载 1665 次)
看到一些字符串的Hash函数，想测试一下它们的实际性能
于是写了个程序来生成5w个字符串
用不同的hash函数计算hash值模9793（随便写的一个数字）
然后再用 sort 和 uniq 看了一下结果，发现 sdbmhash 是最好的, jshash其次，也很不错
然而很意外的是 elfhash 的性能则相当差，完全达不到可用的标准
——在对5w个数进行hash以后得到的结果里面，居然有700多个0和400多个1。
下面贴一些代码：
gen_data.cpp
hash.cpp
查看结果：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
于是中午回去狠查了一些资料，看到了一点东西，充实了些。
下载文件 (已下载 1665 次)看到一些字符串的Hash函数，想测试一下它们的实际性能
于是写了个程序来生成5w个字符串
用不同的hash函数计算hash值模9793（随便写的一个数字）
然后再用 sort 和 uniq 看了一下结果，发现 sdbmhash 是最好的, jshash其次，也很不错
然而很意外的是 elfhash 的性能则相当差，完全达不到可用的标准
——在对5w个数进行hash以后得到的结果里面，居然有700多个0和400多个1。
下面贴一些代码：
gen_data.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char tbl[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+=-?><:';,./][{}\\\"";
int main(){
char s[1024];
int i, l, m = strlen(tbl), j;
srand(732984);
freopen("str.txt", "w", stdout);
for (i = 0; i < 50000; ++i){
l = rand() % 100 + 1;
for (j = 0; j < l; ++j)
s[j] = tbl[rand() % m];
s[j] = 0;
printf("%s\n", s);
}
return 0;
}
#include <stdlib.h>
#include <string.h>
char tbl[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+=-?><:';,./][{}\\\"";
int main(){
char s[1024];
int i, l, m = strlen(tbl), j;
srand(732984);
freopen("str.txt", "w", stdout);
for (i = 0; i < 50000; ++i){
l = rand() % 100 + 1;
for (j = 0; j < l; ++j)
s[j] = tbl[rand() % m];
s[j] = 0;
printf("%s\n", s);
}
return 0;
}
hash.cpp
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
unsigned int elfhash(char *s){
int hash = 0, x = 0;
while (*s){
hash = (hash << 4) + (*s++);
if(((x = hash) & 0xf0000000l) != 0){
hash ^= (x >> 24);
hash &= x;
}
}
return hash & 0x7fffffffl;
}
unsigned int jshash(char *s){
int hash = 1315423911;
while (*s){
hash ^= (hash << 5) + *s++ + (hash >> 2);
}
return (hash & 0x7fffffffl);
}
unsigned int sdbmhash(char *s){
int hash = 0;
while (*s){
hash = (hash << 6) + (hash << 16) - hash + *s++;
}
return (hash & 0x7fffffffl);
}
int main(){
char s[1024];
freopen("str.txt", "r", stdin);
freopen("elf1.txt", "w", stdout);
while(true){
scanf("%s", s);
if(feof(stdin)) break;
printf("%d\n", elfhash(s) % 9793);
}
return 0;
}
#include <cstdlib>
#include <cstring>
using namespace std;
unsigned int elfhash(char *s){
int hash = 0, x = 0;
while (*s){
hash = (hash << 4) + (*s++);
if(((x = hash) & 0xf0000000l) != 0){
hash ^= (x >> 24);
hash &= x;
}
}
return hash & 0x7fffffffl;
}
unsigned int jshash(char *s){
int hash = 1315423911;
while (*s){
hash ^= (hash << 5) + *s++ + (hash >> 2);
}
return (hash & 0x7fffffffl);
}
unsigned int sdbmhash(char *s){
int hash = 0;
while (*s){
hash = (hash << 6) + (hash << 16) - hash + *s++;
}
return (hash & 0x7fffffffl);
}
int main(){
char s[1024];
freopen("str.txt", "r", stdin);
freopen("elf1.txt", "w", stdout);
while(true){
scanf("%s", s);
if(feof(stdin)) break;
printf("%d\n", elfhash(s) % 9793);
}
return 0;
}
查看结果：
引用
$ sort elf1.txt | less
$ sort elf1.txt | uniq | less
$ sort elf1.txt | uniq | less
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
另外，貌似是SDBM Hash吧。