Android 性能为王时代SparseArray和HashMap一争高下

SparseArray 是 Android 中一种高效的数据结构，用于将整数键映射到对象。它与 HashMap 类似，但为了节省内存，使用两个并行数组来存储键和值，并采用二分搜索进行查找。以下是对 SparseArray 源码的详细分析。

一、SparseArray 源码分析

1. 类定义和构造函数

SparseArray 是一个泛型类，继承自 Object。

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;

    public SparseArray() {
        this(10);  // 默认初始容量为10
    }

    public SparseArray(int initialCapacity) {
        if (initialCapacity == 0) {
            mKeys = EmptyArray.INT;
            mValues = EmptyArray.OBJECT;
        } else {
            mKeys = new int[initialCapacity];
            mValues = new Object[initialCapacity];
        }
        mSize = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 基本方法

2.1 put(int key, E value)

将键值对插入 SparseArray 中。

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.2 get(int key)

通过键获取值，如果不存在则返回默认值 null。

public E get(int key) {
    return get(key, null);
}

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 delete(int key)

删除键值对。

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10

2.4 removeAt(int index)

删除指定索引处的键值对。

public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}
1
2
3
4
5
6

2.5 gc()

垃圾回收，清理被标记删除的元素。

private void gc() {
    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }

    mGarbage = false;
    mSize = o;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.6 size()

返回键值对的数量。

public int size() {
    if (mGarbage) {
        gc();
    }
    return mSize;
}
1
2
3
4
5
6

2.7 keyAt(int index) 和 valueAt(int index)

通过索引获取键或值。

public int keyAt(int index) {
    if (mGarbage) {
        gc();
    }
    return mKeys[index];
}

public E valueAt(int index) {
    if (mGarbage) {
        gc();
    }
    return (E) mValues[index];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 辅助方法

3.1 binarySearch()

二分搜索，用于在有序数组中查找元素。

public 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; // value found
        }
    }
    return ~lo;  // value not present
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、使用示例

以下是SparseArray的简单使用示例：

SparseArray<String> sparseArray = new SparseArray<>();
sparseArray.put(1, "One");
sparseArray.put(2, "Two");
sparseArray.put(3, "Three");

// 获取值
String value = sparseArray.get(2); // "Two"

// 删除值
sparseArray.delete(3);

