ArrayList
优点：查找快，尾部插入（删除）快
缺点：删除（插入） 头部（中间）的元素慢
- 查找快：是因为内存是连续的，0xabcdefg + i * 4 可以快速找到元素
- 尾部插入（删除）快：不需要 arrayCopy
LinkedList
优点：插入（删除）速度快
缺点：查找速度慢
- 插入（删除）速度快：双向链表的数据接口，只需要修改指向（prv、next）就可以完成
- 查找速度慢：验证链表一直往下找
HashMap
1.7 之前：数组 + 链表
1.8 之后：数组 + 链表 + 红黑树
优点：结合了 ArrayList 和 LinkedList 的优点
缺点：内存浪费，25%浪费，空间换时间，扩容时耗时
-
put：对 key 进行获取 hashCode，对 length 进行求模，如：
map 的 length 默认为 16，假设 “key” 的 hashCode 为 18，求模结果为：2
往下标 2 的位置插入数据，将原位置的数据以链表的数据结构设为下一个节点。 -
get： 对 key 进行获取 hashCode，对 length 进行求模，再对链表进行轮询来判断 hash 与 key 都相通，再将 value 返回回去。 -
put 的时候可能哈希碰撞，如：
length = 16;
hash1 = 18;
hash2 = 34;
index = 2;
都往 index 的地方插入数据，那么就利用链表的数据结构。
- 长度必须是 2 的次幂
数学家得出的结论，为了减少哈希碰撞 - 阈值 0.75
元素数量达到 length 的 0.75 时，将会对 length 进行扩容，长度为原来的 2 倍 - 扩容
扩容后长度变了，所以求模的 length 变了，所以根据 key 找不到对应的 value 了，所以扩容的时候必须重新计算求模，所以会耗性能，我们应该尽量避免扩容 - new 对象的时候，尽量设置 length
SparseArray
优点：内存节约，二分法查找
缺点：key 只能是 int
put：利用二分法来获取位置
get：利用二分法来获取位置
ArrayMap
hashMap + sparse
|