为什么我的Key中的'1'位越多,放在HashMap中的时间就越长？

Question

我正在为一个类做一个项目,该类专注于在内存中存储一​​个大部分为0值的巨大矩阵,并在其上执行一些矩阵数学运算.我的第一个想法是使用a HashMap来存储矩阵元素,并且只存储非零的元素,以避免使用大量的内存.

我想创建一个关键字,HashMap它代表元素的行号和列号,当我在地图中访问该条目时,我可以重新提取这两个值.我不知道Java和C# - 在C#中我会创建一个structwith Row和Column成员,但在Java中我很快意识到没有用户值类型.在最后期限迫在眉睫的情况下,我选择了一个安全的赌注并且做了Key很长时间.我使用一些非常简单的位移存储了前32位中的行数据(32位int)和最后32位中的列数据.[编辑:我还要注意我的HashMap初始化时使用了一个特定的初始大小,它准确地表示了我存储在其中的值的数量,这是永远不会超过的.]

[旁注:我希望能够再次提取行/列数据的原因是为了大大提高矩阵乘法的效率,O(n^2)从而开始O(n),以及更小n的引导]

实现这个结构后我注意到,从一个只给出非零元素的文本文件中读取一个23426 x 23426矩阵需要花费7秒钟,但只需要2秒钟来计算我们需要的特征值给!在选择性地评论出方法之后,我得出结论,这7秒的大部分时间用于存储我的值HashMap.

public void Set(double value, int row, int column) {
    //assemble the long key, placing row and column in adjacent sets of bits
    long key = (long)row << SIZE_BIT_MAX; //(SIZE_BIT_MAX is 32)
    key += column;
    elements.put(key, value);
}

这是设置值的代码.如果我改用这种方法:

public void Set(double value, int row, int column) {
    //create a distinct but smaller key (around 32 bits max)
    long key = (long)(row * matrixSize) + column;
    elements.put(key, value);
}

阅读只需2秒钟.这两个版本的密钥对于每个元素都是不同的,两者都是长类型,并且创建它们中的任何一个的实际代码的复杂性最小.它是elements.put(key, value)7秒和2之间的差异.

我的问题是,为什么？我看到这些关键版本之间的区别在于第一个版本的位在整个和更频繁地设置为1,而第二个版本的所有最高32位设置为0.我是否追逐红鲱鱼,或者这是一个相当显着的差异在性能方面是内部HashMap.put方法的结果？

Answer 1

看看如何Long实现该hashCode()方法(至少在OpenJDK 7中):

public int hashCode() {
    return (int)(value ^ (value >>> 32));
}

这意味着你的密钥被填充回32位; 所有低位都经常相互抵消,导致很多冲突,这需要HashMap花费额外的时间来寻找存储桶中的空闲插槽.你的第二种方法避免了这个问题,因为每个密钥生成的哈希码都是一个唯一值(因为你只有23426 x 23426 = 548777476项,它们很适合32位).

因此,resaon是您的密钥选择,但不是设置位的数量.

但是,对于"用户价值类型",您究竟是什么意思？

public class MatrixKey {
    private final int row;
    private final int column;
    public MatrixKey(int row, int column) {
        this.row = row;
        this.column = column;
    }
    public int getRow() { return row; }
    public int getColumn() { return column; }
}

Map一旦实现hashCode(),这个类就可以成为Java中非常好的密钥equals().只要确保你没有按照hashCode这种方式实现它的方法Long.:)