当前位置: 萬仟网 > 移动技术>移动开发>Android > 荐 灵魂一问,Android中有代替HashMap的方法吗?

荐 灵魂一问,Android中有代替HashMap的方法吗?

2020年07月14日  | 萬仟网移动技术  | 我要评论

什么是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

如对本文有疑问, 点击进行留言回复!!

相关文章:

验证码:
Copyright © 2017-2020  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com