いくつかの異なるアルゴリズムをテストし、速度と衝突の数を測定しました。

3つの異なるキーセットを使用しました。

• 216,553個の英語の単語のリスト ^{🕗アーカイブ} （小文字）
• 数値"1"から"216553"（ZIPコードと、貧弱なハッシュがmsn.comをどのようにダウンさせたかを考えてください ^{🕗アーカイブ} ）
• 216,553 “ランダム」（つまり、タイプ4uuid ）GUID

各コーパスについて、衝突の数とハッシュに費やされた平均時間記録されました。

テストしました：

• DJB2
• DJB2a （+ diではなくxorを使用したバリアントv>）
• FNV-1 （32ビット）
• FNV-1a （32ビット）
• SDBM
• CRC32
• Murmur2 （32ビット）
• SuperFastHash

結果

各結果には、平均ハッシュ時間と衝突の数が含まれます

Hash Lowercase Random UUID Numbers ============= ============= =========== ============== Murmur 145 ns 259 ns 92 ns 6 collis 5 collis 0 collis FNV-1a 152 ns 504 ns 86 ns 4 collis 4 collis 0 collis FNV-1 184 ns 730 ns 92 ns 1 collis 5 collis 0 collis▪ DBJ2a 158 ns 443 ns 91 ns 5 collis 6 collis 0 collis▪▪▪ DJB2 156 ns 437 ns 93 ns 7 collis 6 collis 0 collis▪▪▪ SDBM 148 ns 484 ns 90 ns 4 collis 6 collis 0 collis** SuperFastHash 164 ns 344 ns 118 ns 85 collis 4 collis 18742 collis CRC32 250 ns 946 ns 130 ns 2 collis 0 collis 0 collis LoseLose 338 ns - - 215178 collis 

メモ：

• LoseLoseアルゴリズム（ハッシュ=ハッシュ+文字）は本当に ひどい です。すべてが同じ1,375個のバケットに衝突します
• SuperFastHashは高速で、物事はかなり散らばっているように見えます。私の良さにより、数の衝突。 移植した人が何か問題を抱えていることを願っています。かなり悪いです
• CRC32はかなり良いです。低速で、1kのルックアップテーブル

衝突は実際に発生しますか？

はい。私はテストプログラムを書き始めて、ハッシュの衝突が実際に発生するかどうかを確認しました。これは単なる理論上の構成ではありません。実際に発生します：

FNV-1の衝突

• creamwoveがquists

FNVと衝突します-1aの衝突

• costarringがliquid
• declinateがmacallums
• altarageはzinke
• altaragesと衝突しますzinkes

Murmur2の衝突

• cataractがperiti
• roquetteと衝突しますskivie
• shawlはstormbound
• dowlasesがtramontane liと衝突します>
• cricketingsがtwanger
• longansと衝突しますwhigs

DJB2衝突

• hetairasがmentioner
• はneurospora
• depravementと衝突しますserafins
• stylistがsubgenera
• joyfulはsynaphea
• redescribedと衝突しますurites
• dramがvivency

DJB2aの衝突

• haggadotは
• adorablenesses rentability
• playwrightと衝突しますsnush liと衝突します>
• playwrightingがsnushing
• treponematosesと衝突しますwaterbeds

CRC32衝突

• coddingがgnu
• がschlager

SuperFastHashの衝突と衝突します

• dahabiahがdrapability

変更されていない辞書からハッシュマップを作成する場合は、完全なハッシュを検討することをお勧めします https://en.wikipedia.org/wiki/Perfect_hash_function -ハッシュ関数とハッシュテーブルの構築中に、特定のデータセットについて、衝突が発生しないことを保証できます。

コメント

• こちら’（最小限の）パーフェクトハッシュの詳細 burtleburtle.net/bob/hash/perfect.html パフォーマンスデータを含みますが、’最新のプロセッサなどを使用していません。
• ‘は非常に明白ですが、衝突がないことを保証するには、キーが値と同じサイズである必要があることを指摘する価値があります。アルゴリズムが利用できる値に対する制約があります。
• @ devios1あなたの発言は無意味です。まず、ハッシュテーブルの値は、完全かどうかに関係なく、キーに依存しません。次に、完全なハッシュテーブルは、値の線形配列であり、すべてのインデックスが一意になるように作成された関数の結果によってインデックスが付けられます。
• @MarcusJ完全なハッシュは通常、100未満で使用されます。キーですが、 cmph.sourceforge.net をご覧ください…まだ範囲がはるかに短いです。
• @DavidCary何もありませんリンクはあなたの主張をサポートします。 O（1）を”衝突なし”と混同している可能性がありますが、’ tまったく同じこと。もちろん、完全なハッシュは衝突がないことを保証しますが、すべてのキーが事前にわかっていて、それらの数が比較的少ないことが必要です。 （ただし、上記のcmphへのリンクを参照してください。）

