初看Java容器的艺术（待续）

接口关系
    0上层接口为：Collection & Map
    Collection：Set、List、Queue；
              Set：HashSet、TreeSet
              List：ArrayList、Vector、LinkedList、
         Queue：LinkedList、PriorityQueue、LinkedBlockingQueue（JDK1.5）等
             Map：HashMap、Hashtable、TreeMap、WeekHaspMap、ConcurrentHashMap、LinkedHashMap等
   这些都是些线型结构（栈、队列、链表等）、网型结构（图、树等）、混型结构（线网混合）。    而比较所有这些结构中，主要从几个方面：
     1、基本数据存储（部分结构还有强引用、软引用、弱引用之分）
     2、是否排序
     3、Thread Safe？
  **Set（HashSet,TreeSet）
  1、两种主要Set都是用的HashMap等存储，所以HashMap所拥有的特性Set都拥有，如果熟悉map的话，Set很容易理解；
  2、HashSet是不排序Map，TreeSet是排序Map；
  3、是不是thread safe看add（）方法，既然Set直接用的是map.put()，HashMap的put()方法线程不安全。如下：

Java代码
public boolean add(E o) { 
return m.put(o, PRESENT)==null; 
   } 
public boolean add(E o) {
return m.put(o, PRESENT)==null;
}
   
**List（CopyOnWriteArrayList,ArrayList,Vector,LinkedList）
    1、ArrayList、Vector都是用的数组，如下：

Java代码
E[] elementData; 
E[] elementData;
    LinkedList是一个链表，用的“内部静态节点”（静态内部类用于内部使用，可访问创建类的静态变量或方法），如下：

Java代码
private transient Entry<E> header = new Entry<E>(null, null, null); 
   
private transient Entry<E> header = new Entry<E>(null, null, null);
   CopyOnWriteArrayList用的数组，如下：

Java代码
private volatile transient E[] array; 
private volatile transient E[] array;
    链表和数组的区别，这里不说了。     2、这几种List都是不排序的，排序需要应用自己控制。
    3、ArrayList、LinkedList都是线程不安全的，Vector、CopyOnWriteArrayList是线程安全的。Vector、 CopyOnWriteArrayList通过synchronized关键字保证的，这种方式效率不高，1.5有更好的“锁”方式；

Java代码
public synchronized boolean add(E o) 
public synchronized boolean add(E o)
CopyOnWriteArrayList的add有点特殊，如下：

Java代码
public synchronized boolean add(E element) { 
       int len = array.length; 
       E[] newArray = (E[]) new Object[len+1]; 
       System.arraycopy(array, 0, newArray, 0, len); 
       newArray[len] = element; 
       array = newArray; 
       return true; 
   } 
public synchronized boolean add(E element) {
int len = array.length;
E[] newArray = (E[]) new Object[len+1];
System.arraycopy(array, 0, newArray, 0, len);
newArray[len] = element;
array = newArray;
return true;
}
**Queue（ProorityQueue,SynchronousQueue,LinkedBlockQueue,ConcurrentLinkedQueue）
    1、PriorityQueue的存储结构为：

Java代码
private transient Object[] queue; 
  private transient Object[] queue;
     SynchronousQueue存储结构为，但是他的大小总为0：

Java代码
private transient Node head; 
private transient Node head;

    LinkedBlockingQueue的存储结构也同LinkedList类似，也是“内部静态节点”。

Java代码
private transient Node<E> head; 
  private transient Node<E> head;
   当一个消费者试图读取一个空的LinkedBlockingQueue时，它可以不返回，制定等待时间一直等待生产者的出现，想要将一个项插入到满队列的尝试也会导致阻塞调用线程，直到队列的存储空间可用。
  

    2、PriorityQueue、LinkedBlockingQueue、ConcurrentLinkedQueue都不做排序，SynchronousQueue排序没有意义。
  

    3、PriorityQueue是线程不安全，而LinkedBlockingQueue是1.5的新特性，如果高效保证线程安全是主要工作，主要是处于对于synchronzied关键字效率低的优化，主要运用了锁队列等机制。
    SynchronousQueues每个插入操作必须等待另一个线程的对应移除操作，反之亦然，这个容器容量甚至不为1，即size总为0，测试程序如下：

Java代码
static class cosumer extends Thread{ 
         BlockingQueue que; 
        .... 
        public void run(){ 
            System.out.println(que.take());//  如果队列size==0的时候，线程阻塞，直到其他线程put数据 
        } 
    } 
    static class producer extends Thread{ 
        BlockingQueue que; 
        public void run(){ 
            que.put(System.currentTimeMillis());// 队列发生阻塞，当前线程阻塞，知道其他线程take走数据 
            System.out.println(que.size()); // print 0 
            que.put(System.currentTimeMillis()); 
            System.out.println(que.size());// print 0 
        } 
    } 
    public static void testsynQueue(){ 
        BlockingQueue que=new SynchronousQueue(); 
        new cosumer(que).start(); 
        new producer(que).start(); 
    } 
