[解決済み] 文字列のハッシュ関数

質問

現在、私の授業でハッシュ関数を扱っています。講師は、私たちのコードで使用した2つのハッシュ関数と比較するために、インターネット上のハッシュ関数に尋ねました。

1つ目は

int HashTable::hash (string word)   
// POST: the index of entry is returned
{       int sum = 0;
        for (int k = 0; k < word.length(); k++)
            sum = sum + int(word[k]);
        return  sum % SIZE; 
}

2番目

int HashTable::hash (string word)
{
   int seed = 131; 
   unsigned long hash = 0;
   for(int i = 0; i < word.length(); i++)
   {
      hash = (hash * seed) + word[i];
   }
   return hash % SIZE;
}

SIZEは501（ハッシュテーブルのサイズ）、入力は20,000語以上のテキストファイルからです。

見た これ の質問で、いくつかのコード例を挙げていますが、ハッシュ関数で何を探せばいいのかよくわかりませんでした。私の理解が正しければ、私の場合、ハッシュは入力（文字列）を受け取り、文字列に番号を割り当てるために数学的な計算を行い、それをテーブルに挿入するのです。この処理は、リストの検索速度を向上させるために行われるのですか？

もし私の論理が正しいのであれば、どなたか文字列を含む別のハッシュ関数を示す良い例や資料をお持ちではないでしょうか？あるいは、私自身の効率的なハッシュ関数を書くプロセスも。

どのように解決するのですか？

まず、実際にはそれほど重要ではありません。ほとんどのハッシュ関数は「十分」です。

でも、もし本当に気になるのなら、それ自体が研究テーマであることを知っておくべきです。それに関する論文は何千と出ています。ハッシュアルゴリズムを研究・設計することで、今日でも博士号を取得することができるのです。

2番目のハッシュ関数は少し優れているかもしれません。なぜなら、この関数は文字列 "ab" という文字列から "ba" . 一方、最初のハッシュ関数に比べると、速さは劣るだろう。これは、あなたのアプリケーションに関係するかもしれないし、ないかもしれない。

ゲノムの文字列に使われるハッシュ関数と、電話データベースの姓名判断に使われるハッシュ関数はかなり違うと思う。おそらく、文字列のハッシュ関数でも、英語やフランス語の単語よりもドイツ語の方が適しているものがあるのだろう。

多くのソフトウェア・ライブラリは十分なハッシュ関数を提供しており、例えば Qt は qhash であり、C++11には std::hash で <functional> Glibにはいくつかの ハッシュ関数 をCで、そして POCO には、いくつかの ハッシュ 関数を使用します。

私はよく、素数を含むハッシュ関数( ベゾーのアイデンティティ ) と xor のようなものである。

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */
unsigned hash_str(const char* s)
{
   unsigned h = FIRSTH;
   while (*s) {
     h = (h * A) ^ (s[0] * B);
     s++;
   }
   return h; // or return h % C;
}

しかし、私はハッシュの専門家だとは思っていない。もちろん A , B , C , FIRSTH は素数であることが望ましいが、他の素数を選ぶことも可能である。

いくつか見てみましょう。 MD5 を実装して、ハッシュ関数がどのようなものになり得るかを感じ取ってください。

アルゴリズムに関する良書には、少なくとも一章がハッシュに割かれています。のウィキページから始めてください。 ハッシュ関数 &です。 ハッシュテーブル .