ここにハッシュ関数のリストがありますが、短いバージョンは次のとおりです。

優れたハッシュ関数が必要な場合、そして待つことはできません。djb2は、私が知っている最高の文字列ハッシュ関数の1つです。さまざまなキーとテーブルサイズのセットで優れた分散と速度を実現します

unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } 

コメント

• 実際、djb2は、そのような単純なハッシュ関数のほとんどと同様に感度がゼロであるため、このようなハッシュを簡単に破ることができます。バイアスが多すぎて衝突が多すぎて分布が悪いため、ほとんどのsmhasher品質テストで壊れます。 github.com/rurban/smhasher/blob/master/doc/bernstein 彼のcdbデータベースはそれを使用しますが、私は’パブリックアクセスでは使用しません。
• DJBはパフォーマンスと配布の観点からかなり悪いです。 ‘今日は使用しません。
• @ConradMeyer ‘賭けます、DJBは私のこの質問のように3倍で、’はおそらく最も使用可能なアルゴリズムを上回ります。配布に関しては、同意します。 2文字の文字列に対しても衝突を生成するハッシュは、’本当に良いものではありません。
• 皆さん、私には疑問があります。 djb2は悪いと言っていますが、受け入れられた回答のテスト結果はそれが良いことを示しています。
• 少なくとも、衝突が少ない賢明な素数を使用するかもしれません。 33の代わりに。 stackoverflow.com/a/2816747/21499

CityHash by Googleは、探しているアルゴリズムです。暗号化には適していませんが、一意のハッシュを生成するのには適しています。

詳細とivid = “については、ブログをご覧ください。 075eeaef5f “>

私は、ファイルをハッシュするときのさまざまなハッシュアルゴリズムの短い速度の比較をプロットしました。

個々のプロットは読み取り方法がわずかに異なるだけであり、すべてのファイルがtmpfsに保存されているため、ここでは無視できます。したがって、疑問に思っているのであれば、ベンチマークはIOバウンドではありませんでした。

• リニアスケール
• 対数目盛

アルゴリズムには次のものが含まれます：SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}。

結論：

• Murmur3、Cityhash、Spookyなどの非暗号化ハッシュ関数は非常に密接に関連しています。私のCPUにはないSSE4.2のCRC命令を使用したCPUでは、Cityhashの方が高速である可能性があることに注意してください。私の場合、SpookyHashは常にCityHashの少し前にありました。
• 暗号化ハッシュ関数を使用する場合、MD5は良いトレードオフのようですが、SHA256は MD5とSHA1の衝突の脆弱性。
• すべてのアルゴリズムの複雑さは線形です。これは、ブロック単位で機能するため、実際には驚くべきことではありません。 （読み取り方法に違いがあるかどうかを確認したかったので、右端の値を比較できます。）
• SHA256はSHA512よりも低速でした。
• のランダム性については調査しませんでした。ハッシュ関数。ただし、ここは、 IanBoydsの回答にないハッシュ関数の優れた比較です。これは、CityHashにコーナーケースでいくつかの問題があることを示しています。

プロットに使用されるソース：

• https://github.com/sahib/rmlint/tree/gh-pages/plots （醜いコードでごめんなさい）

コメント

• 線形スケールグラフは、プロットしている量を示すy軸ラベルを切り取ります。おそらく、対数目盛と同じように、”秒単位の時間”になると思います。 ‘修正する価値があります。

SHA-256などがあることは知っていますが、これらのアルゴリズムは設計されています 安全である必要があります。これは通常、一意性が低いアルゴリズムよりも低速であることを意味します。

暗号化ハッシュ関数がより一意であるという仮定は誤りであり、実際には、実際には逆方向であることがよくあります。実は：

1. 暗号化ハッシュ関数は、理想的にはランダム; liと区別できない必要があります。 >
2. ただし、暗号化されていないハッシュ関数では、可能性のある入力と良好に相互作用することが望ましいです。

これは、非暗号化ハッシュ関数の衝突がよりも少ない可能性があることを意味します。 「優れた」データセット用の暗号化されたもの—それが設計されたデータセット。

Ian Boydの回答のデータと少しの数学でこれを実際に示すことができます：誕生日の問題。セット[1, d]からランダムにn整数を選択した場合に予想される衝突ペアの数の式は、次のとおりです（Wikipediaから取得）。

