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



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


9975
2018-05-21 16:12


起源

你选择了什么哈希函数? - Gumbo
对于整数只返回数字本身,字符串hashcode在java docs中描述。 - Thomas Jungblut
那个哈希的目的是什么? - Gumbo
对于整数,我通常使用k%p,其中p =哈希表的大小并且是素数,对于字符串,我从String类中选择哈希码。这足以接受一家大型科技公司的采访吗? - phoenix


答案:


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

  1. 在一个名为result的int变量中存储一些常量非零值,比如17。
  2. 对于对象中的每个重要字段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;
  3.  返回结果。
  4.  完成hashCode方法的编写后,问自己是否 相等的实例具有相同的哈希码。编写单元测试来验证你的直觉! 如果相等的实例具有不相等的哈希码,请弄清楚原因并解决问题。

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

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


5
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 ++的字符串哈希码时,它沿文本均匀分隔了十个字母,用作输入....


2
2018-05-24 08:25



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