algorithm - 有序列表的复合哈希

Question

假设我有某种类型的 n 个对象（x1，x2，...，xn）的有序列表（例如，可变长度二进制数据文件）。

这些对象中的每一个都经过安全散列（例如 SHA1）以产生 m 位散列码（h1、h2、...、hn）

我现在希望将这些哈希码组合成一个复合码，该码可以唯一且安全地（忽略可忽略的碰撞概率）识别有序列表。

（假设对象很大并且不能再次读取它们的实际数据）

一种幼稚且不正确的方法是将哈希码异或在一起。这具有不希望的特性，即 (x1, x2) 将具有与 (x2, x1) 相同的复合代码。

通过什么算法可以组合哈希码以获得所需的属性？

score 2 · Accepted Answer

出于一致性和安全原因，我将通过将 SHA-1 应用于各个 SHA-1 哈希的串联来组合列表项的各个哈希。

score 1 · Accepted Answer

可能您可以使用与 java 中相同的算法来处理列表哈希，这是 32 位哈希码的示例

int hashCode = 0;
for(Element e:list) {
   hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
}

对于多层，您可以使用另一个素数。我希望你能理解这个算法的主要思想，并且可以应用于任意 m 位哈希码。

2 回答 2