荐 灵魂一问，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。

本文地址：https://blog.csdn.net/HouXinLin_CSDN/article/details/107288071