BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース GoogleがFarmHashを公開,文字列ハッシュ関数のニューファミリー

GoogleがFarmHashを公開,文字列ハッシュ関数のニューファミリー

ブックマーク

原文(投稿日:2014/04/04)へのリンク

Googleは文字列ハッシュ関数のニューファミリーとなるFarmHashを発表した。CityHashの後継として多くのトリックやテクニックを継承するFarnHashには,いくつもの目標がある。また,いくつかの面でCityHashよりも改善されている。

同ライブラリをJyrki Alakuijala氏と共同開発した,GoogleのエンジニアであるGeoff Pike氏によると,FarmHashはGoogleのデータセンタで一般的に使用するCPUタイプを前提に開発されてはいるが,携帯電話やタブレット,PCなどにも素早く容易に適応できることを目標のひとつにしているという。これにより,既存の32ビットおよび64ビットのハッシュ実装が改善される。

CityHashと比較した場合,もうひとつの改善点として氏が挙げるのは,さまざまなプラットフォーム特有の実装上で同じインターフェースを提供できる点だ。このためFarmHashは,ハッシュテーブル用に高速で頑強だが,すべてのプラットフォームに共通でなくてもよいハッシュ関数を必要とするようなケースにも対応する。

このようなすべてのため,CityHashのコードが600行程度であるのに対して,FarmHashの実装コードは1,500行(テスト関連コードを除く)に達している。CityHashの完全な解析結果はオンラインで公開されている

今のところFarmHashには,32, 64, 128ビットプラットフォーム用の,バイト配列のためのハッシュ関数のみが含まれている。今後の開発では整数やタプル,その他のデータをサポートする計画だ。

CityHashのハッシュアルゴリズムには,複数のハッシュ衝突の発生(ハッシュフラッディング)を許容するハッシュアルゴリズム内の弱点を狙った攻撃に対する脆弱性が発見されている。これにより,同種のハッシュアルゴリズムを使用する任意のアプリケーションが急激に過負荷となる可能性があるが,CityHashに対するエクスプロイトの存在は確認されていない。この脆弱性はMurmurHashをベースとした他の主要なハッシュ実装にも影響するが,FarmHashが同じ脆弱性の影響を受けるのか,現時点では明確になっていない。

この記事に星をつける

おすすめ度
スタイル

BT