C：为大数据集生成散列键？

我目前正在尝试使用我自己的哈希密钥生成器来哈希和密钥生成。C：为大数据集生成散列键？

目前我有一个约90000个字符串（每个单词和一个不同的单词）的列表。我想知道生成密钥（数字键不是字符串键）的最佳方式是什么？

当前取决于单词最后ascii字符我做一个基于字母值的计算。

结果是大约50％的单词产生与另一个冲突的密钥。

我已经使用二次探测，然后在表中找到剩余单词的空间。

我的问题，如上所述，通常是为90000个不同单词生成密钥的最佳方式？我知道数据集越大，发生冲突的可能性就越大，但是您会如何建议/或最小化冲突？

编辑：另外 - 我不在乎密码学，它只需要快。

谢谢。

来源

2013-02-14 user2013417

'SHA512'怎么样？你只需要8个'uint64_t'就可以进行快速查找。 – 2013-02-14 19:45:58

填充因子是什么？散列值有多少位？什么是你的散列函数？你知道最后一个字符只有26个可能的值吗？（或52或62 ...） – wildplasser 2013-02-14 19:48:35

...或使用http://www.gnu.org/software/gperf/ – 2013-02-14 19:51:21

您可以“借用” Java's implementation of String's hashCode^*：

int hashCode(const char* s) { 
    int h = 0; 
    while (*s) { 
     h = 31*h + (*s++); 
    } 
    return h; 
}

该功能实现了合理的分离，是目前最广泛使用的散列函数在那里之一。

^*其中，as it turns out，java中的C编程转"borrowed" from Kernighan & Ritchie's book。

来源

2013-02-14 19:50:24 dasblinkenlight

是不是Kernighan散列？（或者是那个* 33？） – wildplasser 2013-02-14 19:51:25

@wildplasser它确实是Kerninghan散列，我只是用它来搜索它：“Kernighan和Ritchie的函数使用INITIAL_VALUE 0和31的M. – 2013-02-14 19:56:00

@JerryCoffin我认为任何添加/乘法解决方案都应该优于OP的实现，只需考虑所有字符。哎呀，即使是大于'1'的随机非素数乘法器，也应该比基于字符串最后一个字符的函数做得更好。 – dasblinkenlight 2013-02-14 20:09:02

它不能是选择90,000大小的散列表的好选择，有更好的理想散列的概念，根据这个使用双哈希一个用于表查找和另一个维护列表，你应该尝试乘法的方法两者，我认为这是个好主意。

来源

2013-02-14 19:53:59 Atiq

我见过克努特使用：

register int h,k; register char *p; 
    for (h=0,p=w;*p;p++) h=(*p+h+h)%hash_prime;

哪里hash_prime比在4倍哈希表活条目的预期数量的黄金大。

请参阅：Knuth's literateprogramming.com，冒险的例子。

这里的上下文中的散列码：

#define hash_prime 1009/* the size of the hash table */ 

typedef struct { 
    char text[6]; /* string of length at most 5 */ 
    char word_type; /* a |wordtype| */ 
    char meaning; 
} hash_entry; 

hash_entry hash_table[hash_prime]; /* the table of words we know */ 

void new_word(w,m) 
    char *w; /* a string of length 5 or less */ 
    int m; /* its meaning */ 
{ 
    register int h,k; register char *p; 
    for (h=0,p=w;*p;p++) h=(*p+h+h)%hash_prime; 
    while (hash_table[h].word_type) { 
    h++;if (h==hash_prime) h=0; 
} 

int lookup(w) 
    char *w; /* a string that you typed */ 
{ 
    register int h; register char *p; register char t; 
    t=w[5]; w[5]='\0'; /* truncate the word */ 
    for (h=0,p=w;*p;p++) h=(*p+h+h)%hash_prime; /* compute starting address */ 
    w[5]=t; /* restore original word */ 
    if (h<0) return -1; /* a negative character might screw us up */ 
    while (hash_table[h].word_type) { 
    if (streq(w,hash_table[h].text)) return h; 
    h++;if (h==hash_prime) h=0; 
    } 
    return -1; 
}

注意，此代码：

register char t; 
    // . . . 
    t=w[5]; w[5]='\0'; /* truncate the word */ 
    // . . . 
    w[5]=t; /* restore original word */

是为特定的要求只能看前5个字符，并应该被删除，所以你哈希整个词。

来源

2013-02-14 20:15:29 jimhark

为了防止冲突，你需要一个好的散列密钥生成器。

有几种算法可用。最近和最快的一个被称为xxHash。它用C写成

来源

2013-02-14 20:20:42 Matt

你想要的术语是雪崩 - 提供最佳传播的散列函数。

如果你想让你的密钥保证是唯一的，并且如果你的数据集有零重复那么你可以将你的单词作为base36号码转换为base10号码。如果你使用stroull（）可以返回真正的大整数

char *p=myword; 
for(; *p; p++) 
    *p=toupper(*p); 
unsigned long long key=strtoull(myword, NULL, 36);

这可以溢出，并且仍然返回正数。给定长字符串时的一些散列可能会溢出一个32位整数。 Kerneghan的散列和Bernstein的散列做到了这一点。

在现实中和其他几个人指出：

考虑到碰撞是hash_table大小的功能和hash_function模hash_table规模的雪崩。而不是真正唯一的键你想要的可能是一个更好的hash_table算法和大小。

来源

2013-02-15 22:16:43

C：为大数据集生成散列键？

回答

相关问题