二进制数据的便携式 hashCode 实现

Question

我正在寻找一种为二进制数据创建哈希码的可移植算法。 None 的二进制数据很长——我正在 Avro-编码密钥以供在 kafka.KeyedMessages 中使用——我们谈论的长度可能在 2 到 100 个字节之间，但大多数的键在 4 到 8 个字节中运行ge.

到目前为止，我最好的解决方案是将数据转换为十六进制字符串，然后对其执行 hashCode。我能够在 Scala 和 JavaScript 中完成这项工作。假设我已经定义了 b: Array[Byte]，Scala 看起来像这样：

b.map("%02X" format _).mkString.hashCode

在 JavaScript 中稍微详细一点——幸运的是 someone already ported 基本的 hashCode 算法到 JavaScript——但重点是能够创建一个 Hex 字符串来表示二进制数据，我可以确保散列算法适用于相同的输入。

另一方面，为了创建 hashCode，我必须创建一个两倍于原始大小的对象。幸运的是，我的大部分数据都很小，但仍然 - 必须有更好的方法来做到这一点。

我假设您可以将二进制数据强制转换为字符串，这样字符串的字节数与二进制数据的字节数相同，而不是将数据填充为其十六进制值。它会全是乱码，比可打印字符更多的是控制字符，但它仍然是一个字符串。不过，您运行是否关心可移植性问题？ Endian-ness、Unicode 等

顺便说一下，如果你读了这么多书但还不知道这一点——你不能就这样：

val b: Array[Byte] = ...
b.hashCode

幸运的是我在开始之前就已经知道了，因为我很早就运行进入了那个。

更新

根据给出的第一个答案，乍一看似乎 java.util.Arrays.hashCode(Array[Byte]) 可以解决问题。但是，如果您遵循 javadoc 线索，您会发现这就是它背后的算法，它基于 List 的算法和 byte 的算法相结合。

int hashCode = 1;
for (byte e : list)  hashCode = 31*hashCode + (e==null ? 0 : e.intValue());

如您所见，它所做的只是创建一个 Long 来表示该值。在某个时候，数字变得太大并且环绕。这不是很便携。我可以让它为 JavaScript 工作，但你必须导入 npm 模块 long。如果这样做，它看起来像这样：

function bufferHashCode(buffer) {
  const Long = require('long');
  var hashCode = new Long(1);
  for (var value of buff.values()) { hashCode = hashCode.multiply(31).add(value) }
  return hashCode
}

bufferHashCode(new Buffer([1,2,3]));
// hashCode = Long { low: 30817, high: 0, unsigned: false }

当数据回绕时，您确实会得到相同的结果，虽然我不确定为什么。在 Scala 中：

java.util.Arrays.hashCode(Array[Byte](1,2,3,4,5,6,7,8,9,10))
// res30: Int = -975991962

请注意，结果是 Int。在 JavaScript:

bufferHashCode(new Buffer([1,2,3,4,5,6,7,8,9,10]);
// hashCode = Long { low: -975991962, high: 197407, unsigned: false }

所以我必须使用 low 字节并忽略 high，否则我会得到相同的结果。

Answer 1

此功能已在 Java 标准库中可用，请查看 Arrays.hashCode() 方法。

因为您的二进制数据是 Array[Byte]，您可以通过以下方式验证它是否有效：

println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817
println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817
println(java.util.Arrays.hashCode(Array[Byte](2,2,3))) // prints 31778

更新： Java 实现将字节装箱是不正确的。当然，可以转换为 int，但没有办法绕过它。这是 Java 实现：

public static int hashCode(byte a[]) {
    if (a == null) return 0;
    int result = 1;
    for (byte element : a) result = 31 * result + element;
    return result;
}

更新 2 如果您需要的是一个 Java 脚本实现，其结果与 Scala/Java 实现相同，那么您可以扩展算法，例如，仅采用最右边的 31 位：

def hashCode(a: Array[Byte]): Int = {
  if (a == null) {
    0
  } else {
    var hash = 1
    var i: Int = 0
    while (i < a.length) {
      hash = 31 * hash + a(i)
      hash = hash & Int.MaxValue // taking only the rightmost 31 bits
      i += 1
    }
    hash
  }
}

和Java脚本：

var hashCode = function(arr) {
    if (arr == null) return 0; 
    var hash = 1;
    for (var i = 0; i < arr.length; i++) {
        hash = hash * 31 + arr[i]
        hash = hash % 0x80000000 // taking only the rightmost 31 bits in integer representation
    }
    return hash;
}

为什么这两种实现产生相同的结果？在 Java 中，整数溢出表现得好像在不损失精度的情况下执行加法，然后高于 32 的位被丢弃，& Int.MaxValue 丢弃 32^nd少量。在 JavaScript 中，对于高达 2⁵³ 的整数没有精度损失，这是表达式 31 * hash + a(i) 永远不会超过的限制。 % 0x80000000 然后表现为取最右边的 31 位。没有溢出的情况很明显。

Answer 2

这是 Java 库中使用的算法的核心：

  int result 1;
  for (byte element : a) result = 31 * result + element;

您评论：

this algorithm isn't very portable

不正确。如果我们谈论 Java，那么只要我们都同意 result 的类型，那么该算法是 100% 可移植的。

是的，计算溢出了，但它在 Java 语言的所有有效实现中以 完全相同的方式 溢出。 Java int 被指定为 32 位有符号二进制补码，发生溢出时运算符的行为是明确定义的......并且相同对于所有实现。（long 也是如此……尽管大小显然不同。）

我不是专家，但我的理解是 Scala 的数字类型具有与 Java 相同的属性。 Java脚本不同，它基于 IEE 754 双精度浮点数。然而，如果你应该能够在 Java 脚本中编写可移植的 Java 算法。（我觉得@Mifeet的版本不对...）

二进制数据的便携式 hashCode 实现

Portable hashCode implementation for binary data

javascript

java

scala

hashcode