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

Question

我计划使用一个地图,其中键是相当长的列表(~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()在比较相同的元素时,这并不能解决性能问题.

处理这种情况会有更好的想法吗？

Answer 1

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

如果你坚持使用List接口作为密钥,你应该实现KeyList你提到的.只需创建一个委托给原始List的List实现,但是重写hashCode()以返回可以在构造函数中初始化的memoized值.

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类来为您实现委派模式.

但最重要的是,确保您的列表是不可变的.不要试图在可变列表上同步破坏你的代码,它只是不起作用.