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

题记

     前几天有人问我一个问题：“你一般用什么Collection？”，严格地讲应该问：“你一般用什么Collection 和 Map？”
    在应用过程中，这些数据结构非常常用，自己来重温下SUN写的数据结构吧! 

接口关系  
    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()方法线程不安全。如下：

 public boolean add(E o) {
	return m.put(o, PRESENT)==null;
    }

   
**List（CopyOnWriteArrayList,ArrayList,Vector,LinkedList）
    1、ArrayList、Vector都是用的数组，如下：

 E[] elementData;

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

 private transient Entry<E> header = new Entry<E>(null, null, null);
   

   CopyOnWriteArrayList用的数组，如下：

private volatile transient E[] array;

 

    链表和数组的区别，这里不说了。

    2、这几种List都是不排序的，排序需要应用自己控制。
    3、ArrayList、LinkedList都是线程不安全的，Vector、CopyOnWriteArrayList是线程安全的。Vector通过synchronized关键字保证的，这种方式效率不高，如下：

 public synchronized boolean add(E o)

 

而JDK1.5有更好的“锁”方式，CopyOnWriteArrayList的线程安全正是利用1.5的锁特性保证；

不过CopyOnWriteArrayList的add有点特殊，它是通过复制整个数组来保证线程安全的，如下：

 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的存储结构为：

  private transient Object[] queue;

 

     SynchronousQueue存储结构为，但是他的大小总为0：

private transient Node head;

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

  private transient Node<E> head;

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

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

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

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存储结构为 

transient Entry[] table

 

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

 

private transient Entry<K,V> header;

 

WeakHashMap为：private Entry[] table;

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

 

可以看到为实体数组。

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

 

  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;
    }

 

 

 

 

// 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

 

/**
     * 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中有段如下的注释：

/* 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).  
*/

 

 

 

other stuff:

文件锁

JDK 1.4引入了文件加锁机制，允许我们同步访问一个共享文件，不过，竞争同一文件的两个线程有可能在不同的java虚拟机上，或者一个是java线程，另一 个是操作系统中其他的某个线程，但文件锁对其他线程或其他操作系统进程都是可见的，因为java的文件加锁直接映射到了本地操作系统的加锁机制。

注，这里讲的锁是指锁定其他应用程序，而不是锁定同一虚拟机里访问的同一文件的其他线程 。如果在同一虚拟机两次锁定同一文件或某文件里的同一区域，tryLock与lock则会抛出OverlappingFileLockException异常。

要想获取整个文件的锁，可以用FileChannel的tryLock( )或lock( )方法。(SocketChannel，DatagramChannel，以及 ServerSocketChannel是不需要锁的，因为它们是从单进程实体继承而来；一般来说，你是不会让两个进程去共享一个网络socket的。 tryLock( ) 是非阻塞的，它会试着去获取这个锁，但是如果得不到(其它进程已经以独占方式得到这个锁了)，那它就直接返回；而lock( )是阻塞的，如果得不到锁，它会在一直处于阻塞状态，除非它得到了锁，或者你打断了调用它的线程，或者关闭了它要lock()的channel，否则它是 不会返回的。最后用FileLock.release( )释放锁。
还可以像这样锁住文件的某一部分
tryLock(long position, long size, boolean shared)
或者
lock(long position, long size, boolean shared)
这个方法能锁住文件的某个区域(size - position)。其中第三个参数表示是否是共享锁。

虽然在修改文件的过程中，无参数的lock( )和tryLock( )方法的锁定范围会随文件大小的变化，带参数的方法却不行。如果你锁住了position到position+size这段范围，而文件的长度又增加了， 那么position+size后面是不加锁的。而无参数的lock方法则会锁定整个文件，不管它变不变长。

锁是独占的还是共享的，这要由操作系统来决定。如果操作系统不支持共享锁，而程序又申请了一个共享锁，那么它会返回一个独占锁。你可以用FileLock.isShared( )来查询锁的类型(共享还是独占)。

在写文件时才能锁定，如果对一个只读文件通道进行锁定操作时，会抛NonWritableChannelException异常，即new FileInputStream("data2.txt").getChannel().tryLock();时就会抛异常。

另外锁定写文件通道new FileOutputStream("data2.txt").getChannel().tryLock();时，它会清掉原文件中的内容，所以当文件 中有内容时最好使用 new FileOutputStream("data2.txt",true).getChannel().tryLock(); 以追加方式打开写文件通道。或者使用RandomAccessFile类来创建文件通道然后锁定 new RandomAccessFile("data2.txt","rw").getChannel().tryLock(); ，这样它不会破坏锁定的文件的内容。