すばやく検索したい、関連のない名前の付いたものがたくさんあります。「ツチブタ」は常にどこでも「ツチブタ」であるため、文字列をハッシュして整数を再利用すると、比較が高速化されます。名前のセット全体は不明です (そして時間の経過とともに変化します)。小さな (32 または 16) ビット値を生成し、衝突率が低い高速文字列ハッシュ アルゴリズムは何ですか?
C/C++ に固有の最適化された実装を見たいと思います。
93914 次
14 に答える
35
マーマーハッシュはかなりいいです。
于 2008-09-22T10:17:20.290 に答える
30
FNVバリアントの1つが要件を満たす必要があります。それらは高速で、かなり均等に分散された出力を生成します。
于 2008-09-22T10:08:32.340 に答える
17
固定文字列セットの場合は、gperfを使用します。
文字列セットが変更された場合は、ハッシュ関数を1つ選択する必要があります。そのトピックは以前に議論されました：
于 2008-09-22T10:13:21.017 に答える
17
everlyconfuzzled.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;
}
于 2008-12-16T22:25:09.100 に答える
8
ユースケースに応じてさらに優れた別のソリューションは、インターンされた文字列です。これは、Lisp などでシンボルがどのように機能するかです。
インターンされた文字列は、値が実際の文字列バイトのアドレスである文字列オブジェクトです。そのため、グローバル テーブルをチェックインしてインターンされた文字列オブジェクトを作成します。文字列がそこにある場合は、インターンされた文字列をその文字列のアドレスに初期化します。そうでない場合は、それを挿入してから、インターンされた文字列を初期化します。
これは、同じ文字列から作成された 2 つのインターンされた文字列が同じ値 (アドレス) を持つことを意味します。したがって、N がシステム内のインターンされた文字列の数である場合、特性は次のようになります。
- 構築が遅い (ルックアップと、場合によってはメモリ割り当てが必要)
- 同時スレッドの場合、グローバル データと同期が必要
- Compare は O(1) です。これは、実際の文字列バイトではなく、アドレスを比較しているためです (これは、並べ替えがうまく機能することを意味しますが、アルファベット順の並べ替えにはなりません)。
乾杯、
カール
于 2008-09-22T11:02:46.780 に答える
5
良い題材を作るのに遅いということは決してありませんし、人々が私の発見に興味を持ってくれると確信しています.
ハッシュ関数が必要でした。この投稿を読み、ここに記載されているリンクについて少し調査した後、Daniel J Bernstein のアルゴリズムのこのバリエーションを思いつきました。これを使用して、興味深いテストを行いました。
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;
}
このバリエーションでは、大文字と小文字を区別せずに文字列をハッシュします。これは、ユーザーのログイン資格情報をハッシュする必要がある場合に適しています。「clave」はスペイン語で「鍵」。スペイン語で申し訳ありませんが、それは私の母国語であり、プログラムはスペイン語で書かれています。
さて、私は「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 など。
テストの出力は次のとおりです。'Collision entre XXX y XXX' は、'XXX と XXX の衝突' を意味します。「パラブラス」は「単語」を意味し、「合計」は両方の言語で同じです。
バスカンド コリシオネス...
「test_phiz@hotmail.com」と「test_juxg@cloud-nueve.com」の衝突 (1DB903B7)
「test_rfhh@hotmail.com」と「test_fpgo@yahoo.com」の衝突 (2F5BC088)
「test_wxuj@hotmail.com」と「test_pugy@cloud-nueve.com」の衝突 (51FD09CC)
「test_sctb@gmail.com」と「test_iohw@cloud-nueve.com」の衝突 (52F5480E)
衝突 entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
「test_rfll@hotmail.com」と「test_btgo@yahoo.com」の衝突 (7FD70008)
「test_wcho@cloud-nueve.com」と「test_scfz@gmail.com」の衝突 (9BD351C4)
「test_swky@cloud-nueve.com」と「test_fqpn@gmail.com」の衝突 (A86953E1)
「test_rftd@hotmail.com」と「test_jlgo@yahoo.com」の衝突 (BA6B0718)
「test_rfpp@hotmail.com」と「test_nxgo@yahoo.com」の衝突 (D0523F88)
「test_zlgo@yahoo.com」と「test_rfdd@hotmail.com」の衝突 (DEE08108)
合計 de コリジョン: 11
パラブラスの総数 : 456976
これは悪くありません。456,976 回のうち 11 回の衝突です (もちろん、テーブルの長さとして 32 ビット全体を使用します)。
'test_aaaaa' から 'test_zzzzz' までの 5 文字を使用してプログラムを実行すると、実際にはテーブルを構築するメモリが不足します。以下は出力です。「No hay memoria para insertar XXXX (insertadas XXX)」は、「XXX を挿入するためのメモリが残っていない (XXX が挿入された)」ことを意味します。基本的に malloc() はその時点で失敗しました。
いいえ hay memoria para insertar 'test_epjcv' (insertadas 2097701)。
バスカンド コリシオネス...
...451個の「衝突」文字列...
衝突数の合計: 451
合計 de Palabras : 2097701
これは、2,097,701 個の文字列で 451 回の衝突しかないことを意味します。いずれの場合も、コードごとに 2 回を超える衝突が発生しなかったことに注意してください。インデックス作成のためにログイン ID を 40 ビットの一意の ID に変換する必要があるため、これは私にとって素晴らしいハッシュであることを確認しています。したがって、これを使用してログイン資格情報を 32 ビット ハッシュに変換し、余分な 8 ビットを使用して、コードごとに最大 255 の衝突を処理します。テスト結果を見ると、生成するのはほとんど不可能です。
これが誰かに役立つことを願っています。
編集：
テスト ボックスが AIX のように、LDR_CNTRL=MAXDATA=0x20000000 を使用して実行し、より多くのメモリを与えて実行時間を長くしました。結果は次のとおりです。
Buscando Colisiones... Total de Colisiones: 2908 Total de Palabras : 5366384
5,366,384 回の試行で 2908 回です!!
非常に重要: プログラムを -maix64 (つまり unsigned long は 64 ビット) でコンパイルすると、衝突の数はすべての場合で 0 になります!!!
于 2013-09-26T12:22:05.477 に答える
3
Hsiehハッシュ関数は非常に優れており、Cの一般的なハッシュ関数として、いくつかのベンチマーク/比較があります。必要なものによっては（完全には明らかではありません）、代わりにcdbのようなものを検討することをお勧めします。
于 2008-09-24T04:13:00.273 に答える
3
Boostライブラリを使用しないのはなぜですか? それらのハッシュ関数は簡単に使用でき、Boost のほとんどのものはまもなく C++ 標準の一部になります。一部はすでにそうなっています。
ブーストハッシュは次のように簡単です
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
于 2008-12-16T21:11:27.517 に答える
3
Bob Jenkins には多くのハッシュ関数が用意されており、それらはすべて高速で衝突率が低いものです。
于 2008-12-16T21:30:58.723 に答える
2
GNUgperfをご覧ください。
于 2008-09-22T10:06:20.597 に答える
2
Reflector を使用して String.GetHashCode() メソッドで .NET が使用するものを確認できます。
Microsoft がこれを最適化するのにかなりの時間を費やしたと推測するのは危険です。彼らは、すべての MSDN ドキュメントにも、常に変更される可能性があることを印刷しています。明らかに、それは彼らの「パフォーマンス調整レーダー」にあります;-)
C++ に移植するのもかなり簡単だと思いました。
于 2008-12-16T21:34:14.567 に答える
2
ハッシュ関数の選択方法の概要と、いくつかの一般的な関数の分布に関する統計がここにあります
于 2008-12-09T21:29:21.210 に答える
0
ここで説明するのは、自分で実装する簡単な方法です: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html
投稿からの抜粋:
大文字の英字の文字セットがあるとすると、文字セットの長さは 26 で、A は数字 0、B は数字 1、C は数字 2 など、Z は数字で表すことができます。 25. ここで、この文字セットの文字列を一意の数値にマップするときはいつでも、バイナリ形式の場合と同じ変換を実行します
于 2015-04-17T03:33:27.270 に答える
-3
CRC-32。それのためにグーグルに約1兆のリンクがあります。
于 2008-09-22T10:06:47.397 に答える