BT

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

| 作者: Sergio De Simone フォローする 12 人のフォロワー , 翻訳者 吉田 英人 フォローする 0 人のフォロワー 投稿日 2014年4月13日. 推定読書時間: 1 分 |

原文(投稿日: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が同じ脆弱性の影響を受けるのか,現時点では明確になっていない。

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT