java - 为什么我的Key中的 '1'位越多，放到HashMap中的时间就越长？

Question

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

我想为 HashMap 创建一个键，它代表元素的行号和列号，当我访问映射中的该条目时，我可以重新提取两个值。我对 Java 和 C# 都不了解 - 在 C# 中我会制作一个包含 Row 和 Column 成员的 struct，但在 Java 中我很快意识到没有用户值类型。随着最后期限的临近，我做了一个安全的赌注，将 Key 设为长。我使用一些非常简单的位移位将行数据(32 位整数)存储在前 32 位中，将列数据存储在后 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 秒。这两个版本的 key 对于每个元素都是不同的，都是 long 类型，创建它们中的任何一个的实际代码的复杂性都很低。是 elements.put(key, value) 造成了 7 秒和 2 秒的区别。

我的问题是，为什么？我在这些 key 版本之间看到的区别在于，第一个版本的位始终设置为 1，而且频率更高，而第二个版本的所有最高 32 位都设置为 0。我是在追逐一个红色的鲱鱼，还是这个相当显着的差异HashMap.put 方法内部的结果？

Answer 1

看看 Long 是如何实现 hashCode() 方法的(至少在 OpenJDK 7 中是这样):

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

这意味着您的 key 被重新填充为 32 位；所有较低的位经常相互抵消，导致大量冲突，这需要 HashMap 花费额外的时间在桶中寻找空闲插槽。您的第二种方法避免了该问题，因为每个键生成的哈希码都是一个唯一值(因为您只有 23426 x 23426 = 548777476 个项目，非常适合 32 位)。

因此，原因是您的 key 选择，而不是设置位数。

但是，“用户值类型”到底是什么意思？

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; }
}

一旦您实现了 hashCode() 和 equals()，该类就可以为 Java 中的 Map 创建一个非常好的键。只需确保您没有像 Long 那样实现它的 hashCode 方法。 :)