二进制散列函数系列

我正在寻找散列函数F1，.. Fn的系列，其中每个Fi映射[0,1]中的任何键。我的第一个实现是Fi（k）= F（k，i）= hash（i，hash（k，0））。这里hash是这里提供的hashlittle函数（http://burtleburtle.net/bob/c/lookup3.c）。我还没有仔细研究过究竟做了什么。二进制散列函数系列

由于尖锐的读者会注意到，这将失败。我的问题是如何有效实现这一点。我的目标是平均最小化对于任何给定k1，k2对的最大i，其中Fi（k1）== Fi（k2）。当然它应该也是很快..

来源

2010-07-01 Sandeep

那么，我已经看了一下引擎盖。

uint32_t hashlittle(const void *key, size_t length, uint32_t initval) 
{ 
    union { const void *ptr; size_t i; } u;  /* needed for Mac Powerbook G4 */ 

    u.ptr = key; 
    if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {

写入u.ptr然后阅读u.i是未定义的行为。

编辑

我想我现在明白了。你基本上需要使用两个参数作为输入的散列函数。你几乎可以使用任何散列函数。

散列函数接受一个任意比特大小的一个数据包，并将其转换成一个固定的比特大小的一个数据包：

hashval = Hash(data, len);

需要，其中一个附加的参数，并给出内的使用的功能的转型吧？

hashval = Hash(data, len, addval);

最简单的方法是将额外的值连接到数据包：

memcpy((char *)data + len, &addval, sizeof(addval)); 
hashval = Hash(data, len + sizeof(addval));

如果有可用的源代码，另一种方法是修改它使用新的参数作为初始化为内部散列计算。这完全是在做什么。

Before: 
uint32_t Hash (const void *data, size_t len) 
{ 
    uint32_t hashval = 0; 
    .... 
    return (hashval); 
} 

After: 
uint32_t Hash (const void *data, size_t len, uint32_t init) 
{ 
    uint32_t hashval = init; 
    .... 
    return (hashval); 
}

，此选项可能有点难做，因为内部状态可以比单hashval得多，并且初始化可以说是相当复杂的，而不是简单地用0。hashlittle的是：

/* Set up the internal state */ 
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;

来源

2010-07-01 06:56:01 Secure

恐怕我不太明白。你是说在lookup3.c中的函数没有正确实现。我的问题并不是关于lookup3.c的用法，而是关于这种情况下散列函数的适当选择。我在这里记录的是我目前的做法。 -Sandeep – Sandeep 2010-07-01 13:38:53

“没有正确实施”......你可以这么说，是的。我认为这是一个不成熟优化恶习的完美例子。他试图通过以32位为单位读取数据而不是逐字节读取数据（如果数据未以此方式初始化，这本身又是未定义的行为），并且必须跳过这么多的循环，包括单独的函数小型和大型机器，这简直荒谬。自从你提到它之后，它似乎对你来说已经足够重要了，而且我总是对这样的事情感兴趣，所以我看了一下。 – Secure 2010-07-01 21:53:12

对于你的问题，对不起，我不明白。 – Secure 2010-07-01 22:00:56

二进制散列函数系列

回答

相关问题