package android.util; import com.android.internal.util.ArrayUtils; /**
* SparseArrays 利用integer去管理object对象。不像一个正常的object对象数组，它能在索引数中快速的查找到所需的结果。（这
* 句话是音译，原意是能在众多索引数中“撕开一个缺口”，为什么原文这么表达？下面会慢慢说清楚。）它比HashMap去通过Integer索引
* 查找object对象时在内存上更具效率,不仅因为它避免了用来查找的自动“装箱”的keys，并且它的数据结构不依赖额外的对象去
* 各个映射中查找匹配。
*
* SparseArrays map integers to Objects. Unlike a normal array of 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.
*
* 请注意，这个容器会保持它的映射关系在一个数组的数据结构中，通过二分检索法驱查找key。（这里我们终于知道，为何这个工具类中，
* 提供的添加映射关系的操作中，key的类型必须是integer。因为二分检索法，将从中间“切开”，integer的数据类型是实现这种检索过程的保证。）
*
* 如果保存大量的数据，这种数据结构是不适合的，换言之，SparseArray这个工具类并不应该用于存储大量的数据。这种情况下，它的效率
* 通常比传统的HashMap更低，因为它的查找方法并且增加和移除操作（任意一个操作）都需要在数组中插入和删除（两个步骤才能实现）。
*
* 如果存储的数据在几百个以内，它们的性能差异并不明显，低于50%。
*
* （OK，那么光看Android官方的介绍我们就有初步结论了，大量的数据我们相对SparseArray会优先选择HashMap，如果数据在几百个这个数目，
* 那么选择它们任意一个去实现区别不大，如果数量较少，就选择SparseArray去实现。 其实如果我们理解了二分法，就很容易了SparseArray的
* 实现原理，以及SparseArray和HashMap它们之间的区别了。）
*
* <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>
*
*
* 为了提高性能，这个容器包含了一个实现最优的方法：当移除keys后为了立刻使它的数组紧密，它会“遗留”已经被移除（标记了要删除）的条目（entry） 。
* 所被标记的条目（entry）（还未被当作垃圾回收掉前）可以被相同的key复用，也会在垃圾回收机制当作所有要回收的条目的一员被回收，从而使存储的数组更紧密。
*
* （我们下面看源码就会发现remove()方法其实是调用delete()方法的。印证了上面这句话所说的这种优化方法。
* 因为这样，能在每次移除元素后一直保持数组的数据结构是紧密不松散的。）
*
* 垃圾回收的机制会在这些情况执行：数组需要扩充，或者映射表的大小被恢复，或者条目值被重新检索后恢复的时候。
*
* <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>
*
* 当调用keyAt(int)去获取某个位置的key的键的值，或者调用valueAt(int)去获取某个位置的值时，可能是通过迭代容器中的元素
* 去实现的。
*
* <p>It is possible to iterate over the items in this container using
* {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
* <code>keyAt(int)</code> with ascending values of the index will return the
* keys in ascending order, or the values corresponding to the keys in ascending
* order in the case of <code>valueAt(int)<code>.</p>
*/
public class SparseArray<E> implements Cloneable {
//...
}
####Android开发中高效的数据结构
android开发中，在java2ee或者android中常用的数据结构有Map,List,Set，但android作为移动平台，有些api（很多都是效率问题）显然不够理想，本着造更好*的精神，android团队编写了自己的api用来代替java api 、SimpleArrayMap<K,V>与ArrayMap<K,V> 实质上ArrayMap继承自SimpleArrayMap,主要是为了实现像HashMap一样的api方法，让习惯使用HashMap的开发者感觉不到差异，本质上是SimpleArrayMap+Map的再封装。 一般来说使用这2个类主要来代替HashMap，因为他们比HashMap更加高效，对内存也进行了优化。 、SparseArray<T>与SparseArrayCompat<T>和LongSparseArray<T> 这3个类中，前2个基本上是同一类，只不过第二个类有removeAt方法，第三个是Long类型的。 这3个类也是用来代替HashMap,只不过他们的键(key)的类型是整型Integer或者Long类型，在实际开发中，如月份缩写的映射，或者进行文件缓存映射，viewHolder都特别适用 、AtomicFile AtomicFile首先不是用来代替File的，而是作为File的辅助类从在， AtomicFile的作用是实现事务性原子操作，即文件读写必须完整，适合多线程中的文件读写操作。 用来实现多线程中的文件读写的安全操作 ----
#####用SparseArray代替HashMap
SparseArray是android提供的一个工具类，它可以用来替代hashmap进行对象的存储，其内部实现了一个矩阵压缩算法，很适合存储稀疏矩阵的。 PS:support包中还提供了兼容的类SparseArrayCompat,基本和SparseArray是同一个类，只不过第二个类有removeAt方法 针对源码的详细分析：[http://stormzhang.com/android/2013/08/01/android-use-sparsearray-for-performance-optimization/](http://stormzhang.com/android/2013/08/01/android-use-sparsearray-for-performance-optimization/ "http://stormzhang.com/android/2013/08/01/android-use-sparsearray-for-performance-optimization/") 一、和Hashmap的对比 既然android推荐用这个东西，自然有用它的道理。其内部实现了压缩算法，可以进行矩阵压缩，大大减少了存储空间，节约内存。此外它的查找算法是二分法，提高了查找的效率。 替换原则： > 如果用到了： HashMap<Integer, E> hashMap = new HashMap<Integer, E>(); 可以替换为：SparseArray<E> sparseArray = new SparseArray<E>(); > 如果用到了：HashMap<Integer, Boolean> hashMap = new HashMap<Integer, Boolean> 可以替换为：SparseBooleanArray array = new SparseBooleanArray(); > 如果用到了：HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer> 可以替换为：SparseIntArray array = new SparseIntArray(); 二、用法 既然是键值对那么就有增删改查，但要记得先初始化： Button btn = null; // 测试view，无意义
Button btn02 = null; // 测试view，表示新增的对象
final int KEY = ; /*
* SparseArray指的是稀疏数组(Sparse
* array)，所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用
* 。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。
*/
SparseArray<View> array = new SparseArray<View>(); 2.1 增加数据 /* 增加数据 */
//public void put(int key, E value) {}
array.put(KEY, btn);
//public void append(int key, E value){}
array.append(KEY, btn); 2.2 修改数据 /* 修改数据 */
//在put数据之前，会先查找要put的数据是否已经存在，如果存在就是修改，不存在就添加。
//public void put(int key, E value)
array.put(KEY, btn);
//public void setValueAt(int index, E value)
array.setValueAt(KEY, btn02); 2.3 查找数据 /* 查找数据 */
//public E get(int key)
array.get(KEY);
//public E get(int key, E valueIfKeyNotFound)
//其中get(int key)也只是调用了 get(int key,E valueIfKeyNotFound),最后一个从传参的变量名就能看出，传入的是找不到的时候返回的值.get(int key)当找不到的时候，默认返回null。
array.get(KEY, btn); // 如果这个key找不到value，那么就返回第二个参数。和default value一样 2.4 通过位置，查找键的值 // 查看第几个位置的键：
//public int keyAt(int index)
array.keyAt(); // 如果找不到就返回-1 2.5 通过位置，查找值 // 查看第几个位置的值：
//public E valueAt(int index)
array.valueAt();
// 查看值所在位置，没有的话返回-1：
//public int indexOfValue(E value)
array.indexOfValue(btn); 三、测试代码 package com.kale.pictest; import android.app.Activity;
import android.os.Bundle;
import android.util.Log;
import android.util.SparseArray;
import android.util.SparseBooleanArray;
import android.view.View;
import android.widget.Button; /**
* @author:
* @description :
* @web : http://stormzhang.com/android/2013/08/01/android-use-sparsearray-for-performance-optimization/
* @date :2015年1月19日
*/
public class MainActivity extends Activity { @Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main); int maxMemory = (int) (Runtime.getRuntime().maxMemory() / );
Log.d("TAG", "Max memory is " + maxMemory + "KB"); Button btn = null; // 测试view，无意义
Button btn02 = null; // 测试view，表示新增的对象
final int KEY = ; /*
* SparseArray指的是稀疏数组(Sparse
* array)，所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用
* 。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。
*/
SparseArray<View> array = new SparseArray<View>(); /* 增加数据 */
//public void put(int key, E value) {}
array.put(KEY, btn);
//public void append(int key, E value){}
array.append(KEY, btn); /* 修改数据 */
//在put数据之前，会先查找要put的数据是否已经存在，如果存在就是修改，不存在就添加。
//public void put(int key, E value)
array.put(KEY, btn);
//public void setValueAt(int index, E value)
array.setValueAt(KEY, btn02); /* 查找数据 */
//public E get(int key)
array.get(KEY);
//public E get(int key, E valueIfKeyNotFound)
//其中get(int key)也只是调用了 get(int key,E valueIfKeyNotFound),最后一个从传参的变量名就能看出，传入的是找不到的时候返回的值.get(int key)当找不到的时候，默认返回null。
array.get(KEY, btn); // 如果这个key找不到value，那么就返回第二个参数。和default value一样 // 查看第几个位置的键：
//public int keyAt(int index)
array.keyAt(); // 如果找不到就返回-1 // 查看第几个位置的值：
//public E valueAt(int index)
array.valueAt();
// 查看值所在位置，没有的话返回-1：
//public int indexOfValue(E value)
array.indexOfValue(btn); SparseBooleanArray d;
}
} 测试代码四： public class FragmentPagerItemAdapter extends FragmentPagerAdapter { private final FragmentPagerItems mPages;
private final SparseArrayCompat<WeakReference<Fragment>> mHolder; public FragmentPagerItemAdapter(FragmentManager fm, FragmentPagerItems pages) {
super(fm);
mPages = pages;
mHolder = new SparseArrayCompat<>(pages.size());
} @Override
public int getCount() {
return mPages.size();
} @Override
public Fragment getItem(int position) {
return getPagerItem(position).instantiate(mPages.getContext(), position);
} @Override
public Object instantiateItem(ViewGroup container, int position) {
Object item = super.instantiateItem(container, position);
if (item instanceof Fragment) {
mHolder.put(position, new WeakReference<Fragment>((Fragment) item));
}
return item;
} @Override
public void destroyItem(ViewGroup container, int position, Object object) {
mHolder.remove(position);
super.destroyItem(container, position, object);
} @Override
public CharSequence getPageTitle(int position) {
return getPagerItem(position).getTitle();
} @Override
public float getPageWidth(int position) {
return super.getPageWidth(position);
} public Fragment getPage(int position) {
final WeakReference<Fragment> weakRefItem = mHolder.get(position);
return (weakRefItem != null) ? weakRefItem.get() : null;
} protected FragmentPagerItem getPagerItem(int position) {
return mPages.get(position);
} }
1，SparseArray的原理是二分检索法，也因此key的类型都是整型。
2，（HashMap和SparseArray比较）当存储大量数据（起码上千个）的时候，优先选择HashMap。如果只有几百个，用哪个区别不大。如果数量不多，优先选择SparseArray。
3，SparseArray有自己的垃圾回收机制。