性能优化（一）：数据结构优化

1.数组和链表

数组：是将元素在内存中连续的存储的，因为数据是连续存储的，内存地址连续，所以查找效率高，但是在存储之前，需要申请一块连续的内存空间，并且在编译的时候就必须确定它的空间大小。在运行的时候空间的大小是无法随着需要进行增加或减少的，当数据比较大时，有可能出现越界的情况，当数据比较小的时候，有可能浪费内存空间。在改变数据个数时（增加、插入、删除）效率比较低。

链表：是动态申请内存空间的，不需要提前申请好内存大小，只需要在使用的时候根据需要动态的申请或删除内存空间，对于数据改变（增加、插入、删除）比较灵活，链表中的数据在内存中可以在任意位置，通过应用来关联。

数组&链表.png

2.ArrayList和LinkedList

（1）ArrayList是基于动态数组；LinkedList是基于双向链表。

（2）对于随机访问get和set操作，ArrayList效率高，因为LinkedList需要移动指针从前往后查。

（3）对于数据增删（add和remove）操作，LinkedList效率高，因为增删操作对ArrayList数据的下标索引造成影响，需要进行数据的移动。

3.Android性能优化之SparseArray与ArrayMap

（1） HashMap

Jdk1.7—>数组＋链表

Jdk1.8—>数组＋链表＋红黑树

内部是HashMapEntry<K,V>[] table

put—>装箱 hashCode%length=>hashCode&(length-1) 用&效率高 因为CPU是位运算(位移)

Hash表初始化是在put方法中，用的时候才初始化，节约内存。

默认HashMap多大？2的次幂 new HashMap()—>table[16]

为什么是2的次幂?—>是为了hashCode&(length-1)的运算

扩容的意义？避免冲突

什么时候扩容？阈值0.75 16(length)*0.75=12 >12扩容

扩容了需要resize transfer 而且在此过程中也需要不断的做hash运算—>内存空间造成很大消耗和浪费

避免扩容？ new HashMap(n/0.75+1)—>tableSizeFor转为最接近的2的次幂

HashMap：25%的内存浪费；在尤其扩容的时候耗性能。

所以，在一些情况下我们可以使用SparseArray代替HashMap。

（2）SparseArray

key —>int 避免自动装箱的过程

value—>Object

二分查找法

添加数据时，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好；

查找数据时，也是使用二分查找法找到元素的位置，速度快。

但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。

所以SparseArray使用场景：数据量不大（千级以内）并且key为int类型

但是key只能为int类型，所以有了ArrayMap

（3） ArrayMap

ArrayMap是一个<key,value>映射的数据结构，内部使用两个数组进行储存，一个记录key的hash值，另一个记录value的值。和SparseArray一样，采用二分查找法，数据量大的情况下性能降低。

小结：数据量不大（千级以内），key为int类型用SparseArray，key为long，用LongSparseArray，key为其它类型用ArrayMap

4.HashMap和ArrayMap

（1）存储方式不同，HashMap内部有一个HashMapEntry<K,V>[]对象；而ArrayMap是一个<key,value>映射的数据结构，内部使用两个数组进行储存，一个记录key的hash值，另一个记录value的值。

（2）添加数据时扩容的方式处理不一样：HashMap进行了new操作，重新创建对象，开销大；而ArrayMap用的是copy数据，效率高。

（3）ArrayMap提供了数组收缩功能，在clear或remove后，会重新收缩数组，节省空间。

（4）ArrayMap采用二分查找法。