java - 实现 SparseMatrix 的有效方法

Question

我有一个巨大的矩阵，但很多条目都是空的。

所以我尝试使用 AVL 树的 vector ，其中 vector 的长度约为 20⁷ 并且每个 AVL 树有大约 110,000 个节点(总共 20⁷ · 110,000 个节点)。

但是现在，当我将问题大小增加到 90,000 时，我收到“超出 GC OverHeader 限制”的错误，因为节点太多并且我已将 JVM 配置为最大堆大小为 2 GB。

我想知道是否有其他方法可以有效地实现稀疏矩阵？

如果有帮助:我不需要在创建稀疏矩阵后对其进行修改。我只需要构建一次，然后进行高效查找。

Answer 1

在 https://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix 上有一个很好的稀疏矩阵数据结构总结。但当然这一切都取决于你需要用它做什么。如果您只需要查找，我希望哈希表比平衡树更节省空间。尝试 java.util.HashMap 应该不会花很长时间。