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

Question

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

Answer 1

以下是Effective java第33页的简单配方:

1. 在名为result的int变量中存储一些常量非零值,例如17.
2. 对于对象中的每个重要字段f(通过equals方法考虑的每个字段,即),执行以下操作:
   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方法通过递归调用equals来比较该字段,则在该字段上递归调用hashCode.如果需要更复杂的比较,则为该字段计算"规范表示"并在规范表示上调用hashCode.如果该字段的值为null,则返回0(或其他一些常量,但0是传统的).48第3章所有对象共有的方法
      • 如果该字段是数组,则将其视为每个元素都是单独的字段.也就是说,通过递归地应用这些规则来计算每个重要元素的哈希码,并且每步骤2.b组合这些值.如果数组字段中的每个元素都很重要,则可以使用版本1.5中添加的Arrays.hashCode方法之一.
   2. 将步骤2.1中计算的哈希码c组合成如下结果:result = 31*result + 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);
      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;
}

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