APP的优化是任重而道远的过程，必须在意每一个环节，否者当你想要优化的时候，发现到处都是坑，已经不知道填补哪里了，所以我们必须一点一滴的做起。

数据结构和算法优化

能带来什么好处呢？他能使得你程序获得数据更快，内存占用更合理。最终体现为响应快内存占用小。

我们先看常见的数据结构类型特点

数组： 一片物理上连续的大小确定的储存空间 。int[num]

顺序表：物理上连续、逻辑上连续、大小可以动态增加。ArrayList（查找快，添加删除慢）

链表：物理上不连续、逻辑上连续、可以动态增加和删除节点。LinkedList（查找慢只能轮寻，增加删除快）

物理上连续：数组或者链表在初始化的时候，会申请分配内存空间：只要存储空间足够你申请的大小就分配给你初始化（物理不连续）；必须要连续的存储空间，我才给你分配，否则失败（物理上连续）

那么有没有继承纯虚标和链表的2个有点的数据结构呢？HashMap！     

HashMap

它是由数组和链表结合组成。（HashMap：JDK1.7之前 24 之前： 数组+ 链表； HashMap：JDK1.8 之后：  数组+ 链表 + 红黑树）

下面是HashMap结构图

它是怎么操作的呢？为什么他能同时拥有顺序表和链表的优点呢？  搞清它的实现方式，我们就可以知道了， 大致可以分为以下的步骤。

①put方法，传入object和value，通过hash运算得到一个int类型的hashcode，这里假设为X（后续X为这个hashcode）。

②hashmap内部是有一个table数组+链表形成的。我们拿到这个X后，使用X/table.length(hashcode值/table[].length),得到一个小于table.length的值M，该值就是这个value应该放置的数组位置。我们准备把value放入table[M]中。

③我们把hashcode和value打包为一个node节点(为什么需要这么打包后续会提到),准备存入table[M]中。

④出入table数组的链表中有2种方式：

前插方式：不管数组table[M]节点有值与否，都把这个准备插入的node节点作为数组的根节点。可能出现2种情况：

（1）如果table[M]节点没有值，则node节点作为数组的根节点。

（2）如果table[M]节点已存在数据链表，就把这些数据链表，链到这个准备插入的node节点上，以弄得节点为根节点放入table[M中]。

后插方式：可能会出现的2种情况

  (1)   如果table[M]节点没有值，则node节点作为数组的根节点。

（2）如果table[M]节点已存在数据链表，则把node节点链到该数据链表的最后一个节点上。

经历以上4个步骤就完成了hashmap的插入操作，现在解释一下为什么要打包为node节点。

举个栗子，假如hashmap.length=16,我们准备存入ObjectA(OA)和ObjectB(OB),假设OA经过hash运算得到的hashcode是1，OB经过hash运算得到hashcode是17，OA和OB进行求模运算结果都为1，链到链表上时，我们get方法的时候怎么取到正确的值呢，因为链表上的模运算都是1.这个时候我们就需要通过hashcode来识别这个链表上的哪个值是OA的value哪个是OB的value，因为我们已经把hashcode和value打包起来了。

补充

hashmap的table数组的大小事是2的次幂（不要问为什么，源码定的，他们肯定经过大量的统计或者运算，这是科学）。table数组默认的长度是16，也就是说你new一个空的hashmap长度为16，当然也提供了一个给你设置长度的方法，但是假如你设置17，则长度会为32，这不难理解。

hash碰撞

hash碰撞就是，假如OA、OB...ON经过模运算得到的数组位置相同，那么他们都会挂在这个数组节点的链表上，极端情况想整个hashmap看起来像单链表。但这种情况这并不是我们想要的结果。我们可以通过扩容来尽可能的避免hash碰撞。

扩容：（意义，在于避免大量的hash碰撞，因为在某些极端情况下，有点像单链表）

阈值：阈值=table.length*DEFAULT_LOAD_FACTOR（扩容系数，默认为0.75，也可以自己设定，一般不做修改）

hashmap定义：当hashmap中的元素个数超过阈值大小时，我们就需要对table数组进行2倍扩容，如从16→32。

注意：扩容后hashmap会调用resize()，对hashmap内的数据重新计算所有元素的位置。。因为假如你之前17/16=1，现在17/32=17，你的位置发生变化了。

缺点：

hashMap因为有阈值的扩容机制，所以一定会有空间浪费，比如0.75的时候，一定有25%空间被浪费掉了。空间换时间。

hashmap是线程不安全的。因为可能在一个线程扩容（resize（）方法执行）的情况下,另外一个线程在get，但是拿不到之前的数据了，因为扩容。所以是线程不安全的。或者线程扩容（resize（）方法执行时，多线程进行put的时候导致的多线程数据不一致。

如何线程安全的使用HashMap?使用使用锁分段技术或者使用HashTable(Hashtable的方法是Synchronize的，而HashMap不是,其实也就是锁机制起作用)。

SparseArray（Android为了优化内存所提供的api）

特性：key为int,value为object，二分查找的思想，双数组，删除的时候节点不删除，而是把value删除，避免删除的时候数组还要移动。

SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示。

为什么是能够进行二分查找呢？从源码上看key和value分别是用int类型数组和object数组表示，所以这也是SparseArray的局限性。

 private int[] mKeys;

 private Object[] mValues;

为什么说SparseArray比HashMap更省内存，在某些条件下性能更好？

因为SparseArray有以下一个特性，首先它是2个数组，在数据查找的时候无疑会比hashmap快很多，其次在删除的时候，SparseArray并不会把数组key位置进行删除，而是把key的索引value置位DELETE标志（这样就避免了数组delete操作后的arraycopy的操作）。当我们下次进行插入的时候，若要插入的位置key的索引value为DELETE标志，则把数据覆盖给value（只是经历了set操作，并无其他操作）。否则进行add操作（包含arraycopy）。

所以经过以上的情况，我们可以看出，SparseArray相对于HashMap,会越用越快。

缺点

（1）SparseArray仅仅能存储key为int类型的数据。

（2）插入操作需要复制数组，增删效率降低 数据量巨大时，复制数组成本巨大，gc()成本也巨大。

（3）数据量巨大时，查询效率也会明显下降。

（4）线程不安全问题，类似hashmap

一般我们在满足下面两个条件我们可以使用SparseArray代替HashMap：

（1）数据量不大，最好在千级以内

（2）key必须为int类型，这中情况下的HashMap可以用SparseArray代替：

ArrayMap（Android为了优化内存所提供的api）

ArrayMap和SparseArray差不多，不同的是key类型可以是object类型。

ArrayMap的2个数组，一个数组记录key的hash值，另外一个数组记录Value值。其他存储方式和运行思想和SparseArray一致。

线程不安全:hashmap、ArrayMap、SparseArray