编写一个强大的整数散列函数

-1

我想为散列表编写一个好的整数散列函数。即使我怀疑我的散列表不会太大（比如说大小为36的元素），生成散列值的“关键字”可能会大幅度变化，范围从0,20,21，... 11456,13444等等。在这里发布了类似的问题，我的散列函数从here提供的答案中得到启发。编写一个强大的整数散列函数

以下是我的表的结构：按照

typedef struct _list_t_ { 
    int key; 
    int value; 
    struct _list_t_ *next; 
    } list_t; 

    typedef struct _hash_table_t_ { 
    int size;  /* the size of the table */ 
    list_t **table; /* the table elements */ 
    } hash_table_t;

是我的当前散列函数：

unsigned int hash(hash_table_t *hashtable, int key) 
    { 
    unsigned int hashval; 

    hashval = 0; 
    hashval = key; 
    hashval = ((hashval >> 16)^hashval) * 0x45d9f3b; 
    hashval = ((hashval >> 16)^hashval) * 0x45d9f3b; 
    hashval = ((hashval >> 16)^hashval); 
    return hashval % hashtable->size; // MOD done to keep within the range of the table size 
    }

如上生成的散列值的“钥匙”提到急剧变化（值的范围从0,20,31，... 11456,13444等）。问题是我注意到这个哈希函数非常频繁地生成相同的哈希值。有没有一种方法可以调整它，以便以新的哈希值结束的机会更多。

来源

2013-06-21 PGOnTheGo

很难写出一个好的散列函数。使用经过良好测试的现有产品。 – 2013-06-21 16:10:42

有几个通用的散列函数和它们的实现，[这里]（http://www.partow.net/programming/hashfunctions/） – Kninnug

那么它可能是坏的，但你有客观测试它吗？如果你盯着只包含36个独特符号的强大随机输出，你肯定会看到它重复的模式。这只是人类大脑的工作方式。这并不意味着散列被破坏;它只是受到输出范围的限制。当然，如果输入不唯一，那么输出_cannot_是唯一的。 – sh1

unsigned int hash(hash_table_t *hashtable, int key)

这是一个相当难得的机会，创造一个完美的散列函数。为每个不同输入值生成唯一值的函数。你不可能做得更好。在这种情况下可能的原因是输入位的数量等于输出位的数量。典型的散列函数需要处理更多的输入位和有限数量的输出位。这造成了散列冲突的不可避免的问题。完美哈希没有这样的问题。

在这种情况下，完美哈希函数，一如既往，很简单：

unsigned int getslot(hash_table_t *hashtable, int key) 
{ 
    return (unsigned)key % hashtable->size; 
}

请注意，您所需要的散列函数和散列映射到一个槽或桶的代码来区分。我将它们组合在一个函数中，因为它们非常微不足道，并给它一个合适的名称。还要注意，像你一样添加任何熵都是毫无意义的，结果不会比原来的分布更好。只有当你有更多的输入值并且它们可以相关时，才有意义。

来源

2013-06-21 18:16:22

如果许多密钥是散列表大小的倍数（例如，128位散列表中的8的倍数），那该怎么办？采用这种方法，你*最终会遇到很多冲突，所以加扰输入位仍然是必不可少的。 – Joni

任何散列表实现的一个基本规则是槽的数量是一个主要数据。没有关于哈希的文献从未指出这一点。 –

许多实现实际上使用两个或其他组合的强大功能来调整大小，例如标准Java库中的HashMap。一个体面的哈希码实现使这是一个没有问题。 – Joni

编写一个强大的整数散列函数

回答

相关问题