FirefoxやRustコンパイラ内で使われているハッシュ関数「FxHash」について調べてみた

FxHashとは

FxHashは暗号的に安全でない高速なハッシュ関数です。
64bit環境では64bitいっぺんに処理できることが強みでFirefoxやrustcの内部で使うハッシュマップなどに使われています。
rustcではFNV(これはバイト単位で処理する)からFxHashに変更することで衝突が少し増えたもののスピードが速いので全体としては性能の改善に繋がりました。 PR

参考:
https://searchfox.org/mozilla-central/source/mfbt/HashFunctions.h
https://github.com/cbreeden/fxhash
https://github.com/rust-lang/rustc-hash

アルゴリズム

FxHashのアルゴリズムは超簡単です。

わかりやすさのためにrustのコードをrustc_hashより抜粋

pub struct FxHasher {
    hash: usize,
}

# [cfg(target_pointer_width = "32")]
const K: usize = 0x9e3779b9;
# [cfg(target_pointer_width = "64")]
const K: usize = 0x517cc1b727220a95;

impl Default for FxHasher {
    #[inline]
    fn default() -> FxHasher {
        FxHasher { hash: 0 }
    }
}

impl FxHasher {
    #[inline]
    fn add_to_hash(&mut self, i: usize) {
        self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
    }
}

メインの処理は、

self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);

だけです。

ここでKの値は、
32bitの場合は黄金比、

# python
hex(int((math.sqrt(5) - 1) / 2 * (2 ** 32)))

64bitの場合は円周率

# python
hex(int(1 / math.pi * 2**64))

から導出されています。

解説

入力の最初の32/64ビット

まず、self.hashが0のデフォルトの状態、つまりハッシュ対象が32/64bit以内の場合を考えると、

self.hash = i.wrapping_mul(K);

とただ掛け算しているだけになり、これはKが黄金比の場合、Fibonacci Hashingと呼ばれ出力がよく分散するらしいです。（よくわかってない）
ただ、64bitの場合はKを黄金比にすると偶数となってしまい、そうすると出力が必ず偶数になってしまい良くないので円周率(これは奇数になる)を使っているらしいです。参考 (結局Kが無理数(に近い整数)なら割と何でも良さそう?)
また、オリジナルのソースコードではKは

• 奇数
• 各ビットの1/0の割合が大体半々

なら何でも良いと書いてあります。

入力の32/64ビット以降

ハッシュ対象が32/64bitより大きい場合は32/64bitづつに区切ってハッシュ値を蓄積していくことになります

再掲

self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);

ここではまずself.hashを左に5回転させています。特別5でなくても構いませんが偶数だと回転し続けたときのパターン数が減ってしまうので奇数のほうが良いです(もっと言えば素数だと良い?)。
ちなみにこの左回転はThe Art of Computer Programmingの6.4に載っているG. D. Knottが提唱した、複数語のハッシュ値を単純に加算やxorで合成すると(X, Y)と(Y, X)のハッシュ値が衝突してしまうので事前に回転させるという手法をもってきたものだと思います。たしかに、ここで回転しないと(X, Y)と(Y, X)のハッシュ値が同じになってしまいます。

それから入力とxorを取ったあとで掛け算をします。xorが掛け算の後だとself.hashが0のときに入力をそのまま出力してしまうので良くありません。

これで終わりです。

歴史

• 2012年 Firefoxの内部で実装される。このときは他にspookyhash、murmurhash3、cityhashなどが検討されていた
  • https://bugzilla.mozilla.org/show_bug.cgi?id=729952
• 2016年 rustc内で使われるようになる。このときに64bitへの拡張が行われる。FxHashという名前もここで初めて付いた？
  • https://github.com/rust-lang/rust/pull/37229