1

我有一个应用程序，它将某种对象（例如 type MyClass）的值存储到许多不同的Map<String, MyClass>映射中。

该应用程序需要

  • 将不同映射中的对象引用获取到单个集合（联合）
  • 对单个集合进行排序（以应用顺序）
  • 计算连续集合之间的差异（用于检测变化）
  • 从每个集合的所有对象中产生一个哈希值

（统一）集合中对象的顺序很重要。

为了实现排序，对象（映射值）使用addAll(), in放置ArrayList并通过 排序Collections.sort()。顺序定义在 中，它通过比较它封装的一些字符串字段（比如， ）MyClass来实现接口。ComparatormyField

排序完成后，会生成来自所有对象的唯一签名。对于具有相同 值的对象，此签名需要相同，myField目前通过字符串连接（使用toLowerCase()和 a StringBuilder）然后对结果字符串进行散列处理，该字符串可能有几千个字符长。

有没有更有效的方法来做（任何或全部）上述（复制、排序、比较和散列）？

4

3 回答 3

3

是的，有更好的方法。简单地散列哈希：

List<String> strings;

int hash = 0;
for (String string : strings)
    hash += hash * 31 + string.hashCode();

这将几乎不使用任何内存，速度非常快，并且会产生与您的 StringBuilder 方法相同强度的哈希码。

于 2012-05-11T01:06:03.047 回答
3

如果您需要一个唯一的签名，那么您（至少在概念上）需要：

  • 将相关数据连接成字符串或缓冲区；
  • 使用强哈希函数对该数据进行哈希处理。

我说“概念上”，因为您可以在不将所有数据实际复制到缓冲区的情况下即时计算哈希：这取决于您的特定应用程序这样做的方便程度。

Java 中标准使用的 32 位哈希码通常太弱，无法为您提供唯一代码。

我建议您至少使用 64 位散列函数（我的一篇文章中有一个 64 位散列函数的示例实现，可能会有所帮助）。为了更好地保证唯一性，像 MD5 这样更强大的散列函数会更理想，但会带来一点不便，即生成的散列码太宽而无法存储在原语中。（这是您需要做出的权衡：64 位强哈希通常有助于保证几百万个对象中所有意图和目的的唯一性；MD5 以更广泛的哈希码为代价为您提供了更强大的保证。）

PS我前几天对一个类似的问题给出了这个答案，这也可能有帮助。

于 2012-05-11T01:14:19.140 回答
1

假设您真正想要的只是一个以独特方式描述集合的组合哈希（因此内部排序并不重要）并且仅取决于 myField，我建议：

long hash = 0
for map in maps:
    for key in keys:
        if key in map:
            hash = hash + 64bithash(map[key].myfield)

其中添加的都是有效的模块 2^64。这将为您提供整个集合的散列，该散列可能大到足以唯一（64 位），不依赖于排序（2+3 = 3+2），并且不需要排序或存储在其他结构中（所以会很快）。

警告这假设顺序不重要。可能是您的排序使用了比 myfield 其他的东西，因此有效的哈希取决于 myfield和排序中使用的信息。在这种情况下，上述功能将无法发挥同等作用（但可以通过在 has 中包含用于订购的信息来实现）。

于 2012-05-11T01:42:55.150 回答