java - 使用哈希表在 Java 中构建稀疏矩阵？

Question

在我的项目中，我正在尝试为图形构建邻接矩阵，并且出于空间和时间的考虑，我们应该使用稀疏矩阵，据我了解，使用哈希图最容易做到这一点。不幸的是，我们还必须实现一个邻接列表，我用所说的 hashmap 实现了它，并且由于我们的邻接矩阵在结构上必须不同，所以我不能对矩阵使用 hashmap。还有其他实现方式吗？

Answer 1

对于 n 维矩阵，您可以使用二叉树的变体。插入等时，您所做的是循环遍历尺寸，直到找到一片叶子。

因此，对于一个简单的二维数据集，例如 (2, 5), (10, 1), (5, 6), (3, 4) 以该顺序插入，您将得到

 (2, 5)
    \
   (10, 1)
       \
      (5, 6)
        /
    (3, 4)

(2, 5) 被插入到根目录。

(10, 1) 正确，因为 10 > 2。

(5, 6) 在 (2, 5) 的右边，因为 5 > 2。然后它在 (10, 1) 的右边，因为 6 > 1。

(3, 4) 向右 3 > 2。然后向右 4 > 1。然后向左 3 < 5。

Answer 2

Sparse Matrices上的维基百科页面列出了 6 个备选方案：

• 密钥字典 (DOK)。
• 列表列表 (LIL)
• 坐标列表（COO）
• 耶鲁格式
• 压缩稀疏行（CSR 或 CRS）
• 压缩稀疏列（CSC 或 CCS）

另一种选择是邻接列表。

最后，您还应该考虑将邻接矩阵表示为位图，将每个矩阵单元映射到特定位。（典型的 JVM 将 a 表示boolean[]为一个机器字节数组，每个字节一个布尔值。）当您考虑 Java 哈希表和列表的空间开销时，邻接矩阵需要相当大......并且稀疏......在更复杂的“稀疏”数据结构可以节省空间。

Answer 3

您可以使用列表列表或坐标列表。

Answer 4

如果您知道大小，请尝试List<SparseIntArray>使用ArrayListasList实现或普通数组。SparseIntArray[]

SparseIntArray是一个非常小的隔离类，来自 google android。

以下是我如何利用它来表示具有常见操作的稀疏矩阵。它非常节省内存。