murmurhash3関数の引数を教えてください。

Question

現在作成しているbloomfilterのプログラムでmurmurhash3を使用したいと考えているのですが、関数の引数のkey以外の意味が理解することが出来ず困っています。

Wikipediaやgithubなどで説明を探したのですが引数につい理解することができませんでした．

関数の引数がどういったもなのか教えてください。
また、murmurhashについての説明のある論文など教えていただけると幸いです。

以下が現在参考にしているプログラムになります．
uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed)
{
uint32_t h = seed;
uint32_t k;
/* Read in groups of 4. /
for (size_t i = len >>2; i; i--) {
// Here is a source of differing results across endiannesses.
// A swap here has no effects on hash properties though.
k = ((uint32_t)key);
key += sizeof(uint32_t);
h ^= murmur_32_scramble(k);
h = (h <<13) | (h >>19);
h = h * 5 + 0xe6546b64;
}
/ Read the rest. /
k = 0;
for (size_t i = len &3; i; i--) {
k <<= 8;
k |= key[i - 1];
}
// A swap is not necessary here because the preceeding loop already
// places the low bytes in the low places according to whatever endianness
// we use. Swaps only apply when the memory is copied in a chunk.
h ^= murmur_32_scramble(k);
/ Finalize. */
h ^= len;
h ^= h >>16;
h *= 0x85ebca6b;
h ^= h >>13;
h *= 0xc2b2ae35;
h ^= h >>16;
return h;
}

Answer 1

外部からの入力に基づいてデータ構造を構築する場合、そしてそのデータ構造にハッシュ値を用いる場合には意図的にハッシュ値が衝突するような入力が与えられると著しく性能が下がってしまいます。 そのような攻撃に対する対策として一部の処理をランダム化するという方法があります。

シード値としてランダムな値を与えることでそれを実現するということを意図しているようです。 (もちろんひとつのデータ構造に対しては一貫した値を使う必要があります。) ただし、 MurmurHash ではシードをランダム化しても攻撃を引き起こせる可能性があるとのことです。

シード値は計算の初期値であるに過ぎず、それ自体は何でも良いようなので、攻撃に晒される可能性がないなら決め打ちの適当な値で良いんじゃないでしょうか。

追記

key 以外の引数がわからないというのは len もわからないということでしょうか。

len は key が指すデータの長さを表しています。

Comments

[TKZ28]

回答ありがとうございます。
大変わかりやすい説明で助かりました。