1

我不是在寻找有关散列信息的链接。

我不是在寻找世界上最大的哈希函数。

我对描述的小故事很感兴趣

  • 你工作的问题领域
  • 您正在使用的数据的性质
  • 在为数据设计哈希函数时，您的思考过程是什么。
  • 你对你的结果有多满意。
  • 您从可能对其他人有价值的经验中学到的东西。
4

6 回答 6

9

我考虑的第一个问题是已建立的算法是否适合我的要求。

于 2008-11-11T02:56:02.223 回答
2

从事数据仓库开发。我们有一个包含大约 9,000 行的维度。正在开发的查询包括一些非常丑陋的查询。

所以，我开始分析维度行。维度行基于列的各种组合进行聚类。聚类是从某个键到共享该键的维度行列表的映射。因此，哈希键是列值的元组。

Python 中的中间结果如下所示

{ 
    ( (col1, col2), (col3, col4) ) : [ aRow, anotherRow, row3, ... ],
    ( (col1, col2), (col3, col4) ) : [ row1, row2, row3. row4, ... ],
}

从技术上讲，这是一个倒排索引。

哈希键在构建列值元组时需要小心，部分原因是 Python 不会使用可变集合（即列表）。更重要的是，元组不是列值的简单平面列表。它们通常是二元组，试图根据键组合将维度行划分为不相交的子集

深入的哈希算法是内置的 Python 哈希。然而，选择键并不明显或容易。

于 2008-11-11T03:03:41.600 回答
1

我会支持亚当所说的：不要重新发明哈希轮

我唯一一次需要自定义散列函数是比较有向图的相等性；哈希函数让我可以非常有效地判断两个图何时不相等（当哈希值匹配时，我仍然必须进行逐节点比较才能确定）

于 2008-11-11T02:58:59.657 回答
1

我首先想到的是steal散列算法及其代码的最佳位置。当且仅当我发现没有合适的算法时，我才会使用它们作为起点来创建自己的算法。平心而论，我在这个行业已经7年了，从来没有从大学开始就创建了我自己的哈希算法。但是，如果我确实创建了自己的算法，那么最大程度地减少碰撞应该是最需要考虑的事情。你可能的价值观是什么？这个函数是否准确地分散了这些值，以便希望结果值和原始值之间存在一对一的关系。结果值是否真的分散得很好。意思是说，他们不都有共同的因素？当您执行模运算以使值更小并适合您的索引集合时，这可能会导致冲突。

于 2008-11-11T04:52:15.123 回答
1

发明散列算法很容易。发明一种有效的、有效的、有效的散列算法并非如此。

你应该问自己：

  1. 我需要一个哈希吗？
  2. 假设我确实实现了一个标准的食谱食谱（例如 Effective Java），包括所有相关要求（例如，如果 a.equals(b) 则 a.hashCode() == b.hashCode()）

如果您有两个需要比较是否相等的对象实例，那么您可能需要提供 equals() 的实现。

如果您有多个需要排序的对象实例，那么您可能需要提供 compareTo() 的实现。

如果您有一个自定义对象用作 Map 的键，那么您可能需要提供 hashCode() 的实现。

于 2008-11-11T05:18:30.080 回答
1

不完全是我的经验，但您必须考虑的一些条件：

  1. 最重要的是哈希函数应该类似于相等检查。两个相等的对象应该总是返回相同的散列（两个不相等的对象可以返回相同的散列，但这应该很少见）。

  2. 最好选择现有的散列函数，因为它们很可能在速度和分布之间有更好的平衡。

  3. 散列函数应该很快。如果生成的哈希不会产生更好的值分布，请不要让它变得更慢/更复杂。所以数字类型的哈希总是更好（同意大多数框架都有整数类型的哈希，只是说）。

  4. 哈希应该具有良好的分布，碰撞的机会必须非常少。因此，XOR 是一个糟糕的选择。换句话说，在速度和分布之间找到一个良好的平衡是关键。如果分布更好，哈希值可能会变慢。

  5. 编写函数，了解您的输出大小。如果是，int32则确保不会发生溢出。

  6. 散列函数永远不应该给出错误（除了有效的空引用）。罪魁祸首将是整数溢出。处理它。

  7. 如果您在运行时本身之前就知道您可能的输入是什么，那么就有一个函数来定位它以加快速度。

  8. 很可能散列不需要是可逆的，但如果你需要它（比如从给定的散列中取回两个数字），请相应地编写它。在一般情况下（哈希冲突），这可能不是必需的。

  9. 如果您的散列仅用于快速比较两个对象，请不要将其用于安全目的。加密哈希是完全不同的野兽。

  10. 如果您手头有多个散列函数，请运行快速测试以找出哪个更适合您的输入。测试总是比理论上的分析要好。

这些都是我想不到的。另请参阅Eric 的博客。

于 2012-12-27T10:29:35.487 回答