对于均匀分布的 4 位值的非均匀序列的良好哈希函数？

Question

我有一个非常具体的问题：

我在 15x50 网格上分布了均匀的随机值，我想要散列的样本对应于以任何可能的网格位置为中心的 5x5 单元格正方形。

因此，样本数量可以从 25（远离边界，大多数情况）到 20、15（靠近边界）到最少 9（在角落）不等。

因此，即使单元格值是随机的，位置也会在序列长度中引入确定性变化。

哈希 table 大小是一个小数字，通常在 50 到 20 之间。

该函数将对大量随机生成的网格（一些 hundreds/thousands）进行操作，并且每个网格可能被调用数千次。网格上的位置可以认为是随机的。

我想要一个函数，它可以尽可能均匀地分布 15x50 个可能的样本。

我试过以下伪代码：

int32 hash = 0;
int i = 0; // I guess i could take any initial value and even be left uninitialized, but fixing one makes the function deterministic
foreach (value in block)
{
    hash ^= (value << (i%28))
    i++
}
hash %= table_size

但结果虽然没有严重失衡，但对我来说似乎不太顺利。可能是因为样本太小了，但是这种情况很难运行更大样本上的代码，如果一些精通计算机的人已经为我准备好了答案，我宁愿不必编写完整的测试工具:).

我不确定将值两两配对并使用通用字节哈希策略是否是最佳解决方案，尤其是因为值的数量可能是奇数。

我不得不使用第 17 个值来表示离网单元格，但这似乎引入了偏差（来自边界附近单元格的序列将有很多 "off grid" 值）。

我也不确定什么是测试各种解决方案效率的最佳方法（例如，我应该生成多少个网格才能了解性能）。

Answer 1

尽管你持怀疑态度，我还是会通过标准哈希函数将它们推送过来。如果他们是随机的（并且相对独立 - 你不会说）开始你可能不需要做太多的工作。在这种情况下，Fowler-Noll-Vo (FNV) 是一个很好的候选人。

FNV 在一系列 8 位输入上运行，而您的输入（逻辑上）是 4 位。正如您所描述的，我什至懒得打包 'two by two' 就开始了。如果您想尝试这样做，只需在逻辑上用消息长度填充奇数长度系列（显然减少到 4 位值）。

我不认为打包会改进散列。它可以为您节省少量的周期，因为它将相对昂贵的 * 替换为 << 和 |。

两种都试一下，然后反馈！

这里是 FNV1a 在 C:

中的打包和 'normal' 版本的实现

#include <inttypes.h>

static const uint32_t sFNVOffsetBasis=2166136261;
static const uint32_t sFNVPrime= 16777619;

const uint32_t FNV1aPacked4Bit(const uint8_t*const pBytes,const size_t pSize) {
    uint32_t rHash=sFNVOffsetBasis;
    for(size_t i=0;i<pSize;i+=2){
        rHash=rHash^(pBytes[i]|(pBytes[i+1]<<4));
        rHash=rHash*sFNVPrime;
    }
    if(pSize%2){//Length is odd. The loop missed the last element.
        rHash=rHash^(pBytes[pSize-1]|((pSize&0x1E)<<3));
        rHash=rHash*sFNVPrime;

    }
    return rHash;
}

const uint32_t FNV1a(const uint8_t*const pBytes,const size_t pSize) {
    uint32_t rHash=sFNVOffsetBasis;
    for(size_t i=0;i<pSize;++i){
        rHash=(rHash^pBytes[i])*sFNVPrime;
    } 
    return rHash;
}

注意：我已将其编辑为在添加长度时跳过第一位。很明显奇数长度的低位是100%偏1的，不知道长度是怎么分布的。放在开头可能比放在结尾更明智。

Answer 2

http://www.partow.net/programming/hashfunctions/

这里有一些来自各个领域专家的不同哈希函数。函数专为 8 位值而设计，但我相信您可以针对您的情况进行扩展。我不知道有什么建议，但我认为它们中的任何一个都应该比你现在的想法更有效。

你提出的当前方法的问题是值在字段 2^n 中是循环的，如果你在最后做 mod 64 例如你丢失了大部分值并且只有最后 3 个值保留在最终结果中.

对于均匀分布的 4 位值的非均匀序列的良好哈希函数？

A good hashing function for a non-uniform sequence of uniformly distributed 4 bits values?

algorithm

hash