4

私は現在、独自のハッシュキージェネレーターを作成しようとして、ハッシュとキー生成をいじっています。

現時点では、約 90000 個の文字列 (各 1 語と別の語) のリストがあります。キー (文字列キーではなく数値キー) を生成する最良の方法は何でしょうか?

現在、最後のASCII文字の単語に応じて、文字の値に基づいて計算を行います。

その結果、単語の約 50% が別の単語と衝突するキーを生成します。

2次プロービングを使用して、残りの単語用のテーブル内のスペースを見つけました。

私の質問は、上記のように、90000 の異なる単語のキーを生成するための一般的な最良の方法は何ですか? データセットが大きいほど、衝突が発生する可能性が高くなることはわかっていますが、衝突をどのように提案または最小化しますか?

編集：また、暗号化については気にしません。高速である必要があります。

ありがとう。

4

5 に答える 5

4

衝突を防ぐには、優れたハッシュ キー ジェネレーターが必要です。

いくつかのアルゴリズムが利用可能です。最近の非常に高速なものの 1 つはxxHashと呼ばれます。Cで書かれています。

于 2013-02-14T20:20:42.147 に答える
4

の*の Java の実装をStringhashCode「借りる」ことができます。

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

この関数は合理的な分離を実現し、最も広く使用されているハッシュ関数の 1 つです。

*結局のところ、これはJava がC プログラミングに関するKernighan & Ritchie の本から「借りた」ものです。

于 2013-02-14T19:50:24.587 に答える
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、アドベンチャーの例。

コンテキスト内のハッシュコードは次のとおりです。

#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

ハッシュ テーブルの 90,000 サイズを選択するのは良い選択ではありません。完全なハッシュのより良い概念があります。これによれば、テーブル ルックアップにダブル ハッシュを使用し、リストを維持するためにもう 1 つを使用します。両方の乗算方法を試してください。それは良い考えです。

于 2013-02-14T19:53:59.373 に答える
0

必要な用語は雪崩です。これは、最適なスプレッドを提供するハッシュ関数です。

キーが一意であることを保証したい場合、およびデータセットに重複がない場合は、単語を 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 modulo hash_table サイズの雪崩であると考えてください。真に一意のキーの代わりに、より優れた hash_table アルゴリズムとサイズが必要になる場合があります。

于 2013-02-15T22:16:43.223 に答える