最近、HashMaps/Dictionaries について考えていましたが、それらの実装についての理解にギャップがあることに気付きました。
私のデータ構造クラスから、ハッシュ値はキーを連結リスト バケットのベクトル内の場所に直接マップすると言われました。ウィキペディアによると、MurmurHash は 32 ビットまたは 128 ビットの値を作成します。明らかに、その値をメモリ内の場所に直接マップすることはできません。基になるベクトル内の場所を、ハッシュ マップに配置されているオブジェクトに割り当てるために、そのハッシュ値をどのように使用しますか?
David Robinson の回答を読んだ後、質問を拡張したいと思います。マッピングがリストの基になるベクトルのサイズに基づいている場合、ベクトルのサイズが変更されるとどうなりますか?
通常、ハッシュの結果が生成されると、 moduloが適用されます。NここNで、 はリンクされたリストの割り当てられたベクトルのサイズです。擬似コード:
linked_list = lists[MurmurHash(x) % len(lists)]
linked_list.append(x)
これにより、実装者は、結果の疑似乱数を維持しながら、連結リストのベクトルの長さ (つまり、空間効率と時間効率をどれだけトレードしたいか) を決定できます。
言及する価値のある一般的な代替手段は、ビット マスキングです。たとえば、最下位ビット以外はすべて無視しbます。(たとえば、操作を実行すると、x & 7最下位 3 ビットを除くすべてが無視されます)。これは x modulo 2^b と同等で、ほとんどのオペレーティング システムでたまたま高速です。
2 番目の質問に答えるには、ベクトルのサイズを変更する必要がある場合、ディクショナリに格納されている各値を実際に再マップする必要があります。
Python での辞書の実装に関する優れたブログ投稿があり、その言語が組み込みのハッシュ テーブル (辞書と呼ばれる) を実装する方法を説明しています。その実装では:
スロットの 2/3 以上が使用されている場合、ディクショナリのサイズが変更されます (大きくなります)。
スロットのリストは、現在のサイズの 4 倍にサイズ変更されます
スロットの古いリストのすべての値は、スロットの新しいリストに再マップされます。
そのブログ投稿には、他にも多くの便利な最適化が記載されています。ハッシュ テーブルを実装する際の実際的な側面について優れた見解を示します。