2019-08-16 App性能优化（一）

数据结构优化

1:   数组》----》一片物理上连续的大小确定的存储空间 int[]。

2：顺序表》--》物理上连续》逻辑上连续》大小可以动态增加 ArrayList，Arraylist是对数组的封装。

（1）add内部是arrayCopy（），如果指定位置add一个节点，指定节点后面所有节点往后移动一个，再添加一个节点。

（2）指定节点删除，把指定节点后面的所有节点往前移动一个位置

映射到面试题：

arraylist怎么删除一个节点？

从零开始一个一个for循环删除所有节点，可以吗？

从后面往前删除是可以的，用迭代器也可以。

缺陷：删除添加会多次调用arrayCopy（）方法，内存消耗比较大，熟读较慢，因为有索引，查找速度很快。

3： 链表  LinkedList

物理上不连续，添加删除非常快，物理上不连续，查找要轮询，效率比较很慢。

4： 哈希表HashMap

数组加链表的混合数据结构，使得增删改查都很快。

put（key，value）方法：

根据key 计算哈希值（key.hashCode（）），以哈希值取模运算（hash%table.length（））取值范围（0-table.length()-1）作为数组的下标，位运算使得hash值尽量均匀，哈希表会有一个默认大小，hashmap越大越好，但是空间比较浪费，因此有了加载因子是0.75，hashmap长度>长度*0.75扩容，一旦扩容就是扩容双倍，hash值全部改变，所有节点重新计算一次，速度比较慢，如果使用hashmap，首先评估粗略大小，并使hashmap大于粗略大小，减少扩容操作，也是代码优化点之一。

5：SparesAarray 

如果能用spareaarray尽量不要用hashmap,因为

spaseArray  内部是int[]类型的key：object[]的value，经过测试，同时申请十万个hashmap的节点占用内存大概是7M，占用时间是2203毫秒；申请十万个SpaseArray占用内存4.1M,占用时间是8毫秒，有兴趣可以测试一下！

数据结构分析：key--------value

                         key--------value

                         key--------value

                         key--------value

                         key--------value

                               ......

                         key--------value

key与value相对应，Sapsearray put（int  key，E value）源码，key为int类型，通过二分查找key的位置，大小排序，插入value；删除delete（int key），把节点key相对应的value这是为空，不做arrayCopy（），再次添加操作，或找到此节点，吧相对应的value赋值给null value  速度会越来越快，我们可以把安卓代码里面的HashMap替换成SparseArray，来提高效率，（以下是干货，百度上搜不到）因为SparseArray的key只能是int，我们要怎么替换呢？这个方法老师讲的时候我也半天没明白，在群里问了好几遍才知道，就是i想办法吧hashmap里面的String类型的key改成int呀，让写接口的后端配合改一下，他们不改怎么办，锤他，往死了锤，还是不改怎么办？其实我们也有办法，大家都知道，安卓有一个取string.xml id的方法，R.string.key1,这个就是int，我们吧这个value写成我们hashmap的key不就可以了吗！！是不是完美解决问题，这样就可以把所有hashmap替换成SprseArray了，效率可以大大提升。注：这两个都不是线程安全的，自己看着办。

关于HashMap和HashTable的内容请点击：https://www.jianshu.com/p/47bddb3bbf0d

以上是最长用的数据结构，可以根据自己需求，选择应该使用哪一个！