// 获取键和值
for (int i = 0; i < sparseArray.size(); i++) {
    int key = sparseArray.keyAt(i);
    String val = sparseArray.valueAt(i);
    Log.d("SparseArray", "Key: " + key + ", Value: " + val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

通过这种方式，我们可以高效地管理键为整数的键值对，特别适用于性能敏感的应用场景。

继续深入分析SparseArray的实现细节，并探讨其优缺点和使用场景。

三、详细实现分析

3.1 ContainerHelpers 类

ContainerHelpers 提供了 SparseArray 使用的二分搜索功能。

public class ContainerHelpers {
    public 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; // value found
            }
        }
        return ~lo;  // value not present
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

该方法通过二分查找在一个有序整数数组中定位特定值的位置。如果找到匹配值，则返回其索引；否则返回插入点的反码（即 ~lo）。

3.2 GrowingArrayUtils 类

GrowingArrayUtils 用于在数组中插入元素并自动扩展数组容量。

public class GrowingArrayUtils {
    public static int[] insert(int[] array, int currentSize, int index, int element) {
        if (currentSize + 1 > array.length) {
            int[] newArray = new int[growSize(currentSize)];
            System.arraycopy(array, 0, newArray, 0, index);
            newArray[index] = element;
            System.arraycopy(array, index, newArray, index + 1, currentSize - index);
            return newArray;
        } else {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
    }

    public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
        if (currentSize + 1 > array.length) {
            @SuppressWarnings("unchecked")
            T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(), growSize(currentSize));
            System.arraycopy(array, 0, newArray, 0, index);
            newArray[index] = element;
            System.arraycopy(array, index, newArray, index + 1, currentSize - index);
            return newArray;
        } else {
            System.arraycopy(array, index, array, index + 1, currentSize - index);
            array[index] = element;
            return array;
        }
    }

    private static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

该类提供了向数组中插入元素的方法，如果数组已满，则会扩展数组容量。growSize 方法根据当前大小决定扩展大小。

四、优缺点

4.1 优点

1. 内存效率高：SparseArray 使用并行数组，避免了 HashMap 中对象封装导致的内存开销，特别适合键是整数的情况。
2. 高效查找：通过二分查找在键数组中定位元素，查找时间复杂度为 O(log N)。
3. 自动扩展：GrowingArrayUtils 确保数组在需要时自动扩展，减少手动管理数组大小的麻烦。
4. 避免自动装箱：与 HashMap<Integer, Object> 不同，SparseArray 直接使用 int 类型键，避免了自动装箱的开销。

4.2 缺点

1. 不适合频繁删除操作：删除操作只是将值标记为 “已删除”，需要额外的垃圾回收步骤，这可能影响性能。
2. 键必须是整数：只能用于整数键的情况，不够通用。
3. 固定容量扩展：数组扩展是按固定策略进行的（当前大小的倍数扩展），在某些极端情况下可能导致不必要的内存浪费。

五、使用场景

5.1 适用场景

1. 大量键值对：适用于需要存储大量键值对且键为整数的场景，如缓存、映射关系等。
2. 高性能要求：适合内存敏感的应用，如低端设备上的应用、实时应用等。
3. 稀疏数据集：特别适用于键值对稀疏分布的场景。

5.2 不适用场景

1. 频繁插入删除：如果应用需要频繁插入和删除操作，SparseArray 的性能可能不如 HashMap。
2. 非整数键：如果键不是整数，SparseArray 无法使用。

六、实际使用示例

下面是一个实际应用场景中的示例，用于存储和查找用户会话数据：

public class SessionManager {
    private SparseArray<Session> sessionSparseArray;

    public SessionManager() {
        sessionSparseArray = new SparseArray<>();
    }

    public void addSession(int sessionId, Session session) {
        sessionSparseArray.put(sessionId, session);
    }

    public Session getSession(int sessionId) {
        return sessionSparseArray.get(sessionId);
    }

    public void removeSession(int sessionId) {
        sessionSparseArray.delete(sessionId);
    }

    public int getSessionCount() {
        return sessionSparseArray.size();
    }

    // 清理被标记删除的会话
    public void cleanUpSessions() {
        for (int i = 0; i < sessionSparseArray.size(); i++) {
            int key = sessionSparseArray.keyAt(i);
            Session session = sessionSparseArray.get(key);
            if (session.isExpired()) {
                sessionSparseArray.removeAt(i);
            }
        }
    }
}

class Session {
    private long creationTime;
    private long expiryTime;

    public Session(long creationTime, long expiryTime) {
        this.creationTime = creationTime;
        this.expiryTime = expiryTime;
    }

    public boolean isExpired() {
        return System.currentTimeMillis() > expiryTime;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

在这个示例中，SessionManager 使用 SparseArray 存储和管理用户会话。通过addSession、getSession、removeSession等方法，可以高效地管理会话数据。cleanUpSessions 方法演示了如何清理过期会话，同时展示了删除标记和垃圾回收机制。

七、总结

SparseArray 是 Android 提供的一个高效数据结构，用于整数键值对的存储和查找。它通过优化内存使用和查找性能，特别适合在性能敏感和内存有限的应用中使用。通过理解其实现原理和优缺点，可以在适当的场景中充分利用其优势。

SparseArray 是一种优化的稀疏数组，适用于键为整数的场景。它的实现通过两个并行数组和二分搜索来提高查找和存储的效率，避免了使用HashMap可能带来的内存开销。

• 存储：使用两个并行数组分别存储键和值。
• 查找：通过二分搜索快速定位键的位置。
• 垃圾回收：延迟删除机制，通过标记删除和垃圾回收减少数组重新分配次数。
• 性能优化：通过ViewHolder模式和减少对象分配，SparseArray 在大量数据操作时性能表现良好。