针对FNV-1a哈希的该修正方案是否可行？

修正后的FNV-1算法 #

algorithm fnv-1 is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash XOR byte_of_data
        hash := hash × FNV_prime
        hash := hash XOR multiply_carry

    return hash 

其中multiply_carry指乘法运算结果中无法存入hash变量的高半部分。

原FNV哈希的核心缺陷 #

FNV哈希存在两个明显问题：

• 乘法偏差：哈希值的置位数量有持续增加的趋势
• 低位依赖：哈希的低位仅由输入数据低位的异或结果决定，未受高位数据有效影响

验证思路与测试代码 #

已知在依赖末尾对质数取模的简易哈希实现中，上述带进位异或的修正方案能可靠修复位偏差，但不确定该方案在FNV哈希中是否同样有效。以下是基于Stack Overflow答案扩展的C#测试代码，用于验证修正前FNV1a的置位偏差：

const uint FnvOffsetBasis32 = 2166136261;
const uint FnvPrime32 = 0x01000193;
long totalPop = 0;

for (long i = 0; i <= uint.MaxValue; i++)
{
    uint hash = FnvOffsetBasis32;
    hash ^= (uint)(i) & 255;
    hash *= FnvPrime32;
    hash ^= (uint)(i >> 8) & 255;
    hash *= FnvPrime32;
    hash ^= (uint)(i >> 16) & 255;
    hash *= FnvPrime32;
    hash ^= (uint)(i >> 24) & 255;
    hash *= FnvPrime32;
    //totalPop += uint.PopCount((uint)i * FnvPrime32);
    totalPop += uint.PopCount(hash);
}

const long totalInts = 0x1_0000_0000;

// Expected population: 68,719,476,736
Console.WriteLine("Expected population: {0:0,0}", 16 * totalInts);

// Actual population: 68,719,435,411
Console.WriteLine("Actual population: {0:0,0}", totalPop);

注：该测试代码为C#示例，实际应用场景为页面对齐哈希表。

内容的提问来源于stack exchange，提问作者Joshua