标题：A message-digest algorithm producing 64bit digest
出处：Felix021
时间：Sat, 21 Aug 2010 01:22:16 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1914

内容：
前两天在找个摘要算法，要求很简单，冲突少，生成64bit摘要；安全性可以忽略。MD5/SHA-1是好算法，但是它们生成的摘要是128/160bit的。Qining最初提出了个算法，将MD5的128bit分成4个32bit，d[0..3]，然后通过以下公式获得64bit摘要：引用
concat(d[0] XOR d[2], d[1] XOR d[3])

看起来挺有模有样的，但是用0..100,000去测试，发现了3个碰撞，毕竟没有数学理论的支持，胡搞还是不行的。另外再尝试了下，把MD5的前64bit拿出来，效果倒是好，前100,000没有碰撞。只是这种做法毕竟不让人放心，于是到网上搜了一下，发现不少人有此需求，但是没有现成的算法，挺无奈的。还好，有个人一语道破天机：用个字符串hash算法就行了。

于是翻出以前的一篇日志字符串的Hash，从里头把sdbm哈希函数搞出来，测试了一下（跑了好几分钟呢），效果很赞，一亿以内的整数都没有问题，代码如下：#include <iostream>
#include <cstdio>
#include <algorithm>
#include <assert.h>
using namespace std;

typedef unsigned long long ull;

ull sdbmhash(const char *s){
    ull hash = 0;
    while (*s){
        hash = (hash << 6) + (hash << 16) - hash + *s++;
    }
    return hash;
}

int main()
{
    const unsigned N = 100000000;
    ull *all = new(nothrow) ull[N];
    assert(all != NULL);
    unsigned i = 0;
    char tmp[100];
    for (i = 1; i <= N; ++i)
    {
        snprintf(tmp, 100, "%09u", i);
        all[i] = sdbmhash(tmp);
        if (i % (N / 20) == 0) printf("i = %u\n", i);
    }
    sort(all, all + N);
    ull * end = unique(all, all + N);
    printf("%u\n", all + N - end);
    delete[] all;
    return 0;
}



Generated by Bo-blog 2.1.0