32 ビット整数との衝突率が低い高速文字列ハッシュアルゴリズム [非公開]

https://stackoverflow.com/questions/114085

02-07-2019
|

質問

簡単に検索したい、無関係な名前付きのものがたくさんあります。「ツチブタ」はどこにいても常に「ツチブタ」であるため、文字列をハッシュして整数を再利用すると、比較を高速化できます。名前のセット全体は不明です (そして時間の経過とともに変化します)。小さい (32 または 16) ビット値を生成し、衝突率が低い高速文字列ハッシュアルゴリズムは何ですか?

C/C++ に特化した最適化された実装を見てみたいと思います。

解決

の1つ FNVの亜種あなたの要件を満たす必要があります。これらは高速で、かなり均等に分散された出力を生成します。

他のヒント

つぶやきハッシュかなりいいです。

固定文字列セットの場合は、gperf を使用します。

文字列セットが変更された場合は、ハッシュ関数を 1 つ選択する必要があります。このトピックは以前に議論されました:

hash_map を使用するときに stl 文字列に使用する最適なハッシュアルゴリズムは何ですか?

もあります素敵な記事で永遠に混乱している.com.

Jenkins の文字列に対する One-at-a-Time ハッシュは次のようになります。

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

ユースケースに応じてさらに優れた別のソリューションは次のとおりです。 インターンされた文字列. 。これがシンボルの仕組みです。Lispで。

インターンされた文字列は、値が実際の文字列バイトのアドレスである文字列オブジェクトです。したがって、グローバルテーブルをチェックインして、インターンされた文字列オブジェクトを作成します。文字列がそこにある場合は、インターンされた文字列をその文字列のアドレスに初期化します。そうでない場合は、それを挿入し、インターンされた文字列を初期化します。

これは、同じ文字列から構築された 2 つのインターン文字列が同じ値、つまりアドレスを持つことを意味します。したがって、N がシステム内にインターンされた文字列の数である場合、特性は次のようになります。

構築が遅い (ルックアップが必要で、場合によってはメモリ割り当てが必要)
同時スレッドの場合はグローバルデータと同期が必要
実際の文字列バイトではなくアドレスを比較しているため、比較は O(1) です (つまり、並べ替えはうまく機能しますが、アルファベット順の並べ替えにはなりません)。

乾杯、

カール

なぜ使用しないのですかライブラリを強化しますか? それらのハッシュ関数は使い方が簡単で、Boost のほとんどの機能は間もなく C++ 標準の一部となる予定です。一部はすでにそうなっています。

ブーストハッシュは次のように簡単です

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

ブーストは次の場所で見つけることができますブースト.org

良いテーマに取り組むのに遅いということはありません。私の発見に人々はきっと興味を持ってくれるはずです。

ハッシュ関数が必要だったので、この投稿を読み、ここにあるリンクで少し調べた後、ダニエル J バーンスタインのアルゴリズムのバリエーションを思いつきました。これを使って興味深いテストを行いました。



unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}

このバリエーションでは、大文字と小文字を区別せずに文字列をハッシュします。これは、ユーザーのログイン資格情報をハッシュするという私のニーズに適しています。「クラーベ」とはスペイン語で「鍵」を意味します。スペイン語で申し訳ありませんが、スペイン語が私の母国語であり、プログラムはスペイン語で書かれています。

さて、私は「test_aaaa」から「test_zzzz」までのユーザー名を生成するプログラムを書き、文字列を長くするために、このリストにランダムなドメインを追加しました。「cloud-nueve.com」、「yahoo.com」、「gmail.com」、「hotmail.com」。したがって、それぞれは次のようになります。

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on.

これはテストの出力です。「Colision entre XXX y XXX」は「XXX と XXX の衝突」を意味します。「パラブラス」は「言葉」を意味し、「合計」はどちらの言語でも同じです-。

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 456976

これは悪くありません。456,976 件中 11 件の衝突です (もちろん、テーブル長として 32 ビット全体を使用しています)。

5 文字 (「test_aaaaa」から「test_zzzzz」まで) を使用してプログラムを実行すると、テーブルを構築する際に実際にメモリが不足します。以下は出力です。「No hay Memoria para insertar XXXX (insertadas XXX)」は、「XXX (XXX Inserted) を挿入するためのメモリが残っていない」という意味です。基本的に、malloc() はその時点で失敗しました。

    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

つまり、2,097,701 個の文字列で 451 回の衝突が発生するだけです。いずれの場合も、コードごとに 2 回を超える衝突は発生しなかったことに注意してください。必要なのは、インデックス作成のためにログイン ID を 40 ビットの一意の ID に変換することなので、これが私にとって素晴らしいハッシュであることを確認しました。そこで、これを使用してログイン資格情報を 32 ビットハッシュに変換し、追加の 8 ビットを使用してコードごとに最大 255 個の衝突を処理します。テスト結果を確認すると、これを生成するのはほぼ不可能です。

これが誰かの役に立つことを願っています。

編集：

テストボックスが AIX である場合と同様に、LDR_CNTRL=MAXDATA=0x20000000 を使用してテストボックスを実行すると、メモリが増え、実行時間が長くなります。結果は次のとおりです。

ブスカンド・コリシオネス...合計衝突件数:2908合計de palabras：5366384

5,366,384 回の試行後の結果は 2908 回です。

非常に重要:-maix64 (つまり unsigned long は 64 ビット) を指定してプログラムをコンパイルすると、衝突の数はすべてのケースで 0 になります。

GNUを見てみよう gperf.

の謝ハッシュ関数は非常に優れており、C の一般的なハッシュ関数としていくつかのベンチマーク/比較があります。必要なものに応じて（完全に明白ではありません）、次のようなことを検討するとよいでしょう cdb その代わり。

Bob Jenkins は多くのハッシュ関数を利用できます, 、どれも高速で、衝突率が低くなります。

Reflector を使用すると、.NET が String.GetHashCode() メソッドで何を使用しているかを確認できます。

Microsoft はこれの最適化にかなりの時間を費やしたと推測します。すべての MSDN ドキュメントにも印刷されており、常に変更される可能性があります。明らかに、それは彼らの「パフォーマンス微調整レーダー」に載っています ;-)

C++ に移植することもかなり簡単なことだと私は考えていたでしょう。

これには良い議論があります前の質問

ハッシュ関数の選択方法の概要と、いくつかの一般的なハッシュ関数の分布に関する統計も含まれています。ここ

ここでは、自分で実装する簡単な方法を説明します。 http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

投稿の抜粋:

英語の大文字の文字セットがあるとすると、文字セットの長さは 26 です。A は数値 0、B は数値 1、C は数値 2 などで表され、Z は数値で表されます。 25.この文字セットの文字列を一意の数値にマップする場合は、バイナリ形式の場合と同じ変換を実行します。

CRC-32. 。Google には約 1 兆件のリンクがあります。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

32 ビット整数との衝突率が低い高速文字列ハッシュ アルゴリズム [非公開]

32 ビット整数との衝突率が低い高速文字列ハッシュアルゴリズム [非公開]