【JavaSE专栏30】稀疏数组稀疏在哪？为什么可以节省Java内存空间？

Designer 小郑

发布于 2023-08-02 08:03:21

6990

作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序

本文对 Java 中稀疏数组进行了介绍，讲解了稀疏数组和定义语法、应用场景和优势，并给出了样例代码。

一、什么是稀疏数组

稀疏数组是一种特殊的数组存储结构，用于表示大部分元素值为默认值或者为0的数组。在稀疏数组中，只存储非默认值或非

的元素及其对应的索引信息，从而节省了存储空间。

与普通数组相比，稀疏数组具有以下区别：

存储方式：普通数组是按照数组元素的位置顺序依次存储元素值，而稀疏数组则是存储非默认值或非

的元素以及它们的索引信息。

存储空间：由于稀疏数组只存储非默认值或非

的元素，因此相对于普通数组，可以大大减少存储空间的占用。

访问效率：由于稀疏数组需要先根据索引信息进行定位，然后再获取元素值，因此相对于普通数组，访问效率稍低一些。
灵活性：稀疏数组可以在一定程度上降低存储和传输的成本，适用于大部分元素值为默认值或者为

的情况。

在实际应用中，稀疏数组常用于稀疏矩阵、图像处理等需要节省存储空间的场景。

稀疏数组是一种特殊的数组，其中大部分元素具有相同的默认值，并且只有少数元素具有非默认值。稀疏数组通过仅存储非默认值元素的索引和值，以节省内存空间。这种数据结构通常在处理稀疏矩阵或具有大量默认值的数据集时使用。

稀疏数组的定义可以包括以下几个要素：

原始数组的大小：稀疏数组是基于原始数组创建的，需要记录原始数组的大小。
非默认值元素的个数：记录稀疏数组中非默认值元素的个数。
非默认值元素的索引和值：使用一种合适的数据结构（如哈希表、链表等）来存储非默认值元素的索引和值。

二、稀疏数组的应用场景和优势

2.1 应用场景

稀疏数组是一种用于存储大部分元素为默认值（通常为

）的数组，它通过记录非默认值元素的位置和值来节省内存空间，Java 稀疏数组的应用场景有以下四类。

矩阵和稀疏矩阵存储：在处理矩阵和稀疏矩阵时，往往大部分元素都是

或者某一默认值。使用稀疏数组可以只存储非默认值的元素，节省内存空间。对于大型矩阵或者稀疏矩阵，这种优化效果尤为明显。

图的存储：在图的存储中，通常采用邻接矩阵或邻接表的方式。对于稀疏图（边数相对于顶点数较少），采用稀疏数组可以减少存储空间，并且便于快速访问和处理非默认值元素。
文件压缩和存储：在文件系统中，特别是对于大型的文本文件或者二进制文件，使用稀疏数组可以降低存储空间的占用，提高文件的压缩效率。
缓存存储：在缓存存储中，如果缓存中的某些数据很少被访问或者保持默认值，可以使用稀疏数组来存储，减少缓存的占用空间。

2.2 优势

节省内存空间：稀疏数组只存储非默认值元素，可以大幅减少内存占用。
快速访问：由于稀疏数组记录了非默认值元素的位置，可以快速定位和访问这些元素，提高访问效率。
方便处理和操作：由于稀疏数组只存储非默认值元素，可以方便地进行插入、删除和修改操作，而不需要对整个数组进行重新分配内存。

需要注意的是，稀疏数组对于稠密数组（大部分元素非默认值）并不适用，因为这种情况下稀疏数组的存储空间占用可能会比稠密数组更大。因此，使用稀疏数组需要根据具体的应用场景和数据特点来进行合理选择。

三、如何定义稀疏数组

稀疏数组是一种数据结构，用于表示大部分元素值为默认值（通常为

或

null

）的数组。它的设计目的是为了节省存储空间，只存储非默认值的元素及其对应的索引。

以下是用 Java 实现稀疏数组的代码示例，同学们可以复制运行。

public class SparseArray {
    public static int[][] toSparseArray(int[][] array) {
        int rowCount = array.length;
        int colCount = array[0].length;
        int nonZeroCount = 0;
        
        // 统计非默认值元素个数
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < colCount; j++) {
                if (array[i][j] != 0) {
                    nonZeroCount++;
                }
            }
        }
        
        // 创建稀疏数组
        int[][] sparseArray = new int[nonZeroCount + 1][3];
        sparseArray[0][0] = rowCount;
        sparseArray[0][1] = colCount;
        sparseArray[0][2] = nonZeroCount;
        
        // 将非默认值元素存入稀疏数组
        int index = 1;
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < colCount; j++) {
                if (array[i][j] != 0) {
                    sparseArray[index][0] = i;
                    sparseArray[index][1] = j;
                    sparseArray[index][2] = array[i][j];
                    index++;
                }
            }
        }
        
        return sparseArray;
    }
    
    public static int[][] fromSparseArray(int[][] sparseArray) {
        int rowCount = sparseArray[0][0];
        int colCount = sparseArray[0][1];
        int[][] array = new int[rowCount][colCount];
        
        // 将稀疏数组中的非默认值元素还原到原始数组
        for (int i = 1; i < sparseArray.length; i++) {
            int row = sparseArray[i][0];
            int col = sparseArray[i][1];
            int value = sparseArray[i][2];
            array[row][col] = value;
        }
        
        return array;
    }
}

稀疏数组的应用场景包括以下四点，同学可以尝试使用稀疏数组。