GoogleのCityHashハッシュファミリー

Googleは無料のライセンスの下で、文字列用のCityHashハッシュ関数の新しいファミリをレイアウトしました。 これまでに、64ビットおよび128ビットのハッシュコードを受信するためのCityHash64およびCityHash128の機能が提示されました。



開発者によると、実際の状況では、CityHash64は同様のハッシュ関数を少なくとも30%の速度で上回っています。



これらのハッシュ関数は単純であるため、暗号化アプリケーションには適していませんが、理論的にはハッシュテーブルに最適です。 確かに、コードはまだ湿っていて、十分にテストされておらず( 警告を参照)、改善が必要です。



CityHash128は、少なくとも数百バイトの文字列用に最適化されており、十分な長さの文字列で、CityHash64よりも高速です。 細い線では速度が遅くなります。 Google内部では、衝突の数を最小限に抑える必要がある場合に使用されます。



Googleのデータセンターにあるプロセッサの機能を最適化しようとしましたが、ほとんどのPCやラップトップで非常に高速に動作することがわかりました。 64ビットレジスタの処理、命令レベルでの並列処理、メモリ内のアライメントされていないデータへの迅速なアクセスをサポートします。



従来、Googleの開発の主な利点はパフォーマンスです。 そして、ここでも、これは最優先事項でした。 CityHashのハッシュ関数はよく知られた開発に基づいており、主な例は2008年にAustin Applebyによって作成されたMurmurHashでした 。 これは、暗号化的に安全ではない、迅速で簡単な汎用ハッシュ関数です。 すべてのオプションは無料で使用できます。



Googleのアプローチの主な利点は、ほとんどのステップに少なくとも2つの独立した数学的アクションが含まれていることです。 判明したように、最新のCPUはこの種のコードのほうが優れています。



逆に、コードは他の一般的なハッシュ関数よりも複雑になっています。 しかし、開発者は、単純化のためではなく、パフォーマンスのために最適化することを決定し、入力データの短い行に対して特別なバージョンの関数を追加しました。



ハッシュ関数の主な利点として速度を主張する場合、開発者が特定のベンチマークを表示しなかったことは奇妙です。 以下は、オースティンアップルビーのWebサイトにある人気のあるハッシュ関数のパフォーマンスです(ハッシュ関数の速度をテストするためのSMHasherプログラムも開発しました )。



 OneAtATime-354.163715 mb /秒
 FNV-443.668038 mb /秒
 SuperFastHash-985.335173 mb /秒
 lookup3-988.080652 mb /秒
 MurmurHash 1.0-1363.293480 mb /秒
 MurmurHash 2.0-2056.885653 mb /秒



All Articles