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.如果哈希没有改变,我们从地图中获取结果,如果我们重新加载地图.

问题是计算a的散列java.util.List遍历列表的所有元素并计算它们的散列,至少为O(n).

题

我想知道的是,JVM是否会更快地计算List的哈希值,而不是通过getB(String)方法中的循环.可能这取决于hash的实现B.如果是这样,什么样的东西可以工作？简而言之,我想知道这是愚蠢还是可以带来一些性能提升.

Answer 1

在没有真正解释原因的情况下,您似乎有理由相信保持列表结构也是必不可少的.唯一合理的原因是您需要保持集合的顺序一致.如果切换到"普通"地图,则值的顺序不再是常量,例如按照将项目添加到地图的顺序保存.

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

您的问题的另一个问题是,您无法使用列表的哈希码来安全地确定更改.如果哈希码已更改,您确实确定列表也已更改.如果两个哈希码相同,您仍然无法确定列表实际上是否相同.例如,如果散列码实现基于字符串,则"1a"和"2B"的散列码是相同的.