java - List上hashCode()的JVM优化

Question

想象一个简单的例子:

class B{
    public final String text;
    public B(String text){
        this.text = text;
    }
}

class A {
    private List<B> bs = new ArrayList<B>;

    public B getB(String text){
        for(B b :bs){
           if(b.text.equals(text)){
               return b;
           }
        }
        return null;
    }

    [getter/setter]
}

假设对于 A 的每个实例，List<B>是大，我们需要调用getB(String) 经常。但是，假设列表也有可能发生变化(添加/删除元素，甚至重新分配)。

在这个阶段，getB(String) 的平均复杂度是 O(n)。为了改进这一点，我想知道我们是否可以使用一些巧妙的缓存。

假设我们缓存 List<B>在Map<String, B>关键是 B.text .这会提高性能，但如果列表发生更改(新元素或删除元素)或重新分配(A.bs 指向新引用)，它将不起作用。

为了解决我认为的问题，以及 Map<String, B> ，我们可以存储列表的散列 bs .当我们调用 getB(String)方法，我们计算列表的散列 bs .如果哈希没有改变，我们从 map 中获取结果，如果改变了，我们重新加载 map 。

问题是计算 java.util.List 的哈希值遍历列表的所有元素并计算它们的哈希值，这至少是 O(n)。

问题

我想知道的是，JVM 计算 List 的哈希值是否会比我在 getB(String) 中的循环更快方法。可能这取决于 B 的哈希实现.如果是这样，什么样的事情可以工作？简而言之，我想知道这是否愚蠢或可以带来一些性能改进。

Answer 1

没有实际解释原因，您似乎出于某种原因相信保持列表结构也很重要。这样做的唯一合理原因是您需要集合的顺序保持一致。如果切换到“普通” map ，值的顺序将不再恒定，例如按照您将项目添加到 map 的顺序保存。

如果您需要保持顺序(列表行为)并使用键访问单个项目，您可以使用 LinkedHashMap，它本质上加入了一个行为LinkedList 和一个 HashMap。即使 LinkedHashMap.values() 返回一个集合而不是一个列表，列表的行为在集合中也得到保证。

您的问题的另一个问题是，您不能使用列表的哈希码来安全地确定更改。如果散列码发生了变化，您确实可以确定列表也发生了变化。如果两个哈希码相同，您仍然不能确定列表实际上是否相同。例如。如果哈希码实现基于字符串，则“1a”和“2B”的哈希码相同。