一、ArrayList
长度可变数组，类似于c++ STL中的vector.
元素以线性方式连续存储，内部允许存放重复元素。
允许对元素进行随机的快速访问，但是向ArrayList中插入和删除元素的速度较慢。
ArrayList是非线程安全的，若要成为线程安全，可以使用：List list=Collections.synchronizedList(new ArrayList());
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。
这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。
当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。
二、LinkedList
内部采用双向循环链表实现，类似于c++ STL中的list.
插入和删除元素的速度较快，随机访问的速度较慢.
LinkedList单独具有addFirst(),addLast(),getFirst(),getLast(),removeFirst()和removeLast()方法.
这些方法使得它可以作为堆栈、队列和双向队列来使用.
LinkedList也是非线程安全的.
三、HashMap
基于哈希表的Map接口实现,类似于c++ STL中的unordered_map.
元素是无序的.
采用拉链法来处理哈希冲突，注意：链表中存储的仍然是key值，而非value，对于同一个key，value的新值会替换旧值.
当哈希表中的条目数超过了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（重建内部数据结构），将哈希的桶数量扩大两倍左右.
HashMap是基于HashCode的，HashMap也是非线程安全的，若要线程安全，可用：Map m=Collections.synchronizedMap(new HashMap());
自己实现，最好使用局部锁：把HashMap进行拆分,拆分成了多个独立的块,这样在高并发的情况下减少了锁冲突的可能，增加了并发性.
四、TreeMap
基于红黑树，类似于c++ STL中的map.
使用了SortedMap接口.
确保key键是有序的，无重复的.
也是非线程安全的.
五、HashSet
基于Hash表的Set接口实现，类似于c++ STL中的unordered_set，采用hash散列存储.
元素是无序的，无重复的.
也是非线程安全的.
六、TreeSet
基于红黑树实现，类似于c++ STL中的set.
TreeSet 底层实际使用的存储容器就是TreeMap.
元素是有序的，无重复的.
也是非线程安全的.
七、总结
Java中的容器大多在c++ STL中都有实现，实现方法和使用方法都大同小异.
在Java容器中，只有HashTable和Vector是线程安全（同步）的，同步实现的方法是：
将状态封闭起来，并对每个共有方法进行同步，是的每次只有一个线程能访问容器状态，并发性较差.
------------------------------------------------------------------------------------------
什么是Map.
在数组中我们是通过数组下标来对其内容索引的，而在Map中我们通过对象来对对象进行索引，用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对.
HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）.
HashMap 非线程安全 TreeMap 非线程安全
线程安全
在Java里，线程安全一般体现在两个方面：
1. 多个thread对同一个java实例的访问（read和modify）不会相互干扰，它主要体现在关键字synchronized.
如ArrayList和Vector,HashMap和Hashtable（后者每个方法前都有synchronized关键字）。
如果你在interator一个List对象时，其它线程remove一个element,问题就出现了.
2. 每个线程都有自己的字段，而不会在多个线程之间共享. 它主要体现在java.lang.ThreadLocal类，而没有Java关键字支持，如像static. transient那样.
1.AbstractMap抽象类和SortedMap接口
AbstractMap抽象类：（HashMap继承AbstractMap）覆盖了equals（）和hashCode（）方法以确保两个相等映射返回相同的哈希码. 如果两个映射大小相等. 包含同样的键且每个键在这两个映射中对应的值都相同，则这两个映射相等. 映射的哈希码是映射元素哈希码的总和，其中每个元素是Map.Entry接口的一个实现. 因此，不论映射内部顺序如何，两个相等映射会报告相同的哈希码.
SortedMap接口：（TreeMap继承自SortedMap）它用来保持键的有序顺序. SortedMap接口为映像的视图（子集），包括两个端点提供了访问方法. 除了排序是作用于映射的键以外，处理SortedMap和处理SortedSet一样. 添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现. TreeMap类是它的唯一一份实现.
2.两种常规Map实现
HashMap:基于哈希表实现. 使用HashMap要求添加的键类明确定义了hashCode（）和equals（）.
可以重写hashCode（）和equals（）。为了优化HashMap空间的使用，您可以调优初始容量和负载因子.
- HashMap（）： 构建一个空的哈希映像
- HashMap（Map m）： 构建一个哈希映像，并且添加映像m的所有映射
- HashMap（int initialCapacity）： 构建一个拥有特定容量的空的哈希映像
- HashMap（int initialCapacity, float loadFactor）： 构建一个拥有特定容量和加载因子的空的哈希映像
TreeMap:基于红黑树实现. TreeMap没有调优选项，因为该树总处于平衡状态.
- TreeMap（）：构建一个空的映像树
- TreeMap（Map m）： 构建一个映像树，并且添加映像m中所有元素
- TreeMap（Comparator c）： 构建一个映像树，并且使用特定的比较器对关键字进行排序
- TreeMap（SortedMap s）： 构建一个映像树，添加映像树s中所有映射，并且使用与有序映像s相同的比较器排序
3.两种常规Map性能
- HashMap:适用于在Map中插入. 删除和定位元素.
- Treemap:适用于按自然顺序或自定义顺序遍历键（key）.
4.总结
HashMap通常比TreeMap快一点（树和哈希表的数据结构使然），建议多使用HashMap,在需要排序的Map时候才用TreeMap.
------------------------------------------------------------------------------------------
一、Collection：存放独立元素
Collection中的接口都是可选操作，事实上现类 并不一定实现了其全部接口，这是为了防止“接口爆炸”。
最常见的Unsupported Operation都源自于背后由固定尺寸的数据结构支持的容器，比方使用ArrayList.asList将数组转换成List的时候，就会得到这种容器。
（1）Collection之List
List较之Collection添加了非常多额外的接口，特别是LinkedList。
|
|
长处 |
缺点 |
保存元素的顺序 |
应用 |
| ArrayList |
随机訪问速度快，内部使用数组实现。
|
迭代，插入和删除元素慢， 尤其是当List尺寸比較大的时候。 |
插入顺序 |
可变长数组 |
| LinkedList |
迭代(顺序訪问经过优化)，插入、删除都非常快 内部使用双向链表实现 |
随机訪问速度慢 |
插入顺序 |
顺序訪问, 批量插入删除元素的场合 |
（2）Collection之Set
存入Set的每个元素都必须是唯一的，由于Set不保存重复元素。
可是存入Set的元素必须要定义equals()方法以确保对象的惟一性。
另外Set与Collection有着全然同样的接口。
Set并不保证维护元素的次序，所以须要注意。
Set不包括随机訪问的get方法。由于Set是自己维护内部顺序的，不须要随机訪问。
|
|
长处 |
保存元素的顺序 |
要求 |
| HashSet |
为快速查找设计 |
散列存储 |
必须定义hashCode()方法 |
| LinkedHashSet |
和HashSet一样的查询速度， 可是插入要比HashSet慢一些， 由于它通过维护链表形式维护元素。
|
使用链表维护元素顺序(插入顺序) |
必须定义hashCode()方法 |
| TreeSet |
保存有序的Set，底层通过TreeMap来实现的 |
依照排序顺序维护元素 |
必须实现Comparable接口(包括compareTo方法) |
注意，假设没有特别的限制，HashSet就应该是你的默认选择，由于它对速度进行了优化。
（3）Collection之Queue：
|
|
特点 |
保存元素的顺序 |
| LinkedList |
LinkedList除了普通List之外， 还加入了<队列、栈、双向队列>三种数据结构的方法。 尤其是模拟Queue的时候在两端插入删除元素非常快(经过了优化)。
|
插入的顺序 |
| PriorityQueue |
依照排序顺序取出元素，所以要求必须实现Comparable接口。 |
排序顺序 |
二、Map：存放键-值对
为了保证Map中的唯一性，不论什么“键”都须要有一个equals()方法，推断当前键是否与表中的键同样。
|
|
特点 |
保存元素的顺序 |
要求 |
| HashMap |
Map基于散列存储。插入和查询“键值对”的开销是固定的。
|
散列存储 |
存入的键须要具备hashCode()方法，当然，返回的标识不一定要唯一 |
| LinkedHashMap |
为了提快速度散列了全部元素，插入查询仅仅比HashMap慢一点点，由于它在维护散列数据结构的同一时候还要维护链表(插入顺序)。 可是迭代訪问的时候更快。由于内部使用链表维护次序。
|
插入顺序 |
同样须要键实现hashCode()方法 |
| TreeMap |
Map基于红黑树的实现。所以所得的结果是经过排序的。 |
红黑树 |
为了排序。必须实现Comparable接口。 |
其它为解决特殊问题设计的Map还有IdentityHashMap。WeakHashMap，ConcurrentHashMap等。
实验证明。除了IdentityHashMap之外的其它全部Map，随着Map的尺寸变大，插入会明显变慢。可是查找的代价小非常多。我推測这是由于每次插入都要通过equals方法来确保键值的唯一性导致的，只是Map最经常使用的操作是查询操作，所以情况还比較乐观。
总结：
（1）要想让你的容器类型安全，须要使用泛型（否则编译器同意你向容器中插入各种不同类型，仅仅要是Object就可以）；
（2）创建容器的时候尽量将其向上转型为接口，像这样：
List<Apple> apples = newArrayList<Apple>();
使用接口的目的在于当你决定改动你的实现的时候。仅仅须要在创建的地方改动它就能够了。
（3）Java有大量的用于容器的卓越的方法，他们被封装到java.util.Collections类中，全部都是static方法。
比方Collections类中有unmodifiableMap/List/Set()方法设置Collection和Map为不可改动。还有synchronizedCollection/List/Set/Map等方法同步整个容器。
另外排序，填充，逆置，最大最小值等非常多方法也能够找到。
--------------------------------------------------------- End.
转载请注明：http://www.cnblogs.com/crazyacking/
