enbug diary(2009-09-23)
_ 連想配列に使うハッシュ関数 unladen-swallowのissue を見て、ちょっと気になったので、昨今のハッシュ関数の事情を調べていたのですが、 一言でいうと、難しい、です。 Pythonのハッシュ関数は、今でも FNV っぽいアルゴリズムを用いています。 ただし、実際には独立して開発されていて、たまたま似ているというだけだそうです。 で、 Hash functions: An empirical comparison なんかを見ると、 Murmur2 が汎用的には奨励されていて、 FNVよりも大体速くて、場合によっては衝突も少ないという結果が出ているみたいです。 では、なぜPythonがあいもかわらずFNVっぽいのかというと、 Python 3000のハッシュアルゴリズムの議論 でも見られるように、「ランダムなハッシュ関数は望ましくない（かもしれない）」というのが根拠らしいです
.:: General Purpose Hash Function Algorithms - By Arash Partow ::.
Introduction Hash functions are by definition and implementation generally regarded as Pseudo Random Number Generators (PRNG). From this generalization it can be assumed that the performance of hash functions and comparisons between other hash functions can be determined by modelling the functions as PRNGs. Analysis techniques such a Poisson distribution can be used to analyse the collision rates
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
