C でのカッコーハッシュ
https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
誰かが実装していますか カッコーハッシュ Cで？オープンソースの非 GPL バージョンがあれば完璧です。
Adam がコメントで言及しているので、なぜこれがあまり使用されないのか知っている人はいますか?それは単に実装の問題なのでしょうか、それとも理論上の優れた特性が実際には実現しないのでしょうか?
他のヒント
他の回答が指摘しているように、最も単純なカッコウハッシュテーブルでは、テーブルが半分空であることが必要です。ただし、概念は d -aryカッコウハッシュに一般化されており、単純なバージョンでは2つの場所ではなく、各キーがネストできる d 場所を持ちます。
d が増加すると、許容負荷率は急速に増加します。 d = 3の場合のみ、すでに75％のフルテーブルを使用できます。欠点は、 d 独立したハッシュ関数が必要なことです。私はこの目的のためのボブジェンキンスのハッシュ関数のファンです（ http://burtleburtle.netを参照してください） /bob/c/lookup3.c ）、カッコウハッシュの実装に役立つかもしれません。
カッコウハッシュは学外では比較的使用されていません（ハードウェアキャッシュは別ですが、アイデアを借用することもありますが、実際には完全には実装されていません）。挿入に十分な時間をかけるには、非常にまばらなハッシュテーブルが必要です。パフォーマンスを向上させるには、テーブルの51％を空にする必要があります。したがって、高速で大量のスペースを使用するか、低速で効率的にスペースを使用します。両方を使用することはできません。他のアルゴリズムは時間とスペースの両方で効率的ですが、時間またはスペースのみが考慮される場合、カッコウよりも悪いです。
カッコウハッシュテーブルのコードジェネレーターです。ジェネレーターのライセンスをチェックして、出力が非GPLであることを確認してください。あるはずですが、とにかく確認してください。
-アダム
それは古い質問ですが、誰かがまだ興味を持っているかもしれません：）
このペーパーでは、並列d-aryカッコウハッシュの実装について説明しています。 GPU（CUDA / OpenCL）で。非常によく説明されており、説明に基づいて実装するのは非常に簡単です。このトピックに興味がある場合は、一般的に読む価値があります。 （ただし、ACMログインが必要です。）
IO言語には、PHash.cに1つあります。 Githubで IOのコードを見つけることができます。 IOはBSDライセンスです。
利用上のポイントはわかりましたが、これがこの特定のハッシュ スキームを試した理由でした。何か見逃した場合はお知らせください。
私の知る限り、動的辞書を作成するためのハッシュテーブルの代替案として考えられるのは、(バランスの取れた) バイナリ ツリーとスキップリストです。議論のために、キーと値の型を抽象化し、値にアクセスすると仮定しましょう。 void *.
二分木の場合は次のようになります。
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
したがって、ポインタがすべて同じサイズであると仮定すると、 s, 、保管する n 必要なアイテム 4 s バイト。
スキップリストは、ノード内のポインターの平均数が 2 であるため、ほぼ同じです。
ハッシュテーブルでは次のようになります。
struct slot {
void *key;
void *value;
}
したがって、各アイテムに必要なのは 2 つだけです s 保存されるバイト数。負荷率50%の場合、 n 同じように必要なアイテム 4 s バイトをツリーとして。
私にはそれほど悪くはないようです：cuckoo ハッシュテーブルはバイナリ ツリーとほぼ同じ量のメモリを占有しますが、アクセス時間は O(log n) ではなく O(1) になります。
ツリーのバランスを維持する複雑さと、ノードにバランス情報を保存するために必要となる可能性のある追加情報は考慮しません。
他のハッシュ スキームでは、最悪の場合のアクセス時間 ( O(n) になる可能性さえあります) を保証せずに、より良い負荷率 (たとえば 75% または 80%) を達成できる可能性があります。
ところで、 d-ary カッコーハッシュ そして "カッコーが隠し場所でハッシュする" アクセス時間を一定に保ちながら負荷率を高めることができるようです。
私にとってカッコーハッシュは貴重な技術のように思え、すでに研究されているものだと思っていました。それが私の質問の理由です。
ソフトウェアについて話すことはできませんが、カッコウハッシュは確かにハードウェアで使用されており、非常に人気があります。ネットワーク機器の主要ベンダーはカッコウハッシュを検討しており、一部のベンダーは既にそれを使用しています。カッコウハッシュの魅力は、もちろん一定のルックアップ時間だけでなく、ほぼ一定の挿入時間にもあります。
挿入は理論的には無制限ですが、実際にはテーブル内の行数のO（log n）に制限することができ、測定すると、挿入時間は平均で約1.1 * dのメモリアクセスになります。これは、絶対最小値よりもわずか10％高いだけです！メモリアクセスは、多くの場合、ネットワーク機器の制限要因です。
独立したハッシュ関数は必須であり、適切に選択することは困難です。幸運を祈ります。
「onebyone」からのコメントに従って、Cuckooハッシュのいくつかのバージョンを実装およびテストして、実際のメモリ要件を決定しました。
いくつかの実験の後、特に＆quot; stash ＆quot;トリックが実装されています。
問題は、テーブルを拡大するときです。通常のアプローチはサイズを2倍にすることですが、これにより新しいテーブルの使用率は25％になります！
実際、ハッシュテーブルに16個のスロットがあると仮定します。8番目の要素番号を挿入すると、適切なスロットがなくなり、再アッシュする必要があります。これを2倍にすると、テーブルは32スロットになり、そのうち8つだけが占有され、75％の無駄です！
これは、「定数」を得るために支払う価格です。検索時間（アクセス/比較の数の上限に関して）。
別のスキーマを考案しました：1より大きい2の累乗から開始し、テーブルにnスロットがあり、nが2の累乗である場合、n / 2スロットを追加し、n / 3スロットを追加します：
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
etc。
テーブルが50％いっぱいになったときにのみ再アッシングが行われるという仮定と合わせて、これはテーブルが75％空（1/4）ではなく66％空（1/3）に過ぎないという事実につながりますリーシュ（最悪の場合）。
sqrt（n）によって毎回拡大すると、無駄なスペースが漸近的に50％に近づくこともわかりました（ただし、数学をチェックする必要があります）。
もちろん、メモリ消費量を減らすために支払う代償は、最終的に必要となるリーシュの数の増加です。残念ながら、無料のものは何もありません。
誰かが興味を持っている場合は、さらに調査します。
