CでCuckoo ハッシュを実装している人はいますか? オープン ソースの非 GPL バージョンがあれば完璧です!
Adam のコメントで言及されているので、あまり使われていない理由を知っている人はいますか? それは単なる実装の問題ですか、それとも優れた理論的特性が実際には実現しないのでしょうか?
Remo.D
質問する
12166 次
8 に答える
7
他の回答が指摘しているように、最も単純なカッコウハッシュテーブルではテーブルが半分空である必要があるのは事実です。ただし、概念はd- aryカッコウハッシュに一般化されており、単純なバージョンの2つの場所とは対照的に、各キーにはdの可能なネスト場所があります。
許容負荷率は、dが増加するにつれて急速に増加します。d = 3の場合、すでに75％のフルテーブルを使用できます。欠点は、 d個の独立したハッシュ関数が必要なことです。私はこの目的のためのBobJenkinsのハッシュ関数（http://burtleburtle.net/bob/c/lookup3.cを参照）のファンです。これは、カッコウのハッシュ実装で役立つ場合があります。
于 2009-04-10T12:39:38.153 に答える
6
カッコウのハッシュは、学界以外では比較的使用されていません（ハードウェアキャッシュは別として、アイデアを借りることもありますが、実際には完全には実装されていません）。挿入に十分な時間をかけるには、非常にまばらなハッシュテーブルが必要です。パフォーマンスを向上させるには、テーブルの51％を空にする必要があります。したがって、高速で多くのスペースを必要とするか、低速でスペースを効率的に使用します。両方を使用することはできません。他のアルゴリズムは時間と空間の両方で効率的ですが、時間または空間のみを考慮した場合、カッコウよりも劣ります。
これがカッコウハッシュテーブルのコードジェネレーターです。ジェネレータのライセンスをチェックして、出力が非GPLであることを確認します。あるべきですが、とにかく確認してください。
-アダム
于 2008-10-23T20:53:59.117 に答える
5
于 2008-10-27T14:13:11.320 に答える
3
それは古い質問ですが、誰かがまだ興味を持っているかもしれません:)
この論文では、GPU (CUDA/OpenCL) での並列 d-ary カッコウ ハッシュの実装について説明します。非常によく説明されており、説明に基づいて実装するのは非常に簡単です。このトピックに興味がある場合は、一般的に読む価値があります。(ただし、ACM ログインが必要です。)
于 2010-08-09T11:39:09.647 に答える
2
ソフトウェアについて話すことはできませんが、カッコウハッシュは確かにハードウェアで使用されており、非常に人気が高まっています. ネットワーク機器の主要なベンダーは、カッコウ ハッシュを検討しており、すでに使用しているベンダーもあります。カッコウハッシュの魅力は、検索時間が一定であることはもちろんですが、挿入時間もほぼ一定であることです。
理論的には挿入に制限はありませんが、実際には、テーブル内の行数の O(log n) に制限することができ、測定すると、挿入時間は平均で約 1.1*d メモリ アクセスです。これは、絶対最小値よりわずか 10% 多いだけです。多くの場合、メモリ アクセスはネットワーク機器の制限要因です。
独立したハッシュ関数は必須であり、適切に選択することは困難です。幸運を。
于 2009-05-12T12:44:04.647 に答える
1
「onebyone」からのコメントに続いて、実際のメモリ要件を決定するために、Cuckooハッシュのいくつかのバージョンを実装してテストしました。
いくつかの実験の後、特に「隠し」のトリックが実装されている場合、テーブルがほぼ50％いっぱいになるまで再灰化する必要がないという主張は真実のようです。
問題は、テーブルを拡大するときです。通常のアプローチはサイズを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
+--+--+--+--+--+--+--+--+
等
テーブルが50％いっぱいになったときにのみ再アッシュが発生するという仮定と合わせて、これにより、再アッシュ後のテーブルは75％空（1/4）ではなく、66％空（1/3）になるという事実につながります（つまり、最悪の場合）。
また、毎回sqrt（n）で拡大すると、無駄なスペースが漸近的に50％に近づくこともわかりました（ただし、計算を確認する必要があります）。
もちろん、メモリ消費量を減らすために支払う代償は、最終的に必要となる再灰の数の増加です。残念ながら、無料で提供されるものはありません。
興味のある方はさらに調査させていただきます。
于 2008-10-27T13:58:02.160 に答える
1
使用率のポイントはわかりますが、これがこの特定のハッシュスキームを試す理由でした。私が何かを逃したかどうか私に知らせてください。
私の知る限り、動的ディクショナリを作成するためのハッシュテーブルの可能な代替手段は、（バランスの取れた）バイナリツリーとスキップリストです。議論のために、キーと値の型から抽象化し、。を介して値にアクセスすると仮定しましょうvoid *。
二分木の場合、私は次のようになります。
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
したがって、ポインタのサイズがすべて同じであると仮定すると、 n個のアイテムを格納するには、 4sバイトが必要になります。
スキップリストは、ノード内のポインターの平均数が2であるのとほぼ同じです。
ハッシュテーブルでは、次のようになります。
struct slot {
void *key;
void *value;
}
したがって、各アイテムは2秒のバイトのみを格納する必要があります。負荷率が50％の場合、n個のアイテムを格納するには、ツリーと同じ4sバイトが必要になります。
私にはそれほど悪くはないようです。カッコウハッシュテーブルは、バイナリツリーとほぼ同じ量のメモリを占有しますが、O（log n）ではなくO（1）アクセス時間を与えます。
ツリーのバランスを保つことの複雑さと、ノードにバランス情報を格納するために必要となる可能性のある追加情報をカウントしません。
他のハッシュスキームでは、最悪の場合のアクセス時間（O（n）の場合もあります）を保証せずに、より良い負荷率（たとえば、75％または80％）を達成できます。
ちなみに、d-aryカッコウハッシュと「スタッシュ付きカッコウハッシュ」は、一定のアクセス時間を維持しながら、負荷率を上げることができるようです。
カッコウのハッシュは私にとって貴重なテクニックのようで、すでに検討されていると思いました。それが私の質問の理由です。
于 2008-10-24T06:15:52.197 に答える
1
IO 言語には、PHash.c に 1 つがあります。Githubで IOのコードを見つけることができます。IO は BSD ライセンスです。
于 2008-10-23T20:58:24.833 に答える