static class cosumer extends Thread{
BlockingQueue que;
....
public void run(){
System.out.println(que.take());//  如果队列size==0的时候，线程阻塞，直到其他线程put数据
}
}
static class producer extends Thread{
BlockingQueue que;
public void run(){
que.put(System.currentTimeMillis());// 队列发生阻塞，当前线程阻塞，知道其他线程take走数据
System.out.println(que.size()); // print 0
que.put(System.currentTimeMillis());
System.out.println(que.size());// print 0
}
}
public static void testsynQueue(){
BlockingQueue que=new SynchronousQueue();
new cosumer(que).start();
new producer(que).start();
}
   会发现线程阻塞。

  **Map(HashMap,LinkedHashMap,TreeMap,Hashtable,WeakHashMap,IdentityHashMap,ConcurrentHashMap）

    1、HashMap、Hashtable存储结构为

Java代码
transient Entry[] table 
transient Entry[] table
     TreeMap为：private transient Entry<K,V> root = null;（存储结构决定了数据操作，节点型数据有利于排序），可以猜出LinkedHashMap为节点型存储结构：

Java代码
private transient Entry<K,V> header; 
private transient Entry<K,V> header;
WeakHashMap为：private Entry[] table;

      ConcurrentHashMap高并发Map是把数据分割成了很多final Segment[] segments;

可以看到为实体数组。

     HashMap插入的顺序与输出的顺序是不同的，那么是以什么顺序做插入的呢？我们看看put方法：

Java代码
public V put(K key, V value) { 
      K k = maskNull(key); 
      int hash = hash(k); // HashMap自行计算hashcode 
      int i = indexFor(hash, table.length);// 根据hash值来判定数组位置 
 
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {// 查找table[i]链表是否有符合的值 
          if (e.hash == hash && eq(k, e.key)) { // 注意这里的eq（），他会比较K的equals()的返回值，这也就为什么重写hashcode后，同时需要重写equals方法，不然就为Object的equals方法了。 
              V oldValue = e.value; 
              e.value = value; 
              e.recordAccess(this); 
              return oldValue;// 如果是已装入容器的对象，则直接返回 
          } 
      } 
 
      modCount++; 
      addEntry(hash, k, value, i);// 如果没有，入table[i]链表中 
      return null; 
  } 
  public V put(K key, V value) {
K k = maskNull(key);
int hash = hash(k); // HashMap自行计算hashcode
int i = indexFor(hash, table.length);// 根据hash值来判定数组位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {// 查找table[i]链表是否有符合的值
if (e.hash == hash && eq(k, e.key)) { // 注意这里的eq（），他会比较K的equals()的返回值，这也就为什么重写hashcode后，同时需要重写equals方法，不然就为Object的equals方法了。
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;// 如果是已装入容器的对象，则直接返回
}
}
modCount++;
addEntry(hash, k, value, i);// 如果没有，入table[i]链表中
return null;
}
Java代码
// addEntry操作主要如下，这里的bucketIndex是插入的位置 
void addEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex]; 
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
        if (size++ >= threshold) 
            resize(2 * table.length);//HashMap自行扩展table[]空间，复制的时候会消耗性能 
    } 
// addEntry操作主要如下，这里的bucketIndex是插入的位置
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);//HashMap自行扩展table[]空间，复制的时候会消耗性能
}
    bucketIndex是通过indexFor(hash, table.length)来的，然后看看indexFor

Java代码
/**
     * Returns index for hash code h. 
     */ 
    static int indexFor(int h, int length) { 
        return h & (length-1); 
    } 
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
所以显然顺序就不同的了，如果要保持顺序，可以用TreeMap,LinkedHashMap

     WeekHashMap为private static class Entry<K,V> extends WeakReference<K> implements         Map.Entry<K,V>，他是继承了WeakReference，弱引用是不入JVM的引用队列的，所以随时可能被GC回收。

     LinkedHaspMap是一个双向链表存储结构存储Entry
     存储结构为：private transient Entry<K,V> header，非数组结构，为链表结构;

     线程非安全

     排序的，插入顺序与输出顺序一致，遍历的时候

      ConcurrentHashMap

    StringBuffer和StringBuilder

    在StringBuilder的comments中有段如下的注释：

Java代码
/* This class is designed for use as a drop-in replacement for
* <code>StringBuffer</code> in places where the string buffer was being
* used by a single thread (as is generally the case).  
*/ 

转自：http://www.huomo.cn/developer/article-e710.html