在面试中使用一个好的哈希函数来处理整数、字符串？

Question

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

Answer 1

这是来自 Effective java page 33：

1. 将一些常量非零值（例如 17）存储在名为 result 的 int 变量中。
2. 对于对象中的每个重要字段 f（由
   equals方法，即），执行以下操作：
   1. 计算该字段的 int 哈希码 c：
      • 如果该字段是布尔值，则计算 (f ? 1 : 0)。
      • 如果字段是 byte、char、short 或 int，则计算 (int) f。
      • 如果字段为 long，则计算 (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合并为结果，如下：
      结果 = 31 * 结果 + c;
3. 返回结果。
4. 当你写完 hashCode 方法后，问问自己是否
   相同的实例具有相同的哈希码。编写单元测试来验证您的直觉！
   如果相等的实例具有不相等的哈希码，请找出原因并解决问题。

Answer 2

您应该询问面试官哈希函数的用途 - 这个问题的答案将决定哪种哈希函数是合适的。

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

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

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

public static final int hash(int a) {         
      a ^= (a << 13);
      a^=(a>>>17);        
      a ^= (a << 5);
      返回一个；   
}

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

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;
}

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

Answer 3

对于整数，我通常使用 k % p，其中 p = 哈希表的大小，并且是素数；对于字符串，我从 String 类中选择哈希码。对于一家大型科技公司的面试来说这足够了吗？ – 菲尼克斯 2 天前

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

就我个人而言，我认为重要的是面试是对通用哈希算法的理想特征的清晰理解，基本上是对于任何两个值相差仅一位的输入键，输出中的每一位都有大约 50/50 的机会翻转。我发现这非常违反直觉，因为我第一次看到的许多散列函数都使用位移位和异或，并且翻转的输入位通常会翻转一个输出位（通常在另一个位位置，因此 1-输入位影响许多当我在 Knuth 的一本书中读到 -output-bits 时，您至少能够测试和评估特定的实现，无论它们是如何实现的，

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

尽管如此，您有时可以比这种随机方法做得更好您知道输入键中的模式和/或所涉及的存储桶数量的特定情况（例如，您可能知道输入键从 1 到 100 是连续的，并且有 128 个存储桶，因此您可以通过没有任何碰撞）。然而，如果输入不再满足您的期望，您可能会遇到可怕的碰撞问题，而“随机”方法永远不会比 load (size() / buckets) 所暗示的情况更糟糕。另一个有趣的见解是，当您想要快速而平庸的散列时，您不必在生成散列时合并所有输入数据：例如，上次我查看 Visual C++ 的字符串散列代码时，它选择了均匀间隔的十个字母沿着文本用作输入......