标题：字符串的Hash
出处：Felix021
时间：Sat, 16 May 2009 23:11:37 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1596

内容：
早上参加了腾讯的笔试，做完以后自我感觉良好，但是后来和sandy讨论了一下，发现还是挫了，因为没用上Hash。
于是中午回去狠查了一些资料，看到了一点东西，充实了些。
点击这里下载文件
看到一些字符串的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;
}


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;
}


查看结果：
引用
$ sort elf1.txt | less
$ sort elf1.txt | uniq | less





Generated by Bo-blog 2.1.0