2

我计划使用一个地图，其中键是相当长的列表（~10/100k 的小元素）：

Map<List<K>, V> myMap = new HashMap<List<K>, V>();

默认List::hashCode()实现（在 AbstractList 中）在循环中使用所有列表元素的哈希码计算它的哈希码值。该List::equals()方法还依次比较所有列表元素，并为第一个不同的元素返回 false。

这一切都是有道理的，除了列表哈希码值没有被缓存（JDK 6）因此每次都重新计算，这使得这种使用模式非常低效（地图经常依赖哈希码）。对于不同的元素而言，问题会更少，equals()因为平均而言，第一个不同的项目的索引相当低，因此循环会提前中断（但必须比较相同列表的所有元素）。

我正在考虑用一个新的自定义类封装我的列表，KeyList将哈希码值保存在缓存中以提高性能，但是：

  1. 这不是微不足道的，因为您必须处理同步问题并实现一些列表接口方法；
  2. 这是侵入性的，因为您必须在客户端代码中使用此装饰器；
  3. 这并不能解决equals()比较相同元素时的性能问题。

处理这种情况会有更好的主意吗？

4

3 回答 3

6

对于这种情况，您的列表必须是不可变的，否则hashCode()会随着时间的推移而改变，这会破坏哈希映射。如果列表是不可变的，您可以计算hashCode()一次并将其用作包装在Long对象中的键。

如果你坚持使用 List 接口作为键，你应该实现KeyList你提到的。只需创建一个委托给原始 List 的 List 实现，但覆盖 hashCode() 以返回可以在构造函数中初始化的记忆值。

public abstract static class MemoizedHashCodeList<K> implements List<K>{
    private final long hashCode;
    private final List<K> delegate;
    public MemoizedHashCodeList(List<K> delegate) {
        this.delegate = delegate;
        hashCode = delegate.hashCode();
    }

    /* Rest of the List<K> implementation */
}

为了加快实现速度，您可以使用ForwardingList为您实现委托模式的 Google Guava 类。

但最重要的是，确保您的列表是不可变的。不要试图用可变列表上的同步来破坏你的代码，它是行不通的。

于 2013-09-23T11:24:38.640 回答
2

我认为您最好的解决方案是 KeyList 类。我建议将键列表的类隔离到一种方法，并让客户端代码从该方法请求列表引用。在其他任何地方，它都可以作为列表引用。

假设键列表是不可变的，它们需要用作 Map 键，您只需要在计算哈希码时进行同步。或者甚至跳过它，并复制 String 创建其哈希码的方式。

除了只有 32 位的标准哈希码之外，您也许可以添加一个冲突概率非常低的更强大的哈希码，然后比较它们，而不是对列表进行逐个元素的比较。使用您自己的 KeyList 类允许覆盖 equals 以及 hashCode。

于 2013-09-23T11:28:05.740 回答
0

我认为您需要重构代码并创建一个单独的对象以用作键。您几乎可以做任何事情来创建唯一键，也许将列表保存在数组中并使用数组索引，或者计算列表的哈希码并将其用作键。但是将大对象保留为键是非常不寻常的，我建议您不要这样做。

于 2013-09-23T11:39:04.760 回答