问题一个很好的哈希函数用于采访整数，字符串？

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

9975

2018-05-21 16:12

起源

你选择了什么哈希函数？ - Gumbo

对于整数只返回数字本身，字符串hashcode在java docs中描述。 - Thomas Jungblut

那个哈希的目的是什么？ - Gumbo

对于整数，我通常使用k％p，其中p =哈希表的大小并且是素数，对于字符串，我从String类中选择哈希码。这足以接受一家大型科技公司的采访吗？ - phoenix

答案:

这是一个简单的食谱有效的java第33页：

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

2018-05-21 16:32

你应该问面试官哈希函数是什么 - 这个问题的答案将决定什么样的哈希函数是合适的。

如果它是用于 散列数据结构 像hashmaps一样，你希望它尽可能简单（快速执行）并避免冲突（最常见的值映射到不同的哈希值）。一个很好的例子是对同一个整数进行整数散列 - 这是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;
}

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

2018-05-21 16:36

对于整数，我通常使用k％p，其中p =哈希表的大小并且是素数，对于字符串，我从String类中选择哈希码。这足以接受一家大型科技公司的采访吗？ - 凤凰2天前

也许不会。需要向哈希表提供哈希函数并不罕见，哈希表的实现对您来说是未知的。此外，如果您以一种依赖于使用大量存储桶的实现的方式进行散列，那么如果实现由于新的库，编译器，OS端口等而发生更改，则性能可能会降低。

就个人而言，我认为在访谈中重要的是清楚地理解通用哈希算法的理想特征，这基本上是对于任何两个输入键，其值的变化小到一位，每个位都在输出有大约50/50的翻转几率。我发现这很反直觉，因为我第一次看到的很多散列函数都使用了位移和XOR，而翻转的输入位通常会翻转一个输出位（通常在另一个位位置，因此1输入位影响很多） -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 ++的字符串哈希码时，它沿文本均匀分隔了十个字母，用作输入....

2018-05-24 08:25

“另一个有趣的见解是，当你想要一个快速和平庸的哈希” - 另一个例子，对于URI我只在分裂“/”后使用最后一个段。没有必要翻阅所有那些重复的东西 http://www.my-company.com/ 在每个URI中都是相同的东西。 - Michael Kay

问题 一个很好的哈希函数用于采访整数，字符串？

答案:

热门问题

问题一个很好的哈希函数用于采访整数，字符串？