FNV-1a

FNV-1aとは、めっちゃ軽いハッシュ関数です。主にハッシュテーブルやキャッシュのキー生成に使われます。

FNVの語源は「Fowler Noll Vo 1 alternate」であり、FNVは考案者である「Glenn Fowlerさん」「Landon Curt Nollさん」「Kiem-Phong Voさん」の三人の名前から取られたものです。

XORと乗算だけというシンプルさ。

/* 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];
        hash *= prime;
    }
    return hash;
}

/* 例: 文字列用ラッパ */
#include <string.h>
uint32_t fnv1a_32_str(const char *s)
{
    return fnv1a_32(s, strlen(s));
}

FNV-1aはFNV-1の改良版であり、変更点はXORと乗算の順番を入れ替えただけです。

FNV-1 = 乗算, XOR

        hash *= prime;
        hash ^= p[i];

FNV-1a = XOR, 乗算

        hash ^= p[i];
        hash *= prime;

C#での実装例

// FNV-1a 32-bit (C#)
public static class Fnv1a
{
    private const uint OffsetBasis32 = 0x811C9DC5u;
    private const uint Prime32       = 0x01000193u;

    public static uint Hash32(string text)
    {
        uint hash = OffsetBasis32;
        foreach (var ch in System.Text.Encoding.UTF8.GetBytes(text))
        {
            hash ^= ch;
            hash *= Prime32;
        }
        return hash;
    }
}

Luaでの実装例

-- FNV-1a 32-bit (Lua)
local OFFSET_BASIS_32 = 0x811C9DC5
local PRIME_32        = 0x01000193

local function fnv1a32(str)
    local hash = OFFSET_BASIS_32
    for i = 1, #str do
        local b = string.byte(str, i)
        hash = hash ~ b          -- bitwise XOR (Lua 5.3+)
        hash = (hash * PRIME_32) & 0xFFFFFFFF
    end
    return hash
end

-- 例:
-- print(string.format("%08X", fnv1a32("foobar")))