Android - 性能优化之数据结构

什么是性能优化

一款app除了要有令人惊叹的功能和令人发指交互之外，在性能上也应该追求丝滑的享受，这样才能提供用户体验

优化目的	性能指标	优化方法
更快	流畅性	启动速度，页面显示速度（显示和切换），响应速度
更稳定	稳定性	避免出现应用崩溃（Crash），避免出现应用无响应（ANR）
更省	资源节省性	内存大小，安装包大小，耗电量，网络流量

线性数据结构

• 数组

  一片连续的存储空间. eg：int[i]

• 顺序表 （ArrayList）

  • 物理上连续
  • 逻辑上连续
  • 大小可以动态增加

• 链表（LinkedList）

  • 物理上不连续

  • 逻辑上连续

  • 可以动态增加和删除节点

	顺序表	链表
优点	物理上连续，所以寻找快	空间不连续，逻辑上连续，删除，增加元素快
缺点	删除和增加元素要大量移动数据，损耗性能	物理上不连续，查找要轮训，查找慢

Hash 表

结合了数组和链表的优点，增删改查都很快。

HashMap

hashMap的特点

• Collection 是集合，有数组（ArrayList）查找快增删慢，有链表（LinkList）增删快查找慢，Map 就是数组与链表的结合体，结合了两的优点。

• HashMap 的数据关系是 key 到 value 的映射关系，key 是唯一的，value是可以重复的。

• HashMap 的 Hash , 是因为 key 是需要计算哈希值，这种数组就是散列表。

• HashMap 可以理解为 key计算后的位置用 数组 保存，数组里面的内容放着 链表，链表的节点是 key-value 一个个保存起来，查找的时候，快速找到数组中对应的位置，然后遍历链表。

• HashMap 非线程安全，可以用 HashTable。

• HashMap 数据是无序的，需要有序的使用 LinkedHashMap。

操作	原理
增加	先计算Key的hash值（装箱拆箱），根据hash值找到数组位置，再往链表中添加元素
查找	先计算Key的hash值（装箱拆箱），根据hash值找到数组位置，再遍历链表
删除	先计算Key的hash值（装箱拆箱），根据hash值找到数组位置，再从链表中删除节点

SparseArray

操作	原理
增加	根据Key值进行二分查找，找到可以添加元素的位置，然后插入数据，并移动其他数据
查找	根据Key值进行二分查找，找到数组下标，然后取出对应value值
删除	根据Key值进行二分查找，找到数组下标，然后将mValues数组的对应下标处的值置为DELETED

HashMap 和 SparseArray性能对比