Update SparseArray docs to be more informative.

Change-Id: I5d8d17d46a69ccdcf6b29f93be3d44addd80ab61

8 files changed, 90 insertions, 18 deletions

diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
index 26bcce4..18534c6 100644
--- a/core/java/android/util/ArrayMap.java
+++ b/core/java/android/util/ArrayMap.java
@@ -34,8 +34,7 @@ import java.util.Set;
  * that may contain large numbers of items.  It is generally slower than a traditional
  * HashMap, since lookups require a binary search and adds and removes require inserting
  * and deleting entries in the array.  For containers holding up to hundreds of items,
- * the performance difference is not significant, less than 50%.  For larger numbers of items
- * this data structure should be avoided.</p>
+ * the performance difference is not significant, less than 50%.</p>
  *
  * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support
  * null keys.</p>
@@ -44,7 +43,7 @@ import java.util.Set;
  * standard Java containers it will shrink its array as items are removed from it.  Currently
  * you have no control over this shrinking -- if you set a capacity and then remove an
  * item, it may reduce the capacity to better match the current size.  In the future an
- * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p>
+ * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p>
  *
  * @hide
  */
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index 2d3380e..4e1d32c 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -33,8 +33,7 @@ import java.util.Set;
  * that may contain large numbers of items.  It is generally slower than a traditional
  * HashSet, since lookups require a binary search and adds and removes require inserting
  * and deleting entries in the array.  For containers holding up to hundreds of items,
- * the performance difference is not significant, less than 50%.  For larger numbers of items
- * this data structure should be avoided.</p>
+ * the performance difference is not significant, less than 50%.</p>
  *
  * <p><b>Note:</b> unlike {@link java.util.HashSet}, this container does not support
  * null values.</p>
@@ -43,7 +42,7 @@ import java.util.Set;
  * standard Java containers it will shrink its array as items are removed from it.  Currently
  * you have no control over this shrinking -- if you set a capacity and then remove an
  * item, it may reduce the capacity to better match the current size.  In the future an
- * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p>
+ * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p>
  *
  * @hide
  */
diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java
index 660b743..77dfcf4 100644
--- a/core/java/android/util/LongSparseArray.java
+++ b/core/java/android/util/LongSparseArray.java
@@ -20,8 +20,25 @@ import com.android.internal.util.ArrayUtils;
 
 /**
  * SparseArray mapping longs to Objects.  Unlike a normal array of Objects,
- * there can be gaps in the indices.  It is intended to be more efficient
- * than using a HashMap to map Longs to Objects.
+ * there can be gaps in the indices.  It is intended to be more memory efficient
+ * than using a HashMap to map Longs to Objects, both because it avoids
+ * auto-boxing keys and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
+ *
+ * <p>To help with performance, the container includes an optimization when removing
+ * keys: instead of compacting its array immediately, it leaves the removed entry marked
+ * as deleted.  The entry can then be re-used for the same key, or compacted later in
+ * a single garbage collection step of all removed entries.  This garbage collection will
+ * need to be performed at any time the array needs to be grown or the the map size or
+ * entry values are retrieved.</p>
  */
 public class LongSparseArray<E> implements Cloneable {
     private static final Object DELETED = new Object();
diff --git a/core/java/android/util/LongSparseLongArray.java b/core/java/android/util/LongSparseLongArray.java
index 503295c..d795308 100644
--- a/core/java/android/util/LongSparseLongArray.java
+++ b/core/java/android/util/LongSparseLongArray.java
@@ -22,8 +22,18 @@ import java.util.Arrays;
 
 /**
  * Map of {@code long} to {@code long}. Unlike a normal array of longs, there
- * can be gaps in the indices. It is intended to be more efficient than using a
- * {@code HashMap}.
+ * can be gaps in the indices. It is intended to be more memory efficient than using a
+ * {@code HashMap}, both because it avoids
+ * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
  *
  * @hide
  */
diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java
index 001fc5b..0e013c3 100644
--- a/core/java/android/util/SparseArray.java
+++ b/core/java/android/util/SparseArray.java
@@ -20,8 +20,25 @@ import com.android.internal.util.ArrayUtils;
 
 /**
  * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
- * there can be gaps in the indices.  It is intended to be more efficient
- * than using a HashMap to map Integers to Objects.
+ * there can be gaps in the indices.  It is intended to be more memory efficient
+ * than using a HashMap to map Integers to Objects, both because it avoids
+ * auto-boxing keys and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
+ *
+ * <p>To help with performance, the container includes an optimization when removing
+ * keys: instead of compacting its array immediately, it leaves the removed entry marked
+ * as deleted.  The entry can then be re-used for the same key, or compacted later in
+ * a single garbage collection step of all removed entries.  This garbage collection will
+ * need to be performed at any time the array needs to be grown or the the map size or
+ * entry values are retrieved.</p>
  */
 public class SparseArray<E> implements Cloneable {
     private static final Object DELETED = new Object();
diff --git a/core/java/android/util/SparseBooleanArray.java b/core/java/android/util/SparseBooleanArray.java
index 73e3629..430755a 100644
--- a/core/java/android/util/SparseBooleanArray.java
+++ b/core/java/android/util/SparseBooleanArray.java
@@ -21,8 +21,18 @@ import com.android.internal.util.ArrayUtils;
 /**
  * SparseBooleanArrays map integers to booleans.
  * Unlike a normal array of booleans
- * there can be gaps in the indices.  It is intended to be more efficient
- * than using a HashMap to map Integers to Booleans.
+ * there can be gaps in the indices.  It is intended to be more memory efficient
+ * than using a HashMap to map Integers to Booleans, both because it avoids
+ * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
  */
 public class SparseBooleanArray implements Cloneable {
     static final boolean[] EMPTY_BOOLEANS = new boolean[0];
diff --git a/core/java/android/util/SparseIntArray.java b/core/java/android/util/SparseIntArray.java
index 122f7f5..b6fb295 100644
--- a/core/java/android/util/SparseIntArray.java
+++ b/core/java/android/util/SparseIntArray.java
@@ -20,8 +20,18 @@ import com.android.internal.util.ArrayUtils;
 
 /**
  * SparseIntArrays map integers to integers.  Unlike a normal array of integers,
- * there can be gaps in the indices.  It is intended to be more efficient
- * than using a HashMap to map Integers to Integers.
+ * there can be gaps in the indices.  It is intended to be more memory efficient
+ * than using a HashMap to map Integers to Integers, both because it avoids
+ * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
  */
 public class SparseIntArray implements Cloneable {
     private int[] mKeys;
diff --git a/core/java/android/util/SparseLongArray.java b/core/java/android/util/SparseLongArray.java
index c608996..55cb3a2 100644
--- a/core/java/android/util/SparseLongArray.java
+++ b/core/java/android/util/SparseLongArray.java
@@ -20,8 +20,18 @@ import com.android.internal.util.ArrayUtils;
 
 /**
  * SparseLongArrays map integers to longs.  Unlike a normal array of longs,
- * there can be gaps in the indices.  It is intended to be more efficient
- * than using a HashMap to map Integers to Longs.
+ * there can be gaps in the indices.  It is intended to be more memory efficient
+ * than using a HashMap to map Integers to Longs, both because it avoids
+ * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
+ * for each mapping.
+ *
+ * <p>Note that this container keeps its mappings in an array data structure,
+ * using a binary search to find keys.  The implementation is not intended to be appropriate for
+ * data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.</p>
  */
 public class SparseLongArray implements Cloneable {
     static final long[] EMPTY_LONGS = new long[0];