数据结构优化

ArrayList性能优化

ArrayList由数组构成，在数据结构中叫做“顺序表”或者“线性表”。ArrayList的性能消耗主要在扩容和元素位移上。

增删操作带来的性能损耗

性能优化的点，就在add(T t)方法。

add方法在调用时，使用System.arrayCopy()方法，其内部是遍历数组，更改下标，达到后移的效果，这种位移十分消耗性能。

所以ArrayList的add和remove方法非常消耗性能。

解决办法一：

尽量不要调用add(int index,T t)从中间插入，而是从最后add，那么就只有数组扩容，不需要位移。

解决方案二：

用LinkedList替换提高增删效率。在查询之前，转换为ArrayList。

解决方案三：

用Hashmap来替换，hashmap的特点就是增删快，查询也快。

初始化时提高效率

因为ArrayList每次扩容固定10个，所以在创建ArrayList时可以设置默认长度为10，以提高第一add操作时的性能消耗。

HashMap性能优化

实现

怎么解决哈希碰撞

使用链表结构来解决哈希碰撞。当出现哈希碰撞时，两个node通过Key取模运算出的index是一样的，就出现了哈希碰撞。此时HashMap会跟进今后顺序，把所有index一致的节点都放到同一个index的链表上，当查询时如果查到对应的index，会继续遍历链表去查找指定的key。

大数据量查询优化

当链表长度过长时，性能将明显下降，所以JDK1.8采用红黑树降低了查询时间。

解决方法：重写key的hashCode降低hash冲突概率。

扩容带来的性能消耗

如果发生扩容，数组长度会变大，然后会把所有节点重新计算hash值，再重新分布储存。这带来的性能损失是非常大的，所以我们应该尽量避免扩容。

解决方案一：

预估最大容量，阈值=预估值/0.75+1，加1是因为预估值/0.75有可能就是阈值，所以加1主动让他扩容，阔完再用。

为什么要再Put时初始化哈希表

避免在全局使用时造成内存浪费，所以采用了一个懒加载策略。

为什么一定保证是2的次幂

SpaceArray<int,Object>原理

双数组模型，二分查找。