12


我在面试中遇到过需要对整数或字符串使用哈希函数的情况。在这种情况下，我们应该选择哪些？在这些情况下我错了，因为我最终选择了产生大量冲突的那些，但哈希函数往往是数学上的，你无法在面试中回忆起它们。是否有任何一般性建议，至少面试官对您的整数或字符串输入方法感到满意？在“面试情况”中，哪些功能适用于两种输入

4

3 回答 3

8

这是Effective java page 33中的一个简单配方：

  1. 在名为 result 的 int 变量中存储一些常量非零值，例如 17。
  2. 对于对象中的每个重要字段 f（即 equals 方法考虑的每个字段），请执行以下操作：
    1. 计算字段的 int 哈希码 c：
      • 如果该字段是布尔值，则计算 (f ? 1 : 0)。
      • 如果字段是 byte、char、short 或 int，则计算 (int) f。
      • 如果字段是长的，则计算 (int) (f ^ (f >>> 32))。
      • 如果该字段是浮点数，则计算 Float.floatToIntBits(f)。
      • 如果该字段是双精度，则计算 Double.doubleToLongBits(f)，然后按照步骤 2.1.iii 对结果进行散列运算。
      • 如果该字段是对象引用，并且此类的 equals 方法通过递归调用 equals 来比较该字段，则在该字段上递归调用 hashCode。如果需要更复杂的比较，请为此字段计算“规范表示”并在规范表示上调用 hashCode。如果该字段的值为 null，则返回 0（或其他一些常量，但 0 是传统的）。48 第 3 章 所有对象通用的方法
      • 如果该字段是一个数组，则将其视为每个元素都是一个单独的字段。也就是说，通过递归应用这些规则来计算每个重要元素的哈希码，并在步骤 2.b 中组合这些值。如果数组字段中的每个元素都很重要，则可以使用 1.5 版中添加的 Arrays.hashCode 方法之一。
    2. 将步骤 2.1 中计算的哈希码 c 组合成 result 如下： result = 31 * result + c;
  3. 返回结果。
  4. 当你写完 hashCode 方法后，问问自己相等的实例是否有相等的哈希码。编写单元测试来验证你的直觉！如果相等的实例具有不相等的哈希码，找出原因并解决问题。
于 2011-05-21T16:32:41.080 回答
5

你应该问面试官散列函数是干什么用的——这个问题的答案将决定什么样的散列函数是合适的。

  • 如果它用于散列数据结构（如散列图），您希望它尽可能简单（执行速度快）并避免冲突（最常见的值映射到不同的散列值）。一个很好的例子是一个整数散列到相同的整数 - 这是 java.lang.Integer 中的标准 hashCode() 实现

  • 如果出于安全目的，您将需要使用加密散列函数。这些主要是为了使哈希函数难以反转或发现冲突而设计的。

  • 如果您想要快速的伪随机哈希值（例如用于模拟），那么您通常可以修改伪随机数生成器来创建这些值。我个人最喜欢的是：

public static final int hash(int a) {         
      a ^= (a << 13);
      a ^= (a >>> 17);        
      a ^= (a << 5);
      return a;   
}

如果您正在为某种形式的复合结构（例如具有多个字符的字符串、数组或具有多个字段的对象）计算散列，那么您可以使用各种技术来创建组合散列函数。我建议对组成部分的旋转哈希值进行异或，例如：

public static <T> int hashCode(T[] data) {
    int result=0;
    for(int i=0; i<data.length; i++) {
        result^=data[i].hashCode();
        result=Integer.rotateRight(result, 1);
    }
    return result;
}

请注意，上述内容不是加密安全的，但可以用于大多数其他目的。您显然会遇到冲突，但是在将大型结构散列为整数时这是不可避免的:-)

于 2011-05-21T16:36:01.450 回答
2

对于整数，我通常使用 k % p 其中 p = 哈希表的大小并且是质数，对于字符串，我从 String 类中选择哈希码。这足以应付一家大型科技公司的面试吗？– 凤凰 2 天前

也许不吧。需要为您不知道其实现的哈希表提供哈希函数的情况并不少见。此外，如果您以依赖于使用质数存储桶的实现的方式进行散列，那么如果实现因新库、编译器、操作系统端口等而发生变化，您的性能可能会下降。

就个人而言，我认为面试重要的是要清楚地了解通用哈希算法的理想特征，这基本上是对于任何两个值变化小到一位的输入键，每一位在输出有大约 50/50 的机会翻转。我发现这很违反直觉，因为我第一次看到的许多散列函数都使用移位和异或，并且翻转的输入位通常会翻转一个输出位（通常在另一个位位置，所以 1-input-bit-affects-many -output-bits 是我在 Knuth 的一本书中读到它的一个小启示。有了这些知识，您至少能够测试和评估特定的实现，而不管它们是如何实现的。

我将提到一种方法，因为它实现了这个理想并且易于记忆，尽管内存使用可能使其比数学方法慢（也可能更快，取决于硬件），是简单地使用输入中的每个字节进行查找一个随机整数表。例如，给定一个 24 位 RGB 值，并且int table[3][256],table[0][r] ^ table[1][g] ^ table[2][b]是一个很好的哈希值 - 如果输入随机分散在这些值中（而不是说递增 - 见下文）sizeof int，这确实是“完美的” 。int这种方法对于长或任意长度的键并不理想，尽管您可以开始重新访问表并移位值等。

总而言之，对于您知道输入键中的模式和/或所涉及的桶数（例如，您可能知道输入键从 1 到100 和有 128 个桶，所以你可以传递密钥而无需任何碰撞）。但是，如果输入不再符合您的期望，您可能会遇到可怕的碰撞问题，而“随机化”方法永远不会比负载 (size() / buckets) 所暗示的更糟糕。另一个有趣的见解是，当您想要一个快速且平庸的哈希时，您不必在生成哈希时合并所有输入数据：例如，上次我查看 Visual C++ 的字符串哈希代码时，它选择了十个均匀分布的字母沿着文本用作输入....

于 2011-05-24T08:25:24.720 回答