c++ - 整理哈希函数

Question

在本地对象中有一个 collat​​e facet。

collat​​e facet 有一个返回 long 的 hash 方法。
http://www.cplusplus.com/reference/std/locale/collate/hash/

两个问题:

• 有人知道使用什么散列方法吗。
• 我需要一个 32 位的值。
  如果我的 long 长于 32 位，是否有人知道将散列折叠成较短版本的技术。我可以看到，如果操作不当，折叠可能会产生很多冲突(尽管我可以应对冲突，因为无论如何我都需要考虑到这一点，但我希望将它们最小化)。

注意:我不能使用 C++0x 特性
Boost 可能没问题。

Answer 1

不，没有人真正知道——它可能因一种实现而异。主要要求是(N3092，§20.8.15):

对于存在专门化哈希的所有对象类型 Key，实例化哈希应:

1. 满足Hash要求(20.2.4)，以Key为函数调用参数类型，DefaultConstructible要求(33)，CopyAssignable要求(37)，
2. 左值可交换 (20.2.2)，
3. 提供两个嵌套类型 result_type 和 argument_type，它们分别是 size_t 和 Key 的同义词，
4. 满足如果k1 == k2为真，则h(k1) == h(k2)也为真，其中h是hash类型的对象，k1和k2是Key类型的对象。

和(N3092，§20.2.4):

如果满足以下条件，则类型 H 满足哈希要求:

1. 它是一个函数对象类型(20.8)，
2. 它满足 CopyConstructible 和 Destructible (20.2.1) 的要求，
3. 下表中显示的表达式是有效的并且具有指示的语义，并且
4. 它满足本子条款中的所有其他要求。

§20.8.15 涵盖了对哈希结果的要求，§20.2.4 涵盖了哈希本身。但是，如您所见，两者都非常通用。提到的表格基本上涵盖了另外三个要求:

1. 哈希函数必须是“纯”的(即，结果仅取决于输入，而不是任何上下文、历史等)
2. 函数不得修改传递给它的参数，并且
3. 它不能抛出任何异常。

确切的算法肯定没有指定——尽管很长，上面的大部分要求实际上只是陈述要求(至少对我来说)看起来很明显。简而言之，该实现可以自由地以几乎任何它想要的方式实现散列。