Java common collections

[TOC]

Collection

最基本的集合类型，所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个共的Collection，有一个Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。

若要检查Collection中的元素，可以使用foreach进行遍历，也可以使用迭代器，Collection支持iterator()方法，通过该方法可以访问Collection中的每一个元素.

Iterator it=collection.iterator();
while(it.hasNext()){
   Object obj=it.next();
}

Set和List是由Collection派生的两个接口

List

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引的位置来访问List中的元素，类似于Java数组。

List允许有相同的元素存在。

除了具有Collection接口必备的的iterator()方法外，还提供了listIterator()方法，放回一个 ListIterator接口。

实现List接口的常用类有LinkedList、ArrayList、Vector和Stack

LinkedList类

LinkedList实现了List类接口，允许null元素。此外LinkedList提供额外的get、remove、insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。LinkedList没有同步方法

AyyayList类

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步方法。

size(),isEmpty(),get(),set()方法运行时间为常数。但是add()方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capactity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入之前可以调用ensureCapacity()方法来增加ArrayList容量已提高插入效率。

Vector类

Vector非常类似ArrayList，当时Vector是同步的。由Vector创建的iterator，虽然和ArrayLsit创建的iterator是同一接口，但是，因为Vector是同步的，当一个iterator被创建而且这在被使用，另一个线程改变了Vector状态，这时调用iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

Stack类

Set

Set是一种不包含重复元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。

HashSet

HashSet调用对象的hashCode(),获得哈希码，然后在集合中计算存放对象的位置。通过比较哈希码与equals()方法来判别是否重复。所以，重载了equals()方法同时也要重载hashCode()。

TreeSet

TreeSet 继承SortedSet接口，能够对集合中对象排序。默认排序方式是自然排序，但该方式只能对实现了Comparable接口的对象排序，java中对Integer、Byte、Double、Character、String等数值型和字符型对象都实现了该接口。

Map

Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供了3中集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key--value映射。

HashTable

HashTable继承Map接口，实现了一个key--value映射的哈希表。任何非空的对象都可作为key或者value。

其操作是同步的。效率太差，不推荐使用。

HashMap

HashMap和HashTable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，但是将HashMap视为Collection时，其迭子操作时间开销和HahMap的容量成比例。

WeakHashMap

WeakHashMap是一种改进的HashMap，他对key实行弱引用，如果一个key不再被外部所引用，那么该key可以被GC回收。

ConcurrentHashMap

ConcurrentHashMap最重要的地方是实现线程安全。我们先看一下他是如何实现线程安全的。再1.7和1.8中，ConcurrentHashMap做了很大的改变。在1.7中ConcurrentHashMap使用了分段锁，1.8中则使用了CAS算法。

JDK1.7—分段锁

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

JDK1.8—CAS算法

CAS原理：CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

LinkedHashMap

LinkedHashMap继承自HashMap，但是一个Map无论如何也是实现不了链表的功能。所以LinkedHashMap自己维护了一个双向链表。这个双向链表按照我们想要的顺序把HashMap中的元素串联起来实现链表。也就是说，数据的存储还是按照HashMap的方式存放，但是LinkedHashMap中维护了一个链表将所有的元素串联起来。

实现 LRU，最近最少使用算法。

StringBuffer和StringBuilder

从字符串的拼接和读取来看，StringBuilder的速度比StringBuffer要快。这是因为Stringbuffer中方法大都采用了synchronized的关键字修饰。也就是说，StringBuffer中所有的方法都要加锁，所以好多操作看上去都是线性操作的。所以要慢些。

StringBuilder不支持并发操作，线性不安全的，不适合多线程中使用。新引入的StringBuilder类不是线程安全的，但其在单线程中的性能比StringBuffer高。

yunshuipiao / Potato