Android-Java:常用基本容器学习总结
1.常用容器的总体框架
2.常用容器类的重点
1. ArrayList
https://www.cnblogs.com/skywang12345/p/3308556.html
1.1 存储结构：
value值存在elementData这个Object类型的数组中，默认容量是10。
1.2 容器特点：
- ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。
- ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输.
- ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList.
1.3 注意事项：
- 遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低
- ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList.
2. Vector
Vector 是矢量队列，继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。
https://www.cnblogs.com/skywang12345/p/3308833.html
2.1 存储结构：
value值存在elementData这个Object类型的数组中，默认容量是10。
2.2 容器特点：
-
Vector中的操作是线程安全的,add(),remove(),clear()等操作均加上了synchronized保护;
在这里插入图片描述
3. Stack
Stack是继承Vector来实现，基于Vector的addElement和removeElement来实现push,pop,peek操作，因此Stack也是通过数组实现的，而非链表。
3.1 存储结构：
实质上还是用的Vector的数组实现：
3.2 容器特点：
- Stack实际上也是通过数组去实现的。
执行push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。
执行peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
执行pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。 - Stack继承于Vector，意味着Vector拥有的属性和功能，Stack都拥有。
4. HashMap
http://androidxref.com/9.0.0_r3/xref/libcore/ojluni/src/main/java/java/util/HashMap.java
4.1 存储结构：
JDK1.8 链表结构优化为数组+红黑树形式：
JDK1.8 之前数据+链表实现：
数组是HashMap的主体，链表，红黑树则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表或红黑树,那么对于查找，添加等操作很快，仅需一次寻址即可；
如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。
所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
4.2 容器特点：
- HashMap线程不安全；
- HashMap可以接受为null的键值(key)和值(value)
5. HashTable
HashTable和Hashmap类似，有个HashTableEntry 类型的数组成员变量table，管理着键值对。
Hashtable是synchronized，这意味着Hashtable是线程安全的
但是HashTable已经被淘汰了，如果不需要线程安全，那么使用HashMap，如果需要线程安全，那么使用ConcurrentHashMap。
5.1 HashTable方法API：
5.2 容器特点：
- Hashtable 的函数都是同步的，这意味着它是线程安全的。
- 它的key、value都不可以为null。
- Hashtable中的映射不是有序的。
- 该类型已经提示被淘汰，需要线程安全的话可以使用ConcurrentHashMap
6. HashSet
- HashSet是一个集合，集合中不允许出现重复元素。
- HashSet是基于HashMap实现，HashSet中有一个HashMap的成员变量map，HashSet的Value 值会被以键值对<Value，PRESENT>加入到map中，由于HashMap不可以有重复的key，因而实现了set的去重。
6.1 注意事项：
- HashSet实现了Set接口，它不允许集合中出现重复元素。当我们提到HashSet时，第一件事就是在将对象存储在HashSet之前，要确保重写hashCode（）方法和equals（）方法，这样才能比较对象的值是否相等，确保集合中没有储存相同的对象。
案例：https://www.cnblogs.com/dongying/p/4024519.html
7. ConcurrentHashMap
原理：http://www.cnblogs.com/chengxiao/p/6842045.html
7.1 存储结构：
Segmemt：
每个绿色方块是ConcurrentHashMap的一个Node：
7.2 容器特点：
1.ConcurrentHashMap是线程安全的；
1.ConcurrentHashMap不同于HashMap，它既不允许key值为null，也不允许value值为null；
2.HashTable容器的get方法是需要加锁的，而ConcurrentHashMap的get操作是不加锁的，原因是它的get方法里将要使用的共享变量都定义成volatile；
3.在ConcurrentHashMap中，每个hash区间使用的锁是ReentrantLock；
Android中独有的：
8. SparseArray
8.1 存储结构：
8.2 容器特点
- SparseArray在存储和读取数据时候，使用的是二分查找法；
- 满足下面两个条件我们能够使用SparseArray取代HashMap：
a.数据量不大，最好在千级以内;
b.key必须为int类型，这中情况下的HashMap能够用SparseArray取代; - SparseArray被称为稀疏数组，原因是数组中可能并不是连续存储着value，remove方法并没有去直接删掉元素，而是将这个key指向了DELETED，这时候value失去了引用，如果没有其它的引用，会在下一次系统内存回收的时候被干掉，或者该key被复用指向新的值，是一个优化；
- SparseArray不需要开辟内存空间来额外存储外部映射，从而节省内存，key为int的时候才能使用，注意是int而不是Integer，这也是sparseArray效率提升的一个点，去掉了Hashmap的装箱的操作。
9. ArrayMap
https://www.jianshu.com/p/1fb660978b14
9.1数据结构：
- 数据变量含义：
（1）mHashes，用于保存key对应的hashCode；
（2）mArray，用于保存键值对（key，value），其结构为[key1,value1,key2,value2,key3,value3,......]；
（3）mBaseCache，缓存，如果ArrayMap的数据量从4，增加到8，用该数组保存之前使用的mHashes和mArray，这样如果数据量再变回4的时候，可以再次使用之前的数组，不需要再次申请空间，这样节省了一定的时间；
（4）mTwiceBaseCache，与mBaseCache对应，不过触发的条件是数据量从8增长到12； - allocArrays（）
- 适用场景：
a. 数据量不大
b.空间比时间重要
c.需要使用Map在Android平台，相对来说，内存容量更宝贵。而且数据量不大。所以当需要使用key是Object类型的Map时，可以考虑使用ArrayMap来替换HashMap - 中占据时间复杂度最多的属于第一步:确定key的hashCode在mHahses中的索引值。而这一步对mHashes查找使用的是二分查找，即Binary Search。所以ArrayMap的查询时间复杂度为 O(log n);
