3

我必须在以下两个条件下编写一个哈希函数：

  • 我不知道Object o传递给方法的任何信息——它可以是字符串、整数或实际的自定义对象；
  • 我根本不允许打电话hashCode()。

我现在使用的方法来计算哈希码：

  1. 将对象写入字节流；
  2. 将字节流转换为字节数组；

  3. 循环遍历字节数组并通过执行以下操作计算哈希：

    哈希 = 哈希 * PRIME + byteArray[i]

我的问题是这是一种可以接受的方法，有没有办法改进它？就我个人而言，我觉得这个功能的范围太广了——没有关于对象是什么的信息，但在这种情况下我几乎没有发言权。

4

5 回答 5

3

您可以使用HashCodeBuilder.reflectionHashCode而不是实现自己的解决方案。

于 2011-07-08T13:56:09.620 回答
1

序列化方法仅适用于实际上可序列化的对象。因此，对于所有类型的对象是不可能的。

此外，这通过具有等效的对象图来比较对象，这不一定与相等的.equals()对象图相同。

例如，由相同代码（具有相同数据）创建的 StringBuilder 对象将具有相等的 OOS 输出（即也相等的哈希），whileb1.equals(b2)为 false，具有相同元素的 ArrayList 和 LinkedList 将被注册为不同，while list1.equals(list2)is true。

您可以通过创建一个 custom来避免将字节流转换为数组HashOutputStream的步骤，它只是获取字节数据并对其进行哈希处理，而不是将其保存为数组以供以后迭代。

class HashOutputStream extends OutputStream {

    private static final int PRIME = 13;
    private int hash;

    // all the other write methods delegate to this one
    public void write(int b) {
        this.hash = this.hash * PRIME + b;
    }

    public int getHash() {
        return hash;
    }
}

然后将您的 ObjectOutputStream 包裹在此类的对象周围。

y = y*13 + x您可能会查看其他校验和算法，而不是您的方法。例如，java.util.zip 包含Adler32（用于zlib格式）和CRC32（用于gzip格式）。

于 2011-07-08T14:03:41.873 回答
0

hash = (hash * PRIME + byteArray[i]) % MODULO ?

于 2011-07-08T13:45:25.040 回答
0

此外，当您使用它时，如果您想尽可能避免冲突，您可以在第 3 步中使用标准化（如果故意冲突是一个问题，则使用加密）哈希函数，例如 SHA-2 左右？

看看DigestInputStream，这也让您免去了第 2 步。

于 2011-07-08T13:45:59.203 回答
0

看看Bob Jenkins关于非加密哈希的文章。他介绍了多种方法，并讨论了它们的优势、劣势以及速度和碰撞概率之间的权衡。

如果不出意外，它将允许您证明您的算法决定是合理的。向您的教练解释为什么您选择速度而不是正确性，反之亦然。

作为起点，试试他的One-at-a-time hash：

ub4 one_at_a_time(char *key, ub4 len)
{
  ub4   hash, i;
  for (hash=0, i=0; i<len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return (hash & mask);
}

它很简单，但对更复杂的算法却出奇的好。

于 2011-07-08T14:55:05.823 回答