Java中如何实现稀疏整数数组？求非Android内存优化方案

核心需求匹配思路 #

针对你需要的「仅存储非零值、内存高效、支持按索引快速查找」的稀疏数组需求，最优方案是参考Android SparseIntArray 的实现逻辑，在桌面Java环境中自定义轻量版实现，或使用成熟的开源替代类。

方案一：自定义轻量SparseIntArray #

参考Android SparseIntArray 的设计，用两个平行的基本类型数组分别存储索引和对应值，通过二分查找实现快速定位，既避免了HashMap的对象开销，又保证了高效的索引访问。

核心代码实现 #

public class SparseIntArray {
    private int[] mKeys;
    private int[] mValues;
    private int mSize;

    public SparseIntArray() {
        this(10); // 初始容量可按需调整
    }

    public SparseIntArray(int initialCapacity) {
        if (initialCapacity <= 0) {
            mKeys = new int[0];
            mValues = new int[0];
        } else {
            mKeys = new int[initialCapacity];
            mValues = new int[initialCapacity];
        }
        mSize = 0;
    }

    // 按索引取值，无对应值时返回0
    public int get(int key) {
        return get(key, 0);
    }

    public int get(int key, int defaultValue) {
        int index = binarySearch(mKeys, mSize, key);
        return index >= 0 ? mValues[index] : defaultValue;
    }

    // 仅存储非零值，存入零值时自动删除对应索引记录
    public void put(int key, int value) {
        if (value == 0) {
            delete(key);
            return;
        }
        int index = binarySearch(mKeys, mSize, key);
        if (index >= 0) {
            mValues[index] = value;
        } else {
            index = ~index;
            // 自动扩容逻辑
            if (mSize >= mKeys.length) {
                int newCapacity = Math.max(mSize + 1, (mSize * 3) / 2 + 1);
                int[] newKeys = new int[newCapacity];
                int[] newValues = new int[newCapacity];
                System.arraycopy(mKeys, 0, newKeys, 0, mSize);
                System.arraycopy(mValues, 0, newValues, 0, mSize);
                mKeys = newKeys;
                mValues = newValues;
            }
            // 插入新元素到对应位置
            if (mSize - index != 0) {
                System.arraycopy(mKeys, index, mKeys, index + 1, mSize - index);
                System.arraycopy(mValues, index, mValues, index + 1, mSize - index);
            }
            mKeys[index] = key;
            mValues[index] = value;
            mSize++;
        }
    }

    // 删除指定索引的记录
    public void delete(int key) {
        int index = binarySearch(mKeys, mSize, key);
        if (index >= 0) {
            removeAt(index);
        }
    }

    private void removeAt(int index) {
        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - index - 1);
        System.arraycopy(mValues, index + 1, mValues, index, mSize - index - 1);
        mSize--;
    }

    // 获取当前存储的非零元素数量
    public int size() {
        return mSize;
    }

    // 二分查找核心方法，定位索引位置
    private static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;
        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid; // 找到匹配索引
            }
        }
        return ~lo; // 未找到，返回插入位置的取反值
    }
}

方案优势 #

• 内存极致优化：用基本类型数组存储，无额外对象开销，仅保留非零值的索引与对应数据，完全符合你的内存需求。
• 查找效率高：二分查找实现O(log n)的访问速度，接近原生数组的O(1)效率，远优于链表或普通ArrayList。
• 用法贴近原生数组：get(int index)和put(int index, int value)的调用逻辑与原生数组一致，无学习成本。

方案二：使用Guava的SparseIntArray #

如果不想自己实现，可以直接使用Google Guava库中的com.google.common.primitives.SparseIntArray，它是桌面Java环境下的成熟实现，逻辑与Android版本一致，同样通过平行数组存储，内存效率高，支持按索引快速访问。

基础用法示例 #

import com.google.common.primitives.SparseIntArray;

public class SparseArrayDemo {
    public static void main(String[] args) {
        SparseIntArray sparseArray = new SparseIntArray();
        sparseArray.put(5, 100); // 存储索引5的非零值
        sparseArray.put(10, 200); // 存储索引10的非零值
        
        int val5 = sparseArray.get(5); // 获取索引5的值，返回100
        int val3 = sparseArray.get(3, 0); // 索引3无值，返回默认值0
        
        sparseArray.delete(5); // 删除索引5的记录
    }
}

内容的提问来源于stack exchange，提问作者Leaderboard