n - d + d * ((d - 1) / d)^n 

プラグインn = 216,553およびd = 2 ^ 32 5.5の予想される衝突が発生します。 Ianのテストでは、ほとんどの場合、その近傍の結果が示されますが、1つの劇的な例外があります。ほとんどの関数で、衝突がゼロになりました。連続数テスト。ランダムに216,553個の32ビット数を選択し、衝突がゼロになる確率は約0.43％です。これは、1つの関数の場合のみです。ここでは、ゼロの 5つの異なるハッシュ関数ファミリーがあります。衝突！

つまり、ここで確認しているのは、Ianがテストしたハッシュが、連続する数値データセットと有利に相互作用していることです。つまり、分散しているのは最小限です。理想的な暗号化ハッシュ関数よりも広く入力します。 （補足：これは、FNV-1aとMurmurHash2が数値データセットで彼に「ランダムに見える」というIanのグラフィカルな評価が、彼自身のデータから反駁できることを意味します。そのサイズのデータセットでの衝突はゼロです。両方のハッシュ関数は、驚くほどランダムではありません！）

これは、ハッシュ関数の多くの用途にとって望ましい動作であるため、驚くことではありません。たとえば、ハッシュテーブルキーは非常によく似ています。 Ianの回答は、 MSNがかつてZIPコードハッシュテーブルで抱えていた問題に言及しています。これは、可能性が高い入力での衝突回避がランダムな動作に勝る使用法です。

ここでのもう1つの有益な比較は、CRCと暗号化ハッシュ関数の設計目標の対比です。

• CRCは、ノイズの多い通信チャネルに起因するエラーをキャッチするように設計されています。少数のビットフリップ;
• 暗号化ハッシュは、悪意のある攻撃者による変更をキャッチするように設計されています、限られた計算リソースが割り当てられているが、任意に賢い人が割り当てられています。

したがって、CRCの場合、最小限の異なる入力でランダムよりも衝突が少ない方が良いです。暗号化ハッシュを使用すると、これはノーノーです！

SHAアルゴリズム（SHA-256を含む）は設計は高速 。

実際、速度が問題になる場合があります。特に、パスワードから派生したトークンを格納するための一般的な手法は、標準の高速ハッシュアルゴリズムを10,000回実行することです（…パスワードのハッシュのハッシュのハッシュのハッシュを格納します）。

#!/usr/bin/env ruby require "securerandom" require "digest" require "benchmark" def run_random_digest(digest, count) v = SecureRandom.random_bytes(digest.block_length) count.times { v = digest.digest(v) } v end Benchmark.bmbm do |x| x.report { run_random_digest(Digest::SHA256.new, 1_000_000) } end 

出力：

Rehearsal ------------------------------------ 1.480000 0.000000 1.480000 ( 1.391229) --------------------------- total: 1.480000sec user system total real 1.400000 0.000000 1.400000 ( 1.382016) 

コメント

• ‘は比較的高速で、確かに暗号化ハッシュアルゴリズムです。しかし、OPは値をハッシュテーブルに格納したいだけであり、’暗号化ハッシュ関数が本当に適切だとは思いません。
• 質問が持ち上がりました。 （正直なところ、現在表示されています）暗号化ハッシュ関数の主題。それは’私が対応しているビットです。
• 人々を”の考えから遠ざけるためだけに、パスワードから派生したトークンを保存するための一般的な手法は、標準の高速ハッシュアルゴリズムを10,000回実行することです”-一般的ですが、’ sはただの愚かです。これらのシナリオ用に設計されたアルゴリズムがあります（例：bcrypt）。適切なツールを使用してください。
• 暗号化ハッシュはスループットが高くなるように設計されていますが、多くの場合、セットアップ、分解、.rodataや州のコストが高いことを意味します。 。ハッシュテーブルのアルゴリズムが必要な場合、通常は非常に短いキーと多くのキーがありますが、暗号化の追加の保証は必要ありません。微調整されたJenkinsを一度に1つずつ使用します。
• @ChrisMorgan：暗号的に安全なハッシュを使用するのではなく、ハッシュランダム化を使用してHashTable DoSをはるかに効率的に解決できるため、プログラムまたはすべてのハッシュテーブルでさえ、データが毎回同じバケットにグループ化されるわけではないため、’回答します。

SipHash を使用します。 多くの望ましいプロパティがあります：

• 高速。最適化された実装には1バイトあたり約1サイクルかかります。

