C - 为 int 三元组制作散列函数

Question

我需要为这种三元组实现某种集合数据结构:(int, int, int)，其中前两个整数来自未知范围，第三个整数通常很小。我不需要任何关于排序的信息，所以我决定使用 HashSet。我从来没有实现过类似的东西，但我读到它真的很容易搞砸并且在使用时性能不佳。

这是我打算做的。我制作了一大堆可调整大小的桶，并且(哈希函数 % 大小)给出了用于放入三元组的桶的数量。我知道我需要均匀地使用所有桶以使其高效。问题是:这样做的正确方法是什么？ “(a+b+c) mod size”是否足够有效或者我需要使用更复杂的东西？

Answer 1

不要使用简单的散列函数，因为散列远非最佳且发生冲突的可能性很高。哈希函数一直是许多研究的对象，您应该首先从wikipedia page开始。 - 对于您的使用，您应该考虑非加密的。

如果不确定，FNV-1a 哈希通常被认为是正确的(摘自维基百科):

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash XOR byte_of_data
     hash = hash × FNV_prime
return hash

如果你想要 32 位哈希，素数是 2²⁴ + 2⁸ + 0x93 = 16777619

好的是产品可以写成少量的移位和添加:

hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);

引用文献:FNV Hash