java - 在 Java 中使用长列表作为映射键

Question

我计划使用一个映射，其中键是相当长的列表(~10/100k 的小元素):

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

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

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

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

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

有更好的办法来处理这种情况吗？

Answer 1

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

如果你坚持使用List接口(interface)作为key，你应该实现你提到的KeyList。只需创建一个 List 实现，该实现委托(delegate)给原始 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 */
}

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

但最重要的是，确保您的列表是不可变的。不要尝试通过可变列表上的同步来破坏您的代码，它根本不起作用。