問題タブ [perfect-hash]

何百万ものアイテム（おそらく約10m）の静的な（ランタイムではない）完全なハッシュを作成できる優れたライブラリ（ウィンドウ）を知っている人はいますか？

私は基本的に何百万もの文字列のセットを持っており、文字列が私のセットに含まれているかどうかを最小限のO（1）で知りたいです-それだけです。文字列を実際に検索するのに必要ありません。文字列の背後に値はありません（存在することを除いて）。

文字列値（例： "myObjectName"）を0〜19の整数値にハッシュする方法を考えていました。一意の文字列値は20個以下であることが保証されています。

ありがとう

GSMモデムまたはイーサネット接続のいずれかを使用してネットワークに接続するデバイスに統一された一意のIDを与えるために使用できるハッシュ関数を探しています。

したがって、特定のデバイスについて、ハッシュの生成に使用できるIMEI番号またはMACアドレスがハードコーディングされています。

私はここ数時間ハッシュ関数を研究していて、使用したいと思うかもしれないさまざまな非暗号化および暗号化ハッシュを読んでいます。ハッシュはあまり頻繁に計算されないため、私の焦点はパフォーマンスよりも衝突が少ないことです。

私のフロントランナーは、MD5、FNV-1a、MurmurHash2、Hsieh、およびDJBです。

私が使用するハッシュはすべてCで実装する必要があり、小さなプロセッサを搭載したマイクロコントローラで使用されます。

ニーズに合った適切なハッシュ関数を選択する秘訣は、どのような種類の入力をフィードするかを知ることです。

私がこの質問をしている理由は、IMEIとMACの両方が有限の長さと範囲を持っているという考えが頭に浮かんだので、おそらく両方の完全なセットをカバーでき、衝突がない非常に単純なハッシュ関数が存在するからです。（したがって、完全なハッシュ関数）

IMEI番号は10進数の15桁（16進数で12〜13バイト？）で、MACアドレスは6バイトです。よく考えてみると、2つの入力番号のセットが衝突することはないと思いますが、それが間違っている場合は、遠慮なく訂正してください。もしそうしたら、それを防ぐために何かできるでしょうか？セットの1つにシードを追加しますか？

私は正しい方向に進んでいますか？これらの組み合わせたセットに最適なハッシュ関数を見つけることは可能ですか？

ありがとう！

アップデート

回答とコメントをありがとう。ハッシュ関数として恒等関数;）を使用し、数値のセット間で重複する可能性があるため、マスクも使用することになりました。

IMEI、IMEISV、およびMACはすべて6.5バイト以下に収まるので、値を7バイトに格納してから、最初のバイトで、数値の取得元のセットに基づいたマスクを使用してビット単位のORを実行します。すべてのセットで一意です。

テーブル ルックアップを行う必要がある C 言語アプリがあります。

エントリは文字列です。すべてはランタイムの開始時に認識されます。テーブルは一度初期化され、その後何度も検索されます。テーブルは変更される可能性がありますが、基本的にはアプリが最初からやり直すのと同じです。これは、完全なハッシュを使用できることを意味すると思いますか? ハッシュテーブルの初期化は 1 回だけなので、多少時間がかかっても問題ありません。

エントリ数は 3 ～ 100,000 で、それぞれが一意であり、80% のケースではエントリ数が 100 未満であると推定されます。そのような場合、単純な単純なルックアップは「十分に高速」です。(==誰も文句を言っていない)

ただし、10,000 以上のエントリがある場合、素朴なアプローチのルックアップ速度は受け入れられません。C で文字列のハッシュテーブル ベースの優れたルックアップ パフォーマンスを提供するための適切なアプローチは何ですか? Boost/etc のようなサードパーティの商用ライブラリを持っていないとします。どのハッシュ アルゴリズムを使用すればよいですか? どうやって決めるの？

