「FNV-1a」の版間の差分
Administrator (トーク | 投稿記録) ページの作成:「FNV-1aとは、めっちゃ軽いハッシュ関数です。 XORと乗算だけというシンプルさ。 <source lang=c> →FNV-1a 32-bit (C): #include <stdint.h> #include <stddef.h> uint32_t fnv1a_32(const void *data, size_t len) { const uint8_t *p = (const uint8_t *)data; uint32_t hash = 0x811C9DC5u; →offset basis: const uint32_t prime = 0x01000193u; →FNV prime: for (size_t i = 0; i < len; ++i) { hash ^= p[i];…」 |
Administrator (トーク | 投稿記録) 編集の要約なし |
||
| (同じ利用者による、間の5版が非表示) | |||
| 1行目: | 1行目: | ||
FNV-1aとは、めっちゃ軽いハッシュ関数です。 | FNV-1aとは、めっちゃ軽いハッシュ関数です。 | ||
主に[[ハッシュテーブル]]や[[キャッシュ]]のキー生成に使われます。 | |||
FNVの語源は「Fowler Noll Vo 1 alternate」であり、FNVは考案者である「Glenn Fowlerさん」「Landon Curt Nollさん」「Kiem-Phong Voさん」の三人の名前から取られたものです。 | |||
[[アルゴリズム]]は[[XOR]]と[[乗算]]だけというシンプルさ。 | |||
<source lang=c> | <source lang=c> | ||
/* FNV-1a 32-bit (C) */ | /* FNV-1a 32-bit (C) */ | ||
| 28行目: | 31行目: | ||
</source> | </source> | ||
FNV-1aはFNV- | FNV-1aはFNV-1の改良版であり、変更点はXORと乗算の順番を入れ替えただけです。 | ||
* FNV-1 = 乗算, XOR | * FNV-1 = 乗算, XOR | ||
<source lang=c> | |||
hash *= prime; | |||
hash ^= p[i]; | |||
</source> | |||
* FNV-1a = XOR, 乗算 | * FNV-1a = XOR, 乗算 | ||
<source lang=c> | |||
hash ^= p[i]; | |||
hash *= prime; | |||
</source> | |||
== C#での実装例 == | == C#での実装例 == | ||