代码之家 › 专栏 › 技术社区 › peter.murray.rust

对于普通程序员来说,是否有一个“足够好”的哈希函数?

hash language-agnostic

peter.murray.rust · 技术社区 · 15 年前

我们被告知应该为我们的类实现hashcode(),但是像我这样的大多数人都不知道该如何做,或者如果我们“弄错”了会发生什么。例如,我需要一个哈希函数来索引树中的节点( Finding the most frequent subtrees in a collection of (parse) trees )在这种情况下,我需要基于有序的子节点递归地生成哈希代码,例如

hashCode = function(child1.hashCode, child2.hashCode, ...)

在一个 recent discussion 哈希码的答案包括字符串的哈希(基于长素数和31)和位移。字符串哈希为:

// adapted from String.hashCode()
public static long hash(String string) {
  long h = 1125899906842597L; // prime
  int len = string.length();

  for (int i = 0; i < len; i++) {
    h = 31*h + string.charAt(i);
  }
  return h;
}

我对安全不感兴趣,也不介意碰撞。是否有一个“通用函数”来组合有序对象的哈希代码,这样做弊大于利(也比根本不调用它好)?

还有一个我们可以查找常见案例的网站吗?字符串、列表等)

我没有指定语言,因为我希望有通用的方法。但是,如果它是语言特定的,那么请指出语言,以及为什么它不是通用的。

更新有两个建议是使用IDE的哈希代码生成器。这似乎是一个很好的默认值;下面是NetBeans:

public int hashCode() {
    int hash = 5;
// objects
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0);
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0);
// a string
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0);
    return hash;
}

7 回复 | 直到 11 年前

dustmachine 11 年前

乔舒亚·布洛克有一个很好的hashcode()。 Effective Java . 示例第3章,“所有对象通用的方法” 是免费的(嗯,以前在Sun的旧网站上有一个页面是免费的)。如果你搜索的话,你可能仍然会在某个地方找到那一章的PDF版本)。

您还可以查看 HashCodeBuilder 在ApacheCommonsLang中,但是不要在没有引用的情况下为类复制它。我们花了很多时间来了解这一点——它会让你成为一个更好的人。

Carl Smotricz 15 年前

虽然缺少标签,但我假设你在谈论Java。

一个“懒惰”的解决方案与Eclipse3.5打包在一起,它将在按下按钮时为您生成哈希代码。toString()和equals()。很不错的!我怀疑您可以在IDEA和NetBeans中找到类似的功能。

除此之外,对于相同的输入,几乎所有一致地生成相同值的哈希函数都可以做到。这可能只会影响哈希图之类的东西的效率。

tinkertime 15 年前

如果您是在为自定义类定义哈希代码方面谈的,最好是定义所有字段哈希代码函数的某种数学连接。

在定义散列代码时,您的目标通常是最小化冲突,因此如果您这样做,您通常会很清楚。

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)...

i_am_jorf 15 年前

如果您在Windows上,可以使用 HashData() .

eulerfx 15 年前

这是一个散列代码组合函数,我使用(在C中):

public static int CombineHashCodes(params int[] hashCodes)
{
    unchecked
    {
        var result = 0;
        foreach (var hash in hashCodes)
            result = (result * 397) ^ hash;
        return result;
    }
}

直观的推理是组合方面是XOR运算符。这就是.NET 4如何处理元组:

public static int CombineHashCodes(int h1, int h2)
{
    return ((h1 << 5) + h1) ^ h2;
}

mfeingold 15 年前

要回答什么会出错的问题:如果将函数生成的哈希代码放在哈希表(字典/映射)中,它将用于查找类实例的位置。如果散列函数生成的冲突太多,散列表的性能可能与O(N)一样差。

John Leidegren 15 年前

在任何托管环境中,对象哈希函数的原始实现都是内存地址本身。如果您不关心哈希函数的属性,任何值都可以,只要表示相同值的不同实例之间存在某种等价关系。

如果您熟悉关系数据库设计,请考虑对象的主键?什么值构成主键?

说它是 a, b and c ,那么哈希代码的实现如下所示

return a.hashCode() ^ b.hashCode() ^ c.hashCode();

^是xor(exclusive或)位操作,通过这种方式,您可以将任意数量的值链接在一起以形成哈希值,并且仍然保持一个合适的排列。