taocr' note: JAVA集合框架.mmap
参考 Collection ， List ， Set 和 Map 用法和区别：
http://blog.csdn.net/zccst/article/details/5056920
参考 Java8系列之重新认识HashMap：
http://www.importnew.com/20386.html
HashMap和Hashtable的区别？
https://www.zhihu.com/question/20581065
Java HashMap工作原理及实现
http://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/
Java 集合系列14之 Map总结(HashMap, Hashtable, TreeMap, WeakHashMap等使用场景)
http://www.cnblogs.com/skywang12345/p/3311126.html
数组、ArrayList、List、LinkedList的区别
http://www.cnblogs.com/janneystory/p/5758958.html
Java并发编程：并发容器之CopyOnWriteArrayList（转载）
http://www.cnblogs.com/dolphin0520/p/3938914.html
java 常用集合list与Set、Map区别及适用场景总结
http://blog.csdn.net/qq_22118507/article/details/51576319
数组的存储空间是连续的，占用内存严重，故空间复杂度很大，但是查找时间复杂度较小。数组的特点：寻址容易，插入和删除困难。
链表的存储空间是离散的，占用内存比较宽松，故空间复杂度较小，但查找时间复杂度较大。链表的特点：寻址困难，插入和删除容易。
Iterable<E>
├— Collection<E> 接口
├— List<E>
├— Queue<E>
├— Set<E>
├— SortedSet<E>
Map<K,V> 接口
├—SortedMap<K,V>
List 是有序的 Collection ，次序是 List 最重要的特点：它保证维护元素特定的顺序。
Set 是一种不包含重复的元素的 Collection ，加入 Set 的元素必须定义 equals() 方法以确保对象的唯一性 （ 即任意的两个元素 e1 和 e2都有 e1.equals(e2)=false ），与 List 不同的是， Set 接口不保证维护元素的次序。最后， Set 最多有一个 null 元素。
Set不能按照索引随机访问元素，这是它与List的一个重要区别。
Map 没有继承 Collection 接口， Map 提供 key 到 value 的映射，你可以通过“键”查找“值”。一个Map 中不能包含相同的 key ，每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图， Map 的内容可以被当作一组 key 集合，一组 value 集合，或者一组 key-value 映射。
list与Set、Map区别及适用场景
1、List,Set都是继承自Collection接口，Map则不是
2、
List特点：元素有放入顺序，元素可重复 ，
Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）
3.Set和List对比：
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
4.Map适合储存键值对的数据
5.线程安全集合类与非线程安全集合类
LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
HashMap是非线程安全的，HashTable是线程安全的;
StringBuilder是非线程安全的，StringBuffer是线程安全的。
1 MAP
Map接口 put() get() remove() 键值对的集合
|
Directionary父类
├—Hashtable 同步、线程安全 数组＋链表（链地址法）
AbstractMap父类
├—HashMap 以下均线程不安全 允许null值键/值 数组＋链表/红黑树
│ ├ LinkedHashMap 保存插入顺序 HashMap + 双向链表
│ └ WeakHashMap 对 key 实行“弱引用” 数组＋链表
├—TreeMap 基于红黑树、结果是经过排序的 红黑树
├—IdentifyHashMap 使用 == 代替equals()对“键”作比较 数组＋链表
└—ConcurrentHashMap 线程安全 读取无锁、写入分段锁 数组＋链表/红黑树
└— ConcurrentSkipListMap 线程安全 适合大规模数据访问 有序 跳表
└— EnumMap Key为Enum类型 数组
1.1 Hashtable
HashTable的key和value都不允许为null值
HashTable使用Enumeration
HashTable直接使用对象的hashCode
HashTable中构造hash数组时initialCapacity默认大小是11，增加的方式是 old*2+1。
Hashtable是遗留类，需要线程安全的场合可以用ConcurrentHashMap替换。
HashTable的方法使用synchronized，所以是线程安全的，但是性能差。
Hash算法：
key的hashCode()
1.2 HashMap
HashMap允许null值键/值
HashMap中构造hash数组时initialCapacity默认大小是16，而且一定是2的指数。
HashMap在JAVA8中一个链表超过8个元素时使用红黑树代替链表，查找复杂度变为O(logN)
HashMap使用Iterator
HashMap重新计算hash值，而且用与代替求模
HashMap线程不安全
查找复杂度：
当Hash算法较好，碰撞少时，O(1)
当碰撞较多，使用链表辅助度O(n)，使用红黑树O(lgn)
Hash算法：
通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)
1.3 TreeMap
TreeMap实现SortedMap接口，能够把它保存的记录根据键排序。
TreeMap 当用Iterator遍历TreeMap时，得到的记录是排过序的。
TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator。
TreeMap 使用Comparator比较键是否相同。
实验发现 HashMap必须要 hashcode 和 equals 都相同，才属于相同的键。
查找/插入复杂度：
平均O(logn)
1.4 ConcurrentHashMap
参考 ConcurrentHashMap和HashMap ：
https://netboyc.gitbooks.io/java-high/content/concurrenthashmaphe_hashmap.html
线程安全，读取无锁。
ConcurrentHashMap的实现方式---锁桶（或段）。ConcurrentHashMap将hash表分为16个桶（默认值），诸如get,put,remove等常用操作只锁当前需要用到的桶。试想，原来只能一个线程进入，现在却能同时16个写线程进入（写线程才需要锁定，而读线程几乎不受限制，之后会提到），并发性的提升是显而易见的。
参考 java中ConcurrentHashMap的使用及在Java 8中的冲突方案：
https://segmentfault.com/a/1190000006811416
CHM适用于读者数量超过写者时，当写者数量大于等于读者时，CHM的性能是低于Hashtable和synchronized Map的。
参考 java8中对ConcurrentHashMap的改进：
http://blog.csdn.net/wangxiaotongfan/article/details/52074160
改进一：取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
改进二：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。
问题：
ConcurrentHashMap、synchronized与线程安全
http://blog.csdn.net/sadfishsc/article/details/42394955
文章中的问题，在于containsKey和put两个操作不是原子的，不是整体同步的
参考：AtomicLongMap的使用
http://chenjumin.iteye.com/blog/2182482
使用锁来解决语句块整体问题，它使用ReentrantReadWriteLock读写锁
这个AtomicLongMap应该就是一个存储AtomicLong的ConcurrentHashMap（可能是Hash）
AtomicLongMap是Google Guava项目的一个类，它是线程安全、支持并发访问的。
ReentrantReadWriteLock会使用两把锁来解决问题，一个读锁，一个写锁
线程进入读锁的前提条件：
没有其他线程的写锁，
没有写请求或者有写请求，但调用线程和持有锁的线程是同一个
线程进入写锁的前提条件：
没有其他线程的读锁
没有其他线程的写锁
<span style="background-color: rgb(255, 255, 255); font-size: 15px;"--<------<span style="background-color: rgb(255, 255, 255); font-size: 15px;"--<------<span style="background-color: rgb(255, 255, 255); font-size: 15px;"--<------<span style="background-color: rgb(255, 255, 255); font-size: 15px;"--<--------------
2 List
List接口 add() get() remove()
|
AbstractList父类
├—ArrayList 线程不安全 数组
├—LinkedList 线程不安全 双向循环链表
├— Vector 线程安全、效率低 数组
├— Stack
Object父类
├— CopyOnWriteArrayList 线程安全
2.1 ArrayList
ArrayList内部实现采用动态数组，当容量不够时，自动扩容至（当前容量1.5+1）。
元素的顺序按照插入的顺序排列。默认初始容量为10。
随机访问效率高，随机插入、删除效率低。
ArrayList是非线程安全的。
get() 直接读取第几个下标，复杂度 O(1)
add(E) 添加元素，直接在后面添加，复杂度O（1）
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）
remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）
2.2 LinkedList
LinkedList内部使用双向链表实现。
随机访问效率低，随机插入、删除效率高。
可以当作堆栈、队列、双向队列来使用。
LinkedList也是非线程安全的。
get(index) 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
remove(index) 删除元素，直接指针指向操作，复杂度O(1)
2.3 Vector
Vector跟ArrayList是类似的，内部实现也是动态数组，随机访问效率高。
Vector是线程安全的。
2.4 Stack
Stack是栈，继承于Vector，其各种操作也是基于Vector的各种操作，因此其内部实现也是动态数组。
先进后出。
Stack是线程安全的。
2.5 CopyOnWriteArrayList
CopyOnWriteArrayList在java的并发场景中用得其实并不是非常多，因为它并不能完全保证读取数据的正确性。
CopyOnWrite容器即写时复制的容器。往一个容器添加元素的时候，先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完再将原容器的引用指向新的容器。
这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
CopyOnWrite容器存在两个问题，即内存占用问题和数据一致性问题。
CopyOnWrite并发容器用于读多写少的并发场景。比如白名单，黑名单，商品类目的访问和更新场景。
内存占用问题：压缩元素或换其他并发容器
数据一致性问题：换其他容器
- 它最适合于具有以下特征的应用程序：set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
- 它是线程安全的。
- 因为通常需要复制整个基础数组，所以可变操作（add、set 和 remove 等等）的开销很大。 迭代器不支持可变 remove操作。
- 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
2.6 List使用场景
对于需要快速插入、删除元素，应该使用LinkedList
对于需要快速随机访问元素，应该使用ArrayList
如果List需要被多线程操作，应该使用Vector，如果只会被单线程操作，应该使用ArrayList
ArrayList等是非线程安全的，即它没有同步，不过，可以通过Collections.synchronizedList()静态方法返回一个同步的实例，如：
List synList = Collections.synchronizedList(list);
<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------<span style="background-color: rgb(255, 255, 255); font-size: 14px; font-family: Arial;"--<-------------
3 Set
Set接口 add() iterator() remove()
|
AbstractSet父类
├— TreeSet 有序 继承SortedSet 基于TreeMap
├— HashSet 无序 基于HashMap
├— LinkedHashSet 有序 基于LinkedHashMap
├— CopyOnWriteArraySet 无序 线程安全 基于CopyOnWriteArrayList
├— ConcurrentSkipListSet 有序 线程安全 基于ConcurrentSkipListMap
├— EnumSet Abstract class 位数组
├— RegularEnumSet 私有实现 一个long存储 64bit
├— JumboEnumSet 私有实现 可存储超过64bit
注意: HashSet
1.HashSet先调用HashCode方法算出Hash值,对比Hash值.相同进行第二步,建议重写HashCode方法
2.调用对象的Equals方法,建议重写Equals方法
注意:TreeSet
1.元素具备自然排序的特点,就按照自然顺序进行排序
2.如果元素不具备自然排序的特点,那么元素需要实现Comparable接口,自定义比较规则,重写CompareTo方法
3.1 Set使用场景
HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。
CopyOnWriteArraySet用于读多写少的并发场景
ConcurrentSkipListSet适用于高并发的场景
