设计散列函数时你会考虑哪些问题？

Question

我不是在寻找哈希信息的链接。

我不是在寻找世界上最伟大的散列函数。

我感兴趣的描述

• 问题域你
• 数据的性质进行工作微型小说选刊你用
• 工作你的思维过程是在设计散列函数是什么为您的数据。
• 你对你的结果有多开心。
• 你从经验中学到了什么，可能对他人有价值。

Answer 1

做数据仓库开发。我们有一个约9000行的维度。正在开发的查询包含一些非常难看的查询。

所以，我开始分析维度行。维度行根据列的各种组合进行聚类。群集是从某个关键点到共享该关键点的维度行列表的映射。然后，哈希键是列值的元组。

的中间结果，在Python，看起来像这样

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

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

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

哈希算法深入深入，是内置Python哈希。然而，选择钥匙并不明显，也不容易。

Answer 2

我认为的第一个问题是，一个已建立的算法是否适合我的要求。

Answer 3

我第二亚当说：不重新发明轮子哈希

我曾经所需要的只是时间的自定义哈希函数是比较有向图的平等;哈希函数让我非常有效地告诉当两个图是不是相等（当哈希值匹配时，我仍然必须逐个节点比较确定）

Answer 4

我首先想到的是steal哈希算法及其代码的最佳位置。当且仅当我找不到合适的算法时，我将它们作为创建我自己的起点。公平起见，我已经在这个行业工作了7年，并且我从从来没有自大学以来创建了我自己的散列算法。 但是，如果我确实创建了自己的算法，最小化碰撞应该是最需要考虑的事情。你可能的价值是什么？该函数是否准确地分散这些值，以便希望得到的值与原始值之间存在一对一的关系。结果值是否确实分散？意思是说，它们并不都有共同的因素？这可能会导致碰撞，当你进行模数运算时，使值变小并适合你的索引集合。

Answer 5

发明一种散列算法很简单。发明一个正在工作,高效和有效哈希算法不是。

你应该问自己：

1. 我需要有一个哈希呢？
2. 假设当时我实现一个标准的食谱配方（如有效的Java），包括所有相关的要求（例如，如果a.equals（B），然后a.hashCode（）== b.hashCode（））

如果您有需要平等被比较对象的两个实例，那么你可能需要提供的equals（）的实现。

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

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

Answer 6

不完全是我的经验，但你们中的一些具备条件的考虑：

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

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

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

4. 哈希值应该有很好的分布，碰撞几率要少得多。因此XOR是一个不好的选择。 换句话说求速度分布之间的良好的平衡是关键。如果分布更好，机会可能会更慢。

5. 编写知道你的输出大小的函数。如果是int32则确保不会发生溢出。

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

7. 如果您在运行时间之前知道您的可能输入是什么，那么有一个函数来加速这些事情。

8. 大多数哈希函数不需要是可逆的，但如果您需要它（比如说从给定哈希中得到两个数字），请相应地写出它。这在一般情况下（哈希碰撞）可能不是要求。

9. 如果您的哈希值仅用于快速比较两个对象，则不要将其用于安全目的。 Cryptographic hashing是完全不同的野兽。

10. 如果你手边有多个散列函数，那么运行快速测试来找出哪个更适合你的输入。测试总是比理论分析更好。

这些是我的头顶。见Eric's blog additionally。