使用哈希表在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）

另一种选择是Adjacency List。

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

Answer 3

你可以使用a list of lists or a coordinate list。

Answer 4

尝试List<SparseIntArray>，使用ArrayList作为List实现，或者如果你知道大小，使用普通数组SparseIntArray[]。

SparseIntArray是一个相当小的孤立类来自谷歌android。

Here is how我利用它来表示具有常见操作的稀疏矩阵。它的内存效率非常高。