SparseArray（稀疏数组）的介绍和应用

Bertha 。 2023-06-29 02:21 28阅读 0赞

> 博主声明：  
> 转载请在开头附加本文链接及作者信息，并标记为转载。本文由博主 威威喵 原创，请多支持与指教。  
> 本文首发于此 博主：威威喵 | 博客主页：[https://blog.csdn.net/smile\_running][https_blog.csdn.net_smile_running]

##### 稀疏数组概念和特点介绍 #####

Sparse 翻译过来是稀疏、缺少的意思，SparseArray是稀疏的数组。它应用场景是相对稀少的数据，一般是几百以内的数据性能相对 HashMap 要好，大概提升 0-50% 的性能。SparseArray 是用 Integer 作为键映射对象。

SparseArray 不需要对 key 和 value 进行 auto-boxing（自动装箱），将原始类型封装为对象类型，比如把 int 类型封装成 Integer 类型。

插入 10W 条数据的存储使用 DDMS 查看，HashMap 的存储空间 14M 左右，而SparseArray 只有 8M 左右，少了近 40% 的内存。SparseArray 正序插入效率比起倒序插入快了几乎是 10 倍。

如果是按照 1、3、2 的顺序排列进行插入，但是在 SparseArray 内部会按照正序进行重新排列，这时因为 SparseArray 在检索数据的时候使用的是二分查找（二分法必须是有序），所以每次插入新数据的时候 SparseArray 都需要重新排序，逆序是最差情况。

##### 五子棋游戏 #####

以上的概念介绍，看看就好了，网上都有，所以就不再多说的。  
参考如下，可以自行看看：  
https://www.cnblogs.com/Diyo/p/11305850.html  
https://www.jianshu.com/p/081b78dfe9f6

接下来，我讲讲我的理解。我直接从一个案例来分析，这个案例其实我们都有玩过，它是一个**五子棋游戏**，五子棋玩法挺简单的，其中有这样一个应用场景。比如，我需要将棋盘上的白子和黑子给保存起来，因为玩家可能要**存档**。  
存档呢，意味着要存入本地，那么如何将棋盘上的棋子保存起来，想必大家可能会想到一种最直接的方法，就是使用**二维数组**。

比如，这是一个 6 \* 5 的棋盘  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
我们用二维数组来存储的话，就应该是这样的

// 6*5 的二维数组
    	private static int[][] array = new int[][]{
        
    		{
        0,3,0,0,0},
    		{
        0,0,0,7,0},
    		{
        0,0,0,0,0},
    		{
        0,0,0,0,0},
    		{
        0,0,0,0,0},
    		{
        0,0,0,0,0}
    	};

##### 引出的问题 #####

可以看到，这个二维数组，其实没多大问题。可是如果要进行存储的话，那数组中绝大部分元素的值是 0 的，几乎没有意义。真正的有效值，**只有 3 和 7**，就代表图上的棋子**坐标**。  
如果将这样一个二维数组存到磁盘或者内存中时，它占用的内存空间是 6 \* 5 \* int 个字节。

##### SparseArray（稀疏数组）原理介绍 #####

SparseArray 的原理：**将数组中大部分为 0 或者是同一个值的的元素保存起来，第一行存放二维数组的 行 和 列 以及元素有效值个数，用 行列 来标记不同与其它的元素值和它的位置。**  
稀疏数组有一个特点，那就是它的列是固定的，只有 3 列，行数 = 有效值的数量 + 1，因为第 0 行用于存储二维数组信息。  
所以呢，它就会将棋盘的二维数组，转为如下的样子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
这样的话，从刚刚的 6 \* 5 的数组，一下子变成了 3 \* 3 的数组，占用的内存显然更加低了。

##### 二维数组 —> 稀疏数组 #####

其实，如果我们知道了稀疏数组是什么原理，它是如何将二维数组转换的话，那么在代码方面，应该问题不大。以下是我写的一个**二维数组转稀疏数组**的代码：

/**
    	 * 二维数组 -> 稀疏数组
    	 * @param arrs
    	 */
    	public static void arrayToSparseArray(int[][] arrs) {
        
    		int row = arrs.length;
    		int col = arrs[0].length;
    		int valCount = 0;
    
    		// 用于存储临时元素
    		int size = row * col;
    		int tempI[] = new int[size];
    		int tempJ[] = new int[size];
    		int tempArray[] = new int[size];
    
    		// 获取二维数组中的有效值
    		for (int i = 0; i < row; i++) {
        
    			for (int j = 0; j < col; j++) {
        
    				if (arrs[i][j] > 0) {
        
    					tempI[valCount] = i;
    					tempJ[valCount] = j;
    					tempArray[valCount] = arrs[i][j];
    
    					valCount++;
    					System.out.println("i = " + i + ", j = " + j
    							+ ", realVal = " + arrs[i][j]);
    				}
    			}
    		}
    
    		int spRow = valCount + 1;// 行数 = 有效值 + 1
    		int[][] spArray = new int[spRow][3];
    		// 设置稀疏数组第 0 行的值
    		spArray[0][0] = row;
    		spArray[0][1] = col;
    		spArray[0][2] = valCount;
    
    		// 为稀疏数组赋值
    		for (int i = 0; i < valCount; i++) {
        
    			spArray[i + 1][0] = tempI[i];
    			spArray[i + 1][1] = tempJ[i];
    			spArray[i + 1][2] = tempArray[i];
    		}
    
    		System.out.println("========================");
    		printArray(spArray);
    		System.out.println("========================");
    		sparseArrayToArray(spArray);
    	}

##### 稀疏数组 —> 二维数组 #####

稀疏数组转二维数组也同理，转换思路反过来就行

/**
    	 * 稀疏数组 -> 二维数组
    	 * @param arrs
    	 */
    	public static void sparseArrayToArray(int[][] arrs) {
        
    		// 获取稀疏数组中第一行保存的二维数组的行、列和有效值个数
    		int row = arrs[0][0];
    		int col = arrs[0][1];
    		int valCount = arrs[0][2];
    
    		// 用于存储临时元素
    		int tempI[] = new int[valCount];
    		int tempJ[] = new int[valCount];
    		int tempArray[] = new int[valCount];
    
    		// 获取稀疏数组中的 i,j,val，做临时保存
    		for (int i = 0; i < valCount; i++) {
        
    			tempI[i] = arrs[i + 1][0];
    			tempJ[i] = arrs[i + 1][1];
    			tempArray[i] = arrs[i + 1][2];
    		}
    
    		// 初始化一个默认为 0 的二维数组
    		int[][] array = new int[row][col];
    		for (int i = 0; i < row; i++) {
        
    			for (int j = 0; j < col; j++) {
        
    				array[i][j] = 0;
    			}
    		}
    
    		// 为二维数组设置有效值
    		for (int i = 0; i < valCount; i++) {
        
    			array[tempI[i]][tempJ[i]] = tempArray[i];
    		}
    
    
    		printArray(array);
    	}

打印数组中的元素：

public static void printArray(int[][] arrs) {
        
    		int row = arrs.length;
    		int col = arrs[0].length;
    		for (int i = 0; i < row; i++) {
        
    			for (int j = 0; j < col; j++) {
        
    				System.out.println("i = " + i + ", j = " + j + ", val = "
    						+ arrs[i][j]);
    			}
    		}
    	}

代码就不做过多的解释了，比较简单易懂。

[https_blog.csdn.net_smile_running]: https://blog.csdn.net/smile_running
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200109213317558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020010921474543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70