3

在本地对象中有一个整理方面。

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

两个问题：

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

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

4

2 回答 2

4

不，没有人真正知道——它可能因一种实现而异。主要要求是（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. 它不能抛出任何异常。

虽然肯定没有指定确切的算法——尽管篇幅很长，但上面的大多数要求实际上只是说明了（至少在我看来）看起来很明显的要求。简而言之，该实现几乎可以以任何它想要的方式自由地实现散列。

于 2010-10-12T01:14:10.817 回答
0

如果实现使用合理的散列函数，则散列值中不应该有与输入有任何特殊相关性的位。因此，如果散列函数为您提供 64 个“随机”位，但您只需要其中的 32 个，您可以随意取值的第一个/最后一个/... 32 位。你拿哪一个并不重要，因为每一位都和下一位一样随机（这就是一个好的散列函数）。

因此，获得 32 位哈希值的最简单但完全合理的方法是：

int32_t value = hash(...);

（当然，这会将 40 亿个值的组合并为一个，这看起来很多，但如果源值是目标值的 40 亿倍，就无法避免这种情况。）

于 2010-10-12T01:25:58.737 回答