在 Java 中构建稀疏矩阵而不使用哈希表？
在我的项目中，我试图为图构建一个邻接矩阵，出于空间和时间的考虑，我们应该使用稀疏矩阵，根据我的理解，使用哈希图最容易完成。不幸的是，我们还必须实现一个邻接列表，我用所述哈希图实现了它，并且由于我们的邻接矩阵在结构上必须不同，所以我不能对矩阵使用哈希图。还有其他方法可以实现吗？
In my project, I'm trying to build an adjacency matrix for a graph, and for space and time considerations we are supposed to use a sparse matrix, which, from my understanding, is most easily done with a hashmap. Unfortunately, we also had to implement a adjacency list, which I implemented with said hashmap, and since our adjacency matrix has to be structurally different I can't use a hashmap for the matrix. Is there any other way of implementing one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
对于 n 维矩阵，您可以使用二叉树的变体。当插入等时，你所做的就是循环遍历维度，直到找到叶子。
因此，对于一个简单的二维数据集，例如按顺序插入 (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.
For an n-dimensional matrix, you can use a variant of a Binary Tree. When inserting etc, what you do is cycle through the dimensions until you find a leaf.
So for a simple two-dimensional dataset, say (2, 5), (10, 1), (5, 6), (3, 4) inserted in that order, you would get
(2, 5) gets inserted at root.
(10, 1) goes right because 10 > 2.
(5, 6) goes right of (2, 5) because 5 > 2. Then it goes right of (10, 1) because 6 > 1.
(3, 4) goes right 3 > 2. Then right 4 > 1. Then left 3 < 5.
稀疏矩阵的维基百科页面列出了 6 个替代方案：
另一种选择是 邻接列表。
最后，您还应该考虑将邻接矩阵表示为位图，将每个矩阵单元映射到特定位。 （典型的 JVM 将
boolean[]表示为机器字节数组，每个字节一个布尔值。）当您考虑 Java 哈希表和列表的空间开销时，邻接矩阵需要相当大...和稀疏...在更复杂的“稀疏”数据结构为您节省空间之前。The wikipedia page on Sparse Matrices lists 6 alternatives:
Another alternative is an Adjacency List.
Finally, you should also consider representing the adjacency matrix as a bitmap, mapping each matrix cell to a specific bit. (A typical JVM represents a
boolean[]as an array of machine bytes with one boolean per byte.) When you consider the space overheads of Java hash tables and lists, an adjacency matrix needs to be rather large ... and sparse ... before the more complicated "sparse" data structures give you a space saving.您可以使用列表列表或坐标列表。
You could use a list of lists or a coordinate list.
尝试使用
List，使用ArrayList作为List实现，或者使用普通数组SparseIntArray[]（如果您愿意）知道尺寸。SparseIntArray 是来自 google android 的一个非常小的独立类。
这是我如何利用它来表示具有常见操作的稀疏矩阵。它的内存效率非常高。
Try a
List<SparseIntArray>, usingArrayListasListimplementation, or a plain arraySparseIntArray[]if you know the size.SparseIntArray is a pretty small isolated class from google android.
Here is how I leverage it to represent Sparse matrices with common operations. It's very memory efficient.