性能优化之数据结构

数据结构"/>

性能优化之数据结构

一、ArrayList性能分析
ArrayList底层是用数组进行实现的，顺序表
假设向index=10的位置添加一个元素 “lgj”
如果arr[10] 为空的话，那么就直接赋值 a[10] = “lgj”
如果arr[10] 不为空的话，先进行元素位移，然后再向index=10的位置进行赋值a[10] = “lgj”
如下图所示：

元素位移比较损耗性能
如果每次添加和删除元素都是在末尾进行操作，那么这个也不损耗性能
查询比较快，为什么数组的访问比较快呢？
因为连续内存
int 类型的 elementData 的地址为 0xfaff323
获取 elementData[i] 的元素，可以计算出对应的地址直接获取出来0xfaff323 + i*4
二、LinkList性能分析
LinkList的底层实现是双链表，插入元素和删除元素速率更快，因为不用进行元素移位，具体实现如下图所示：

不能通过索引直接找到对应的元素，因为地址不是连续的，只能轮询所有的元素，然后找出对应的节点并返回，所以速度比较慢（应用场景，删除元素多的话就用LinkList，比如QQ的聊天记录，可以通过右滑进行删除）
三、HashMap性能分析
HashMap：1.7之前底层采用 数组 + 链表 的方式进行实现
HashMap：1.8之后底层采用 数组 + 链表 + 红黑树 的方式进行实现
分析1.7之前：
key 和 value是一一对应，一夫一妻制
存放元素的时候，可以根据Key计算出HashCode值，该值为int类型的，然后通过该值计算出 table的索引下标 index = hashCode % length ，length 为 table 的数组容量

为什么Value是一个链表呢？
求模运算过程中，有可能出现 hashCode1 和 hashCode2 所对应的 index相同，这就叫做hash碰撞，解决碰撞，采用链表法，始终把新加入Value，存放在数组中，指向之前数组所存放的数据。
当Key值相同的时候，Value值进行覆盖就行OK。
扩容：
加载因子：DEFAULT_LOAD_FACTOR = 0.75
阈值：0.75 * 16(length) = 12
整个存的Element元素，大于12的时候就会扩容，包括链表大于12和数组大于12的时候
扩容的意义就是为了提升效率，HashMap效率最低的时候就是Hash碰撞太多了如下图

扩容的时候，会重新计算HashCode值，然后重新进行存放（扩容很耗性能，避免扩容，在创建HashMap的时候指定HashMap的容量 ，假设存放 100 个数据，我们可以指定Map的容量为：(100 / 0.75 + 1)）
HashMap 的初始化是在put的时候进行的，因为避免内存浪费
默认的HashMap多大：16
HashMap：内存浪费 25% 用空间换时间，尤其在扩容的时候，浪费2倍
四、Android推出SparseArray
SparseArray 节省空间，它有一个局限性，Key为int类型的值，Value是Object类型的
SparseArray底层采用双数组进行实现

private int[] mKeys;
private Object[] mValues;

结构如下图：

插入元素的时候，采用二分查找法进行插入，假设之前的key值为：
1 45 1000 10086 999999
然后插入一个 100 的key值，先找到中间元素1000，然后做比较，最终插入到45 和 1000 之间，最后后面的元素统一向后移位
Value值就存放到对应下标：mValues[index] = value;
内存节约，也不会有冲突，速度不会慢，因为这个是二分查找法
Remove的时候，不是真正的移除该元素的位置，只是把这个元素标记成delete，就不会进行元素位移，性能更快。还有就是在添加的时候，可以直接使用这个标记的delete位置，这样速度更快。

五、Android推出ArrayMap
ArrayMap的思想是： HashMap + SparseArray 的思想
ArrayMap 是解决SparseArray key值只能存放int类型问题的