16
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

golangで使える 軽量ハッシュアルゴリズム FNV

Last updated at Posted at 2015-06-08

influxdbのコードを読んでいて出てきた hash/fnv ってなんだ?と思って調査

概要

非常に軽量でありながら比較的高い分散を持つという特徴がある(ただし,セキュリティ用途に用いることができるほどの耐衝突性は無い)。

速度

最後に簡単な速度の比較を行った。結果として, CRC-32 よりも FNV-1 の方が 3% ほど速いという値が得られた。ただしこの結果については,厳密な測定方法を用いなかったことや,測定環境のセットアップの問題などがあり,あまり深い意味を求めることはできない。

FNV-1 と CRC-32 は,いずれもシンプルなアルゴリズムでありながらも特徴があり,プロセッサによっては速度に差が出る可能性も考えられる。 FNV-1 は乗算と XOR のみから構成されるが, CRC-32 は XOR が 2 回と AND とビットシフト,それにテーブル参照から構成されている。

これらの構成を比較すると, CRC-32 は,命令数が速度に直結しやすい(命令レベル並列性が低い)場合や,メモリ参照が高負荷である場合,テーブルがキャッシュ上に維持されないような呼び出され方が繰り返された場合などに,不利になる可能性がある。他方で FNV-1 は,乗算が高負荷である場合に不利になる可能性がある。逆に言えば,乗算さえ速ければ FNV-1 の方が有利であると考えられる。

benchmarkコードは後で書いてみよう。

FNV-1とFNV-1aの違いは?

FNV-1a hash
XORを先にするだけです。変換元のデータが32bitよりも小さい場合はハッシュ値の分散度合いが良くなります。

とりあえず動かしてみる

16
11
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16
11

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?