清单上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的散列。如果哈希没有改变，我们从映射中获取结果，如果它有，则重新加载映射。

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

问题

我想知道的是，JVM在计算列表哈希时是否比在getB(String)方法中遍历循环要快。这可能取决于B哈希的实现。如果是这样的话，什么样的事情能起作用？简而言之，我想知道这是愚蠢的，还是会带来一些性能的改善。

Answer 1

在没有真正解释原因的情况下，您似乎有理由相信保留列表结构也是必要的。唯一合理的理由是，您需要保持集合的顺序保持一致。如果切换到“普通”映射，则值的顺序不再是不变的，例如，按照将项添加到映射的顺序保持不变。

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

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

Answer 2

如果是这样的话，什么样的事情能起作用？

简单地说:不要让任何事情在你不知道的情况下改变你的列表。我怀疑你现在有这样的情况：

public List<String> getAllBs() {
    return bs;
}

..。还有一个类似的策划人。如果您停止这样做，而只是有适当的变异方法，那么您可以确保您的代码是唯一的代码突变列表.这意味着您可以记住您的地图是“脏的”，或者只是在您更改列表的同时对地图进行变异。

Answer 3

您可以实现您自己的类IndexedBArrayList，它扩展了ArrayList<B>。

然后将此功能添加到它中：

• 一个private HashMap<String, B> index
• 除了调用相应的超级方法之外，还重写ArrayList的所有mutator方法，以保持此索引哈希映射的更新。
• 一种使用散列映射的新的public B getByString(String)方法