android开发分享荐 灵魂一问，Android中有代替HashMap的方法吗？

什么是HashMap？

简单的说就是用来存放映射关系数据的一个集合工具，就是一个Key，对应一个Value，通过指定Key，可以查找对应Value。他在JDK1.7和JDK1.8或以后的实现方法不同，1.7是数组+链表，1.8则是数组+链表+红黑树结构，（当链表长度大于8，转为红黑树）。当然还有很多不同的地方。

为什么要代替HashMap？

就像我们生活中一样，一个东西被替代，无非就是新的更好而已，而且具有旧的所有功能。那我们为什么有理由不去使用他呢？

在Android中可以代替HashMap的类是SparseArray，他比HashMap更节省内存，因为它避免了自动装箱操作，也就是int转为Integer类型，哦忘了说了，SparseArray的Key只能为int，也就是当我们只有在key是int的时候才可以使用SparseArray，其实还有SparseIntArray、SparseLongArray、SparseBooleanArray类。那我的key是其他的类型时候呢？当然还有其他办法，那就是ArrayMap。

还有就是SparseArray并不像HashMap采用一维数组+单链表结构，而是采用两个一维数组，一个是存储key(int类型),一个是存在value。

private int[] mKeys;  private Object[] mValues; 

怎么使用SparseArray？

使用他其实和HashMap类似，实例化、put…，SparseArray如果不指定容量，默认是10大小。

 public SparseArray() {      this(10);  } 

插入

SparseArray<Book> bookSparseArray = new SparseArray<>(); bookSparseArray.put(1,new Book("武林秘籍")); bookSparseArray.put(4,new Book("葵花宝典")); bookSparseArray.put(2,new Book("十八掌")); Log.i("TAG", "onCreate: "+bookSparseArray.get(2).getName()); 

输出：

 I/TAG: onCreate: 十八掌 

但是SparseArray还提供了一个append方法，也可以用来添加，

bookSparseArray.put(1,new Book("武林秘籍")); bookSparseArray.put(4,new Book("葵花宝典")); bookSparseArray.put(2,new Book("十八掌")); bookSparseArray.append(3,new Book("九阳真经")); Log.i("TAG", "onCreate: "+bookSparseArray.get(3).getName()); 

从源码第一句可以看出，如果数量不为0，并且新增的key小于等于mKeys[mSize – 1]，就调用put方法，也就是如果新增的key大于现有的所有键时进行优化。

public void append(int key, E value) {     if (mSize != 0 && key <= mKeys[mSize - 1]) {         put(key, value);         return;     }     if (mGarbage && mSize >= mKeys.length) {         gc();     }     mKeys = GrowingArrayUtils.append(mKeys, mSize, key);     mValues = GrowingArrayUtils.append(mValues, mSize, value);     mSize++; } 

和HashMap不同的是，SparseArray提供了valueAt、keyAt用来查找指定索引位置的值、指定索引位置的key是多少。

 SparseArray<Book> bookSparseArray = new SparseArray<>();  bookSparseArray.put(1,new Book("武林秘籍"));  bookSparseArray.put(4,new Book("葵花宝典"));  bookSparseArray.put(2,new Book("十八掌"));  bookSparseArray.append(3,new Book("九阳真经"));  Log.i("TAG", "onCreate: "+bookSparseArray.valueAt(2).getName());  Log.i("TAG", "onCreate: "+bookSparseArray.keyAt(3)); 

输出：

I/TAG: onCreate: 九阳真经 I/TAG: onCreate: 4 

输出的结果是不是意想不到？其实在put的时候做了一些处理，SparseArray会根据Key自动排序（生序）。

删除

删除为我们提供了removeAt、remove、delete，分为是删除指定索引位置的数据，删除指定key、删除指定key。remove和delete是等价的，都一样。

 public void remove(int key) {      delete(key);  } 

还有一个是移除指定区间的removeAtRange。

 SparseArray<Book> bookSparseArray = new SparseArray<>();  bookSparseArray.put(1,new Book("武林秘籍"));  bookSparseArray.put(4,new Book("葵花宝典"));  bookSparseArray.put(2,new Book("十八掌"));  bookSparseArray.append(3,new Book("九阳真经"));  Log.i("TAG", "onCreate: "+bookSparseArray.valueAt(2).getName());  bookSparseArray.remove(2);  Log.i("TAG", "onCreate: "+bookSparseArray.valueAt(2).getName());  bookSparseArray.removeAtRange(0,bookSparseArray.size());  Log.i("TAG", "onCreate: "+bookSparseArray.size()); 

输出

I/TAG: onCreate: 九阳真经 I/TAG: onCreate: 葵花宝典 I/TAG: onCreate: 0 

获取

我们除了根据指定key获取对应值，get方法还有一个重载方法，这个方法提供了当key不存在的时候返回的默认值。

 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];      }  } 

 SparseArray<Book> bookSparseArray = new SparseArray<>();  bookSparseArray.put(1,new Book("武林秘籍"));  bookSparseArray.put(4,new Book("葵花宝典"));  bookSparseArray.put(2,new Book("十八掌"));  bookSparseArray.append(3,new Book("九阳真经"));  Book valueBook = bookSparseArray.get(5, new Book("空手套白狼"));  Log.i("TAG", "onCreate: "+valueBook.getName()); 

设置指定索引位置的值

SparseArray<Book> bookSparseArray = new SparseArray<>(); bookSparseArray.put(1,new Book("武林秘籍")); bookSparseArray.put(4,new Book("葵花宝典")); bookSparseArray.put(2,new Book("十八掌")); bookSparseArray.append(3,new Book("九阳真经")); Log.i("TAG", "onCreate: "+bookSparseArray.valueAt(2).getName()); bookSparseArray.setValueAt(2,new Book("听风逝夜")); Log.i("TAG", "onCreate: "+bookSparseArray.valueAt(2).getName()); 

输出

 I/TAG: onCreate: 九阳真经  I/TAG: onCreate: 听风逝夜 

二分法

在SparseArray中用到了二分法，用来查找key的索引位置。二分法查找针对的是一个有序的数据集合,每次通过与区间的中间元素对比，将待查找的区间缩小为之前的一半,直到找到要查找的元素，或者区间被缩小为0。

下面是ContainerHelpers类下的binarySearch方法实现，当然这个类我们访问不到。但是我们可以使用Collections.binarySearch或者Arrays.binarySearch。

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;   } 

 int[] data ={1,3,4,6,7,9};  Log.i("TAG", "2的索引位置: "+binarySearch(data,data.length,2));  Log.i("TAG", "1的索引位置: "+binarySearch(data,data.length,1));  Log.i("TAG", "9的索引位置: "+binarySearch(data,data.length,9)); 

输出如下，如果找不到，是返回负数的，这个负数也是具有意义的，称之为插入点，插入点值就是第一个比key大的元素在数组中的位置索引，而且这个位置索引从1开始。

 I/TAG: 2的索引位置: -2  I/TAG: 1的索引位置: 0  I/TAG: 9的索引位置: 5 

对于上面数据，如果我们查找10，那么会返回-7。或者大于9的数都会返回-7。