4

我目前正在玩散列和密钥生成，试图制作我自己的散列密钥生成器。

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

目前根据单词最后一个 ascii 字符，我根据字母的值进行计算。

结果是大约 50% 的单词生成了一个与另一个发生冲突的键。

我使用二次探测然后在表格中为其余的单词找到空间。

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

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

谢谢。

4

5 回答 5

4

您可以“借用” Java 的String's hashCode*实现：

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

该函数实现了合理的分离，是目前使用最广泛的哈希函数之一。

*事实证明，Java 又“借用”了 Kernighan 和 Ritchie 的C 编程书籍。

于 2013-02-14T19:50:24.587 回答
4

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

有几种可用的算法。一种最近且非常快的称为xxHash。它是用 C 编写的。

于 2013-02-14T20:20:42.147 回答
0

选择 90,000 大小的哈希表不是一个好选择，完美哈希的概念要好得多，根据这个使用双重哈希，一个用于表查找，另一个用于维护列表，我认为你应该尝试两者的乘法方法那是个好主意。

于 2013-02-14T19:53:59.373 回答
0

我见过 Knuth 使用：

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

其中 hash_prime 是大于哈希表中预期活动条目数 4 倍的素数。

请参阅：Knuth 的 literateprogramming.com，Adventure 示例。

这是上下文中的哈希代码：

#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-14T20:15:29.520 回答
0

您想要的术语是雪崩 - 一种提供最佳传播的哈希函数。

如果您希望保证您的键是唯一的，并且如果您的数据集有零个重复，那么您可以将您的单词作为 base36 数字转换为 base10 数字。如果你使用 sroull() 你可以返回非常大的整数

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-15T22:16:43.223 回答