前言
性能优化是一个app中不可或缺并需不断重复的工作，一个app的性能体验在很大程度上也决定了是否能留住用户，而对于性能优化这一块，有很多的知识点需要掌握，优化的目的总的来说分为三块，分别是：更快（流畅性）、更稳定（稳定性）、更省（资源节省性）。
下面将结合ArrayList、LinkedList、HashMap、SparseArray的源码来跟大家讲解一下关于数据结构方面的优化，数据结构的优化主要是优化速度以及内存空间的。
ArrayList
概要
相信有大部分人在平时写代码时，只要是需要用到集合的地方都会第一时间敲上List<Object> list = new ArrayList<>()，但是也需要注意使用场景，毕竟在某些场景下使用它会耗性能，下面先来分析一下ArrayList的工作原理。
工作原理
ArrayList的底层是使用数组实现的，而这也意味着它也有跟数组类似的缺点，比如它的随机访问效率高，但是增删的效率比较低（尾插除外）。
以下这是尾插add(E e)的代码：
public boolean add(E e) {
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
可以看到，尾插的话只需要把size加1，并往数组的最后一位添加数据就好了。
下面的是往数组中间的特定位置插入数据add(int index, E element)的代码：
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
可以看到，其中的添加数据的代码最重要的是System.arraycopy()这一句，它是通过把原本的index这个位置以及后面的所有位置都往后挪一位，然后再在空出来的那个位置插入数据的，这样添加数据效率并不高。
在添加数组的过程中，我们也要注意一下ensureCapacityInternal()这个方法，下面来看一下这个方法的作用：
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
// 如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需要空间比elementData的内存空间长度要大，则需要扩容
if (minCapacity - elementData.length > 0)
// 扩容代码
grow(minCapacity);
}
在创建ArrayList的时候，若调用的是它的无参构造函数：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
则首先会创建一个空数组，并在添加数据的时候判断是否为空数组并把最小容量赋值为一个默认的数组长度，即DEFAULT_CAPACITY = 10。然后会判断ArrayList的长度是否足够添加新的数据，如果不够则进行扩容。
下面是扩容的关键方法：
private void grow(int minCapacity) {
// 获取到ArrayList中elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容至原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再判断一下新数组的容量够不够，够了就直接使用这个长度创建新数组，
// 不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 若预设值大于默认的最大值检查是否溢出，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
// 并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
可以看到，当原来的数组长度不够时，会创建一个新的内存空间，并把原本的数据复制到新的内存空间。
分析完了添加数据的代码，下面来看一下删除数据的代码：
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
删除数据的操作，跟添加数据的方式相似，首先是判断一下是否有数组越界的可能，然后再通过System.arraycopy()把index后面的所有位置都往前挪一位，最后再把最后一位元素设为null。
接下来来看一下get部分的代码，由于根据索引获取数组的某个数组大家都比较熟悉了，这里就不过多解释，只把相关代码贴上来：
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
优缺点
优点：物理空间连续并且是顺序存储的，随机访问很快，可动态增加数组大小，并且实现了序列化。
缺点：新增元素慢且耗费资源，删除非尾部的元素慢，非线程安全。
使用场景
当只是简单的展示数据，不需要频繁进行增加或删除的操作时可以使用，比如只需要使用RecyclerView展示数据。
常见面试题
如何遍历ArrayList中的元素？
如果只是需要遍历数组里面的元素的话，最简单并且效率最高的是for循环。
如何遍历并删除ArrayList中的所有元素？
当涉及到删除操作的时候应该使用迭代器Iterator，若使用for循环或者for-each的话容易造成数组越界，原理可参考ArrayList的remove方法，若想使用for循环，可从尾部开始删起。有兴趣的可以自己去了解一下，这里不详细说明。
LinkedList
概述
LinkedList跟ArrayList都实现了List接口，但是不同于ArrayList的是：LinkedList是基于链表实现的，熟悉链表的人都知道，它在物理上不是连续的空间，但在逻辑上是有先后顺序，所以它的增删速度快，但是查询速度慢。
工作原理
下面来分析一下LinkedList的add以及remove原理。
首先来看一下LinkedList的Node节点：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
由Node的定义可以看出LinkedList是双向链表。
它可以在头部添加节点也可以在尾部添加节点，以下是添加到尾部的实现：
// 添加到尾部
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
// 指向链表尾部
final Node<E> l = last;
// 创建一个新节点
final Node<E> newNode = new Node<>(l, e, null);
// 将链表尾部指向新节点
last = newNode;
// 如果链表为空，那么该节点既是头节点也是尾节点
if (l == null)
first = newNode;
// 链表不为空，那么将该结点作为原链表尾部的后继节点
else
l.next = newNode;
size++;
modCount++;
}
从上面代码可以看到，linkLast()方法中就是一个链表尾部添加一个双端节点的操作，但是需要注意对链表为空时头节点的处理。添加到头部的操作跟添加到尾部的操作是一样的，这里不多做说明，感兴趣的可以自己去看一下源码。
add(int index, E element)用于在指定位置添加元素，实现如下：
public void add(int index, E element) {
// 检查索引是否越界
checkPositionIndex(index);
// 添加在链表尾部
if (index == size)
linkLast(element);
// 添加在链表中间
else
linkBefore(element, node(index));
}
从上面代码可以看到，主要分为3步：
1. 检查index的范围，否则抛出异常
2. 如果插入位置是链表尾部，那么调用linkLast方法
3. 如果插入位置是链表中间，那么调用linkBefore方法
第二步在上面已经分析过了，现在来分析一下第三步，在分析linkBefore()之前，我们先来看一下node(int index)方法的作用：
// 该方法返回指定位置的节点
Node<E> node(int index) {
// 如果索引位置靠链表前半部分，从头开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 否则，从尾开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
从上面可以看到，node(int index)方法将根据index是靠近头部还是尾部选择不同的遍历方向，这是双向链表的一个好处，可以减少遍历时间。
分析完了node(int index)，现在来看一下linkBefore(E e, Node<E> succ)：
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
从代码中可以看到linkBefore主要分三步：
1. 创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred
2. 将succ的前驱指针指向newNode
3. 根据pred是否为null，进行不同操作：
- 如果pred为null，说明该节点插入在头节点之前，要重置first头节点
- 如果pred不为null，那么直接将pred的后继指针指向newNode即可
LinkedList由于实现了List和Deque接口，所以有多种添加方法，分别如下：
将数据插入到链表头部
- void addFirst(E e)
- boolean offerFirst(E e)
将数据插入到链表尾部
- void addLast(E e)
- boolean add(E e):
- boolean offerLast(E e)
将数据插入到指定索引位置
- boolean add(int index,E e)
其中，添加到头部以及尾部的方法内部都是通过linkLast以及linkFirst实现的，所以这里不多做说明。
add部分分析完了，接下来分析get(int index)部分
public E get(int index) {
// 检查index是否越界
checkElementIndex(index);
return node(index).item;
}
上面的代码中，node(index)我们在上面已经分析过了，不理解的小伙伴可以拉上去看一看。
接下来我们来看一下remove部分的代码，remove操作分为按照位置删除和按照对象删除，下面我们先来分析一下按照对象删除的代码：
// 删除某个对象
public boolean remove(Object o) {
// 如果删除对象为null
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
// 一旦匹配，调用unlink()方法删除对象
if (x.item == null) {
unlink(x);
return true;
}
}
} else { // 如果删除对象不为null
for (Node<E> x = first; x != null; x = x.next) {
// 判断x.item是否为要删除的对象
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 执行删除操作
E unlink(Node<E> x) {
final E element = x.item;
// 得到后继节点
final Node<E> next = x.next;
// 得到前驱节点
final Node<E> prev = x.prev;
// 删除前驱指针
if (prev == null) {
first = next;
} else {
prev.next = next; // 将前驱节点的后继节点指向后继节点
x.prev = null;
}
// 删除后继指针
if (next == null) {
last = prev;
} else {
next.prev = prev; // 将后继节点的前驱节点只想前驱节点
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
根据上面的代码，我们可以分为三步：
1. 得到待删除节点的前驱节点和后继节点
2. 删除前驱节点
3. 删除后继节点
我们再来看一下删除某个位置的对象是怎么实现的：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
分析一下上面代码的两步操作：
1. 检查index是否越界
2. 调用unlink(node(index))进行删除
unlink()以及node(index)这两个方法已经在上面分析过了，通过unlink删除遍历得到的对象，这里不再多说明。
关于删除头节点以及尾节点的方法还有很多，分别如下：
删除头节点位置的对象
- E removeFirst()
- E pollFirst()
删除尾节点位置的对象
- E removeLast()
- E pollLast()
由于它们的内部实现都是一样的，所以这里不具体分析这些方法。
优缺点
优点：基于双向链表实现，在插入和删除时只需要添加或删除前后对象的引用，效率较快
缺点：在内存中存储空间不连续，只能通过遍历查询，效率相对较低，非线程安全
使用场景
当需要频繁地进行增删操作时，或涉及到排序、需要动态的去修改元素的位置时，可使用LinkedList。
LinkedList总结
在首部插入时，LinkedList更快；在中间和尾部插入，ArrayList更快；所以建议，数据量不大的集合，主要进行插入、删除操作，建议使用LinkedList；数据量大的集合，使用ArrayList，不仅查询速度快，并且插入和删除效率也相对较高。并且当数据量大的时候，ArrayList每次扩容都能得到很大的新空间（比如长度为1000，扩容后为1500），解决了前期频繁扩容的劣势。
常见面试题
ArrayList跟LinkedList的区别？
关于这点在上面的优缺点分析中已经说明了，可从底层实现、效率、优缺点来进行回答。
LinkedList一定比ArrayList的插入和删除操作效率高吗？
以下的分析适用于插入操作和删除操作：
（1）在首部插入数据，LinkedList较快，因为LinkedList遍历插入位置花费时间很小，而ArrayList需要将原数组所有元素进行一次System.arraycopy；
（2）插入位置越往中间，LinkedList效率越低，因为它遍历获取插入位置是从两头往中间搜，index越往中间遍历越久，因此ArrayList的插入效率可能会比LinkedList高；
（3）插入位置越往后，ArrayList效率越高，因为数组需要复制后移的数据少了，那么System.arraycopy就快了。
HashMap
概述
HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组跟链表的混合结构。
工作原理
HashMap是近年来较为常见的面试点，我们先来分析一下它的工作原理，后面再解答一些相关的面试点。
我们首先来看一下HashMap的底层结构
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value键值对，它持有一个指向下一个元素的引用，这就构成了链表。
下面来看一下put(key, value)存储的原理：
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果发现已有该键值，则存储新的值，并返回原始值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
在这里我们要注意看hash(key.hashCode())方法，这个方法是通过我们传入的key，然后得到key的hashCode并调用hash(int h)去重新计算一次散列值。注：在JDK1.8时这个方法的计算方式已改变。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
然后把计算得到的hash值通过indexFor(hash, table.length)去对数组的长度进行取模运算，得到的值即为这个元素在数组中的下标值。如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
static int indexFor(int h, int length) {
return h & (length-1);
}
由于HashMap的key是唯一的，所以根据上面put方法的源码可以看出，当程序试图将一个key-value键值对放入HashMap中时，程序首先根据该key的hashCode()返回值决定该Entry的存储位置：如果两个Entry的hash值相同，那它们的存储位置相同。如果这两个Entry的key通过equals比较返回true，新添加Entry的value将覆盖集合中原有Entry的value，但key不会覆盖。如果这两个Entry的key通过equals比较返回false，新添加的Entry将与集合中原有的Entry形成Entry链，而且新添加的Entry位于Entry链的头部。
分析完了HashMap的put原理，下面来分析一下get(Object key)原理：
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
在HashMap中get一个元素时，首先也是通过hash(key.hashCode())去得到该元素位于数组的哪个位置，然后通过遍历该位置下的链表，通过key的equals方法在对应位置的链表中找到需要的元素并返回。
当HashMap中的元素越来越多时，造成hash碰撞的几率也会越来越大，这样会导致在查询某个元素时遍历链表的时间比较长，效率比较低，所以这时候HashMap的数组会进行扩容。那么hashmap什么时候进行扩容呢？
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 数组默认容量
我们先来了解一个概念：负载因子(loadFactor)，也就是HashMap能够承受住自身负载（大小或容量）的因子，loadFactor的默认值为0.75，在默认情况下，HashMap的数组容量是16，当HashMap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为2 * 16=32，即扩大一倍。然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
HashMap总结
HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。HashMap底层采用一个 Entry[]数组来保存所有的key-value，当需要存储一个Entry对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
常见面试题
当两个键的hashcode相同，如何获取它们的值？
通过hashcode可以获取到它们位于数组中的具体位置，然后通过遍历链表，对每个key进行hash计算，并对key进行equals比较后，返回对应的value值。
当两个对象的hashcode相同会怎么样？
两个对象的hashcode相同，说明它们位于数组的同一位置上，然后HashMap会遍历链表中的每个元素，通过key的equals方法来判断是否为同一个key，如果是同一个key，则新的value会覆盖旧的value，并且返回旧的value。如果不是同一个key，则存储在该位置上的链表的链头。
如果HashMap的大小超过了负载因子的容量，会怎么样？
负载因子为0.75，当超过负载因子的容量后，会对数组进行扩容，即创建一个是原来HashMap数组大小的两倍的新数组，并重新计算原本的元素在新数组中的位置。
HashMap的扩容会造成什么问题？
在多线程的情况下，可能产生条件竞争。当重新调整HashMap大小的时候，确实存在条件竞争，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的数组位置的时候，HashMap并不会将元素放在LinkedList的尾部，而是放在头部，这是为了避免尾部遍历。所以在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表，从而导致死循环。（在JDK8中不会导致死循环问题）
Java8中对HashMap的改进
（1）对key求hash值的方法改变了，变为：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
（2）引入了红黑树，这一点在hash不均匀并且元素个数很多的情况时，对hashmap的性能提升非常大。在JDK7中HashMap采用的是位桶+链表的方式，而JDK8中采用的是位桶+链表/红黑树的方式，当某个位桶的链表的长度超过8的时候，这个链表就将转换成红黑树。
因为引入了树，所以其他操作也更复杂了，比如put方法以前只要通过hash计算下标位置，判断该位置有没有元素，如果有就往下遍历，如果存在相同的key就替换value，如果不存在就添加。但是到了8以后，就要判断是链表还是树，如果是链表，插入后还要判断要不要转化成树。
不过这些操作都是常量级别的，复杂度还是O(1)的，但是对整体性能提升非常大。
（3）还有一项比较大的改变就是扩容机制。JDK8以前的扩容机制如下所示：
void addEntry(int hash, K key, V value, int bucketIndex) {
//1、判断当前个数是否大于等于阈值
//2、当前存放是否发生哈希碰撞
//如果上面两个条件否发生，那么就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容，并且把原来数组中的元素重新放到新数组中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
由上面的代码可以看出，在JDK8以前，Hashmap的扩容需要满足两个条件，一是当前数据存储的数量（即size）大小必须大于等于阈值；二是当前加入的数据是否发生了hash冲突。
而在JDK8的时候，扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于阈值（若已有元素等于阈值，下一个存放后必然触发扩容机制）
为什么String、Integer这样的Wrapper类适合作为键
因为在Wrapper类中已经重写了equals()和hashCode()方法，它们是被final修饰的，为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。
SparseArray
SparseArray的功能类似于HashMap，其内部是由两个数组实现的，不同于HashMap的是，SparseArray的key只能是int类型，而HashMap的key是Object类型的。
private int[] mKeys;
private Object[] mValues;
由上面的代码可以看出，SparseArray分别用了数组 int[] 和 object[] 来存储key以及value。
下面我们先来看一下它的构造函数：
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
由构造函数中我们可以看到，当SparseArray使用无参数构造函数进行初始化的时候，默认的数组大小是10。我们也可以使用有参构造函数来对SparseArray进行初始化来设置它的数组大小。
下面我们来分析一下它的put(int key, E value)方法：
public void put(int key, E value) {
// 对key进行二分查找
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
// 如果返回的i是正数，则说明这个key已经存在，直接覆盖value即可
if (i >= 0) {
mValues[i] = value;
} else {
// 若返回的i是负数，说明 key不存在.
// 先对返回的i取反，得到应该插入的位置i
i = ~i;
// 如果i没有越界，且对应位置是已删除的标记，则复用这个空间
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
// 如果需要GC，且需要扩容
if (mGarbage && mSize >= mKeys.length) {
// 先触发GC
gc();
// gc后，下标i可能发生变化，所以再次用二分查找找到应该插入的位置i
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
// 插入key（可能需要扩容）
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
// 插入value（可能需要扩容）
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
mSize++;
}
}
这个方法的注释我在上面已经写得很详细了，在一开始我们就对key进行了二分查找，若查找到该key已经存在，则覆盖它的value，若没有查找到，则判断是否需要gc或者扩容，然后再进行插入操作。这也说明SparseArray与HashMap都是要求key是唯一的。
在上面的put()方法中调用了很多外部的方法以及内部的方法，首先来看一下ContainerHelpers#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; // value found
}
}
// 若没找到，则lo是value应该插入的位置，是一个正数。对这个正数取反，返回负数
return ~lo;
}
那么在插入之前，我们为什么要判断是否需要gc呢？由于之前进行过 delete()、remoeAt()以及 removeReturnOld()中的某一个方法，那就可能要进行gc()操作。当然，这里的gc不是指的内存的gc。
// 垃圾回收函数,压缩数组
private void gc() {
// 保存GC前的集合大小
int n = mSize;
// 既是下标index，又是GC后的集合大小
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
// 遍历values集合，以下算法意义为从values数组中，删除所有值为DELETED的元素
for (int i = 0; i < n; i++) {
Object val = values[i];
// 如果当前value没有被标记为已删除
if (val != DELETED) {
// 压缩keys、values数组
if (i != o) {
keys[o] = keys[i];
values[o] = val;
// 并将当前元素置空，防止内存泄漏
values[i] = null;
}
o++;
}
}
// 修改标识位，改为不需要GC
mGarbage = false;
// gc后的元素个数变为压缩后的个数o
mSize = o;
}
由上面的代码不难看出，gc()的作用是把被标记为DELETED的value剔除掉，把没有被标记为DELETED的value在原数组中重新构建为一个新的数组。gc()完之后，下标 i 可能会发生变化，因此需要重新进行二分查找，以得到一个新的下标 i。
最后就是通过 GrowingArrayUtils.insert() 来进行 key 和 value 的插入。这个 insert() 根据数组类型重载了多个，这里只分析 int[] 类型的即可。
public static int[] insert(int[] array, int currentSize, int index, int element) {
// 确认当前集合长度小于等于 array数组长度
assert currentSize <= array.length;
// 不需要扩容
if (currentSize + 1 <= array.length) {
// 将array数组内从 index 移到 index + 1，共移了 currentSize - index 个，即从index开始后移一位，那么就留出 index 的位置来插入新的值。
System.arraycopy(array, index, array, index + 1, currentSize - index);
// 在index处插入新的值
array[index] = element;
return array;
}
// 需要扩容，构建新的数组，新的数组大小由growSize() 计算得到
int[] newArray = new int[growSize(currentSize)];
// 这里再分 3 段赋值。首先将原数组中 index 之前的数据复制到新数组中
System.arraycopy(array, 0, newArray, 0, index);
// 然后在index处插入新的值
newArray[index] = element;
// 最后将原数组中 index 及其之后的数据赋值到新数组中
System.arraycopy(array, index, newArray, index + 1, array.length - index);
return newArray;
}
这里再看看 growSize() 是如何进行扩容 size 的计算的：
public static int growSize(int currentSize) {
//如果当前size 小于等于4，则返回8， 否则返回当前size的两倍
return currentSize <= 4 ? 8 : currentSize * 2;
}
我们已经分析完了put()方法，现在来看一下get()方法：
public E get(int key) {
return get(key, null);
}
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];
}
}
get()方法相当简单，就是通过 key 来返回对应的 value，这里同样运用到了上面说的二分查找，若查找到了，则会通过下标直接从mValues[]中返回。
接下来再来看一下delete()方法：
public void delete(int key) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
if (mValues[i] != DELETED) {
mValues[i] = DELETED;
mGarbage = true; // 把是否需要gc的标志位设为true
}
}
}
delete() 也非常简单，通过二分查找算法定位到下标，然后将对应的 value 标记为 DELETE，并且标记需要进行 gc 了。这里需要注意的是被标记为 DELETE 的 value 不会在 gc 中被移除掉，而只会被覆盖掉，从而提高了插入的效率。
SparseArray总结
- key值不能重复，否则会发生覆盖，并且key是以升序在数组中进行排列的
- SparseArray的删除操作并不是真的删除，而只是标记为 DELETE，以便下次能够直接复用
常见面试题
HashMap与SparseArray的区别？
（1）HashMap的key值可以是object类型的，而SparseArray的key值只能是int型的；
（2）SparseArray扩容时只需要数组拷贝工作(System.arraycopy)，而HashMap需要重建哈希表并且这个过程十分消耗性能；
（3）SparseArray基于二分查找算法，将 key 以升序的方式排列在一起，从而提高内存的利用率以及访问的效率。相比较 HashMap 而言，这是典型的以时间换空间的策略（在数据量大的情况下）；
（4）在数据量不大的情况下，SparseArray相比于HashMap，既省空间又省时间，申请相同长度的存储结构，SparseArray比HashMap占用的内存更小。
总结
关于性能优化，我们应该从平时最常用的数据结构入手，要善于选择在适合的场景使用合适的数据结构来进行编程，这样可以有效的节省时间跟空间，有利用速度以及内存空间的优化。
网友评论