キーと値のペアを格納するために、ハッシュ マップ (または提案があれば別の構造) を作成したいと考えています。キーはすべて、マップが作成されると同時に一度に挿入されますが、マップを作成する必要がある実行時まで、キーが何になるか (任意の長さの文字列) はわかりません。

このようなクエリ文字列を解析しています"x=100&name=bob&color=red&y=150"（ただし、文字列には無制限の数の変数を含めることができ、変数には任意の長さの名前を付けることができます）。

私はそれを一度解析してハッシュマップを作成したいと思います。できれば最小限で、線形ストレージ要件を満たすために完全なハッシュ関数を使用します。マップが作成されると、値は変更または削除されず、キーと値のペアもマップに追加されないため、マップ全体が事実上定数になります。文字列内で変数が 2 回出現しないことを前提としています (IE."x=1&x=2"は無効です)。

私は でコーディングしており、現在、 string を返すCように使用できる関数を持っていますが、毎回クエリ文字列を解析するため、時間がかかります。非常に大きなクエリ文字列であり、すべての値が数回読み取られるため、最初にロードされたときに一度解析したいと思います。を使用していますが、答えとしてコードを入力する必要はありません。疑似コード、またはすべての提案は素晴らしいでしょう!get("x")"100"O(n)CC

key：valueストアを使用し、Perlで衝突不可能なハッシュを作成したいと思います。Perlモジュール、または衝突不可能なハッシュ関数またはテーブル（おそらくgperfのようなもの）を生成するために使用できる関数はありますか？入力値の範囲はすでにわかっています。

短いASCII文字列を数値（int、float、または数値文字列）に変換する方法を知りたいです。私はここでいくつかの投稿が完璧なハッシュについて言及しているのを見ましたが、それは私が必要としているものかもしれないようです。しかし、私はこれの数学を完全には理解していません。

ASCII文字列を一連の数字に変換してから文字列に戻すにはどうすればよいでしょうか。

ちなみに、文字列をASCII文字番号に分解するのは簡単です。

アップデート

さらに読んだ後、私はこれを思いついた。ただ、数列を短くする方法はあるので、それほど長くはないのではないかと思います。

私はubuntuでgcc4.4.3を使用しています。コマンドを使用してcmphライブラリツール0.9-1をインストールしました

sudo apt-get install libcmph-tools

サンプルプログラムvector_adapter_ex1.cをコンパイルしようとすると、gccはインクルードファイルでcmph.hライブラリを検出できますが、次のような複数のエラーが表示されます。

vector_adapter_ex1.c:(。text+0x93）：cmph_config_new'への未定義の参照vector_adapter_ex1.c:(。text+ 0xbb）： cmph_config_set_mphf_fd'cmph_io_vector_adapter' vector_adapter_ex1.c:(.text+0xa3): undefined reference toへの未定義の参照cmph_config_set_algo' vector_adapter_ex1.c:(.text+0xcf): undefined reference to

ただし、これらはすべてcmphライブラリのソースコードで定義されています。

誰かが発生した可能性のあるエラーを教えたり、最小限の完全なハッシュ関数を構築するための代替方法を提案したりできますか？

文字列識別子のリストの完全なハッシュを作成する必要があるため、この実装を開始する前に (これまでに行ったことはありません)、役立つ可能性のある優れたフレームワークまたは優れたチュートリアルがあるかどうかを知りたいですか?

ありがとう！

私は約200万の値、それぞれ20バイトのセット（静的、コンパイル時に知られています）を持っています。私が必要としているのは、与えられた値がこのセットにあるかどうかをチェックするための高速なO（1）方法です。これにはビット配列を使用した完全なハッシュ関数が理想的であるように思われますが、それを作成する簡単な方法を見つけることができません。gperfなどのユーティリティがいくつかありますが、それらは複雑すぎます。また、私の場合、100％に近い負荷率である必要はなく、10％でも十分ですが、衝突がないことが保証されています。この関数のもう1つの要件は、多くの条件がない単純さです。GPUで実行されます。この場合、あなたは何をアドバイスしますか？