連鎖ハッシュテーブルと理解解散

Question

現在、C＃でカスタムDeflateの実装を作成しようとしています。

私は現在、（最大）32kのデータを持っていて、入力に対して最も長いパターンを検索しようとしているところで、「パターン検索」の部分を実装しようとしています。デフレートを定義

RFC 1951は、そのプロセスについて述べている：

コンプレッサーは3バイト配列に動作ハッシュ関数を使用して、重複した文字列を検索するために連鎖ハッシュテーブルを使用しています 。圧縮中の任意の点で 与えられたポイントで、XYZを検査される の次の3入力バイトにします（必ずしもすべてが異なるわけではありません）。まず、 コンプレッサは、XYZのハッシュチェーンを調べます。チェーンが空の場合、 は、Xをリテラルバイトとして書き出し、入力内の1つを バイトだけ進めます。ハッシュチェーンが空でない場合、 シーケンスXYZ（または不幸な場合には 同じハッシュ関数値を持つ他の3バイト）が発生したことを示すコンプレッサー は、XYZハッシュチェーンのすべての文字列を実際の入力データ が現在の点から始まり、最長の が選択されます。

私はハッシュ関数が何であるかを知っており、ハッシュテーブルも何であるか知っています。しかし、 "連鎖ハッシュテーブル"とは何ですか？また、どのようにそのような構造が（C＃で）効率的に設計され、大量のデータを扱うことができるでしょうか？ Unforunatelyでは、RFCに記述されている構造がどのように機能するのか分かりませんでした。

どのような種類のハッシュ関数を選択できますか（意味があります）？

ありがとうございます！

Answer 1

連鎖ハッシュテーブルは、2つのアイテムのキーが同じ値にハッシュした場合でも、2つのアイテムがまったく同じキーを持っていても、そこに置かれたすべてのアイテムを格納するハッシュテーブルです。

DEFLATEの実装では、（キー、データ）項目の束を特定の順番で格納する必要がなく、そのキーを持つすべての項目のリストをすばやく参照する必要があります。 この場合、キーは圧縮されていない平文の3バイト連続しており、そのデータは平文で3バイトの部分文字列がどこにあるかを示すポインタまたはオフセットです。

多くのハッシュテーブル/辞書の実装では、すべてのアイテムのキーとデータの両方が格納されます。 DEFLATEのテーブルにキーを格納する必要はありませんが、圧縮中に少しだけメモリを使用する以外の問題はありません。

C++ STL unordered_mapのようないくつかのハッシュテーブル/ディクショナリの実装では、格納するすべての（キー、データ）アイテムに一意のキーが必要であると主張しています。すでにテーブルにある古いアイテムと同じキーを持つ別の（キー、データ）アイテムを格納しようとすると、これらの実装は古いアイテムを削除し、新しいアイテムで置き換えます。 が偶然C++ STL unordered_mapなどの実装を使用した場合、圧縮ファイルはC++ STL hash_multimapなどのより適切なライブラリを使用した場合よりも大きくなります。 このようなエラーは、結果の（不必要に大きい）圧縮ファイルが、標準のDEFLATEコンプレッサによって元のファイルと同じビットのファイルに正しく解凍されるため、検出が困難な場合があります。 DEFLATEや他の圧縮アルゴリズムのいくつかの実装では、意図的にこのような実装を使用し、意図的に圧縮ファイルサイズを犠牲にして圧縮速度を向上させています。

Nick Johnson氏によると、標準のハッシュテーブルまたは辞書の実装で使用されるデフォルトのハッシュ関数はおそらくそれ以上のものです。

http://en.wikipedia.org/wiki/Hashtable#Separate_chaining

Answer 2

この場合、各要素には文字列のリスト（この場合は、指定された3文字の接頭辞で始まるすべての文字列）が含まれるハッシュテーブルが記述されています。標準の.netハッシュテーブルまたは辞書プリミティブを使用できるだけで、正確な実装の詳細を複製する必要はありません。

32kは大量のデータではないため、ハッシュテーブルのスケーリングについて心配する必要はありません。また、組み込みプリミティブは、自分で作成できるものよりも効率的です。