一个用于整型数组的C++哈希函数

Question

我需要为unordered_map专门设计哈希函数，以便我可以使用整数数组作为键。这些数组的值通常为0或1，例如int array = {0, 1, 0, 1}，但技术上没有界限。

有人可以推荐在这种情况下适用的良好哈希函数吗？或者，我可以将整数数组转换成字符串并避免专门设计哈希函数。但我担心性能问题，因为我可能会有几百万个这样的数组。

- gewizz

---

使用或模仿Boost的“范围哈希”。它是通过反复调用hash_combine构建的，该函数也在Boost中，并且应该真正成为标准。 - Kerrek SB

如果你有数百万个这样的数组，我建议使用新的算法/数据结构... - Blindy

@Blindy 你会建议使用哪些数据结构？ - gewizz

@Kerreck，http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_range_id420926.html说它不适用于无序容器。这在我的情况下不适用吗？ - gewizz

@gewizz：这个措辞有些粗糙。将无序容器“作为整体”获取确定性哈希值是不合适的[排序可能取决于负载因子和重新分配的次数]。然而，当然可以将其用作无序容器的元素哈希函数。 - sehe

keyType需要可分配吗？通常数组不是这样的。 - Tadeusz Kopec for Ukraine

Answer 1

C++ TR1 包含一个哈希模板函数。

如果你还没有，可以使用 Boost Hash。

一个实用的辅助功能想法：

#include <boost/functional/hash.hpp>

template <typename T, int N>
    static std::size_t hasharray(const T (&arr)[N])
{
     return boost::hash_range(arr, arr+N);
}

这大致相当于：

 size_t seed = 0;
 for (const T* it=arr; it!=(arr+N); ++it)
     boost::hash_combine(seed, *it);
 return seed;

不要忘记实现适当的相等比较操作，如果您正在使用此哈希进行查找。

- sehe

---

我认为应该使用 std::size_t N，因为 std::size_t 能够保证能够表示最大可能的数组大小，而 int 可能会溢出（取决于系统）。此外，它不需要是有符号类型。 - outofthecave

@outofthecave 说得好。然而，无符号类型是具有传染性的，这使得它在偏移量方面难以处理（它们可能是负数，如果 N<10，则 N-10 将会被包装回来。惊喜！）。此外，静态类型大于 2³¹ 元素的数组？那些很少见。如果你拥有它们，你也不经常对它们进行哈希处理。 - sehe

Answer 2

尝试使用lookup8哈希函数。这个函数非常快且优秀。

int key[100];
int key_size=10;
for (int i=0;i<key_size;i++) key[i]=i; //fill key with sample data
ub8 hash=hash((ub8*)key, sizeof(key[0])*key_size, 0);

UPD: 或者使用更好的函数。- t1ha

- vromanov

---

通常哈希函数是用普通的 C 语言编写的。你可以为其创建一个 C++ 封装器。 - vromanov

通常，哈希函数是用当前语言编写的。 - Puppy

你总是像 crc32、sha、md5 这样编写函数，或者使用现有的经过充分测试和高性能实现吗？ :) - vromanov

该函数过于复杂，无法在编译时使用。 - vromanov