• セキュア。 SipHashは強力なPRF（疑似ランダム関数）です。これは、ランダム関数と区別がつかないことを意味します（128ビットの秘密鍵を知らない限り）。したがって：

  • 衝突によってハッシュテーブルプローブが線形時間になることを心配する必要はありません。 SipHashを使用すると、 は、入力に関係なく、平均的なケースのパフォーマンスが得られることを知っています。

  • ハッシュベースのサービス拒否攻撃に対する耐性。

  • SipHash（特に128ビット出力のバージョン）をMACとして使用できます。 （メッセージ認証コード）。メッセージとSipHashタグを受信し、そのタグが秘密鍵を使用してSipHashを実行した場合と同じである場合、ハッシュを作成した人も秘密鍵を所有しており、メッセージも以来、ハッシュは変更されています。

コメント

• Isn ‘セキュリティが必要でない限り、SipHashはやり過ぎですか？単なる栄光のハッシュシードである128ビットキーが必要です。言うまでもなく、MurmurHash3の出力は128ビットで、SipHashの出力は64ビットのみです。明らかに、ダイジェストが大きいほど衝突の可能性は低くなります。
• @bryc違いは、悪意のある入力であっても、SipHashは引き続き正常に動作することです。 SipHashに基づくハッシュテーブルは、潜在的に敵対的なソースからのデータに使用でき、ハッシュ関数の詳細に非常に敏感な線形プロービングなどのアルゴリズムを使用できます。
• Siphash（および関連する新しいprngスタイル関数）は、セキュリティのための私のデフォルトの選択です。パフォーマンスに関しては、xxhashに勝るものはありません。ここでの議論の中でも、インターネット上にはたくさんの悪いハッシュアドバイスがあります。ランダムまたはセミランダム入力での良好なパフォーマンスは無意味です。実際の入力での最悪の場合のパフォーマンスは何ですか？悪意のある入力の結果はどうなりますか？ハッシュテーブルは最終的に攻撃ベクトルになります。

ハッシュするデータによって異なります。一部のハッシュは、テキストなどの特定のデータでより適切に機能します。一部のハッシュアルゴリズムは、特定のデータに適したものになるように特別に設計されています。

Paul Hsiehは、かつて高速ハッシュを作成しました。彼はソースコードと説明をリストしています。しかし、それはすでに殴打されました。 🙂

Javaはこれの単純な乗算を使用します-and-addアルゴリズム：

Stringオブジェクトのハッシュコードは次のように計算されます

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

intアルゴリズムを使用します。ここで、s[i]は文字列の i ​番目の文字です。 nは文字列の長さであり、^は指数を示します。 （空の文字列のハッシュ値はゼロです。）

おそらくもっと良いものがありますが、これはかなり普及していて、良いようです。速度と一意性の間のトレードオフ。

コメント

• まったく同じものを使用しない’ ‘はまだ比較的簡単に衝突するため、ここで使用されています。 ‘ 間違いなくひどいことではありませんが、もっと良いものがあります。また、’ Javaと互換性があるという重要な理由がない場合は、選択しないでください。
• それでもこれを選択する場合何らかの理由でハッシュする方法としては、少なくとも92821のようなより優れたプライムを乗数として使用できます。これにより、衝突が大幅に減少します。 stackoverflow.com/a/2816747/21499
• 代わりにFNV1aを使用することをお勧めします。 ‘も単純な乗算ベースのハッシュですが、より大きな乗数を使用するため、ハッシュがより適切に分散されます。
• ‘ s[0]*31^3 + s[1]*31^2 + s[2]*31 + s[3]を実行したくない。パワー演算子（^）を避け、次のようにします：((s[0]*31 + s[1])*31 + s[2])*31 + s[3]。
• @LeopoldoSanczykはい、コードでは繰り返し実行されます（実行する必要があります）。閉じた式で理解する方が簡単でした。

まず、独自のハッシュを実装する必要があるのはなぜですか？ ほとんどのタスクでは、実装が利用可能であると仮定して、標準ライブラリのデータ構造で良好な結果が得られるはずです（自分の教育のためにこれを行っている場合を除く）。

実際のハッシュアルゴリズムに関する限り、私の個人的なお気に入りはFNVです。 1

Cでの32ビットバージョンの実装例は次のとおりです。

unsigned long int FNV_hash(void* dataToHash, unsigned long int length) { unsigned char* p = (unsigned char *) dataToHash; unsigned long int h = 2166136261UL; unsigned long int i; for(i = 0; i < length; i++) h = (h * 16777619) ^ p[i] ; return h; } 

コメント

• FNV-1aバリアントは、ランダム性がわずかに優れています。*および^：h = (h * 16777619) ^ p[i] == > h = (h ^ p[i]) * 16777619