grep出来的.svn/text-base什么的太讨厌了
sdbm hash for PHP
Aug
21
A message-digest algorithm producing 64bit digest 
前两天在找个摘要算法，要求很简单，冲突少，生成64bit摘要；安全性可以忽略。MD5/SHA-1是好算法，但是它们生成的摘要是128/160bit的。Qining最初提出了个算法，将MD5的128bit分成4个32bit，d[0..3]，然后通过以下公式获得64bit摘要：看起来挺有模有样的，但是用0..100,000去测试，发现了3个碰撞，毕竟没有数学理论的支持，胡搞还是不行的。另外再尝试了下，把MD5的前64bit拿出来，效果倒是好，前100,000没有碰撞。只是这种做法毕竟不让人放心，于是到网上搜了一下，发现不少人有此需求，但是没有现成的算法，挺无奈的。还好，有个人一语道破天机：用个字符串hash算法就行了。
于是翻出以前的一篇日志字符串的Hash，从里头把sdbm哈希函数搞出来，测试了一下（跑了好几分钟呢），效果很赞，一亿以内的整数都没有问题，代码如下：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
引用
concat(d[0] XOR d[2], d[1] XOR d[3])
于是翻出以前的一篇日志字符串的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;
}
#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;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
