java的集合对比----Collection

之前一直没有弄清楚过java的各种集合的差异，所以在这里合在一起对比下。

Collection and Map

java的所有集合都来自于Collection和Map这两个接口中的其中一个。

Collection接口是普通的集合接口。

Map接口有点特殊，他的元素都是以Key-Value的形式存储。

先对比Collection下的集合，它的下面又有两个大类，一个list接口，一个set接口，他们最大的不同就是set中不允许有重复的元素。

List接口

List继承了Collection接口，他是一个有序的集合，实现这个接口的类有4个：ArrayList,LinkedList,Stack和Vector。

ArrayList：我习惯把他当作一个长度可以自动增长的动态数组，通过名叫elementData的数组来保存元素，他不是线程安全的。如果不在初始化指定大小，默认为10个。关于每次的自增大小，我看见一些博客上说是：新的容量=“(原始容量x3)/2 + 1”但是我在eclipse中打断点发现却是：新的容量=“(原始容量x3)/2”，取整。在下面代码中，11行打断点。

 1 public class test { 2      3     public static void main(String[] args){ 4          5         List<Integer> list = new ArrayList<Integer>(3); 6          7         for (int i = 0; i < 3; i++) { 8             list.add(i); 9         }10         11         for (int i = 0; i < 1; i++) {12             list.add(i);13         }14 15     } 16 }

可以看到此时elementData长度为3，当我向下执行再向list中添加一条数据时，

可以看到，他的elementData长度为4，而不是5；我试了下初始容量为9，超出后也为13，而不是14；

LinkedList：他以链表的形式存储，而且是双向链表，可以get()随机访问，可以当作栈，队列，双端队列使用，因为他实现了pop，push，peek，peekFrist,peekLast，poll，pollFrist,pollLast方法，poll返回头，并移除。peek至返回。他不是线程安全的。

 1 public class test { 2      3     public static void main(String[] args){ 4          5         LinkedList<Integer> list = new LinkedList<Integer>(); 6          7         for (int i = 0; i < 10; i++) { 8             list.push(i); 9         }10         11         System.out.PRintln(list.size());//1012         list.poll();13         System.out.println(list.size());//914         list.peek();15         System.out.println(list.size());//916 17     } 18 }

ArrayList和LinkedList的选用：对于数组来说，增加一个元素，特别是在中间增加一个元素，需要移动其他元素，而链表不存在这种问题，链表只需改变指针地址即可。但是对随机访问，链表却存在一个问题，就是链表的数据结构决定了他只能顺序访问，即便他可以用get（）随机访问，也是一个一个找下来的。因此，在选择用哪个时，应该考虑当前集合是否频繁改变大小size，是否频繁的随机访问。

Vector:感觉和ArrayList差不多，但是他是线程安全的。

Stack：标准的栈（FILO），继承自Vector，同样用数组实现，peek方法只取不弹。

集合的线程安全性

首先，Vector和Stack是线程安全的，而ArrayList和LinkedList不是线程安全的。我用代码的运行结果来证明下，想法是这样的，我用两个线程，每个线程都向list中添加100个数，那么，按照正常的想法，最后list的大小list.size()是应该等于200的。

 1 public class test { 2  3     //List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>()); 4     //List<Integer> list = Collections.synchronizedList(new LinkedList<Integer>()); 5     //List<Integer> list = new ArrayList<Integer>(); 6     //List<Integer> list = new Vector<Integer>(); 7     List<Integer> list = new LinkedList<Integer>(); 8     //Stack<Integer> list = new Stack<Integer>(); 9     public static void main(String[] args) {10         test t = new test();11 12         ThreadA tA = t.new ThreadA();13         ThreadB tB = t.new ThreadB();14         //开始线程15         tA.start();16         tB.start();17         try {18             tA.join();19             tB.join();20         } catch (InterruptedException e) {21             e.printStackTrace();22         }23         System.out.println("list size：" + t.list.size());24     }25     class ThreadA extends Thread {26         @Override27         public void run() {28             super.run();29             for (int i = 0; i < 100; i++) {30                 list.add(i);31                 //list.push(i);32             }33         }34     }35     class ThreadB extends Thread {36         @Override37         public void run() {38             super.run();39             for (int i = 0; i < 100; i++) {40                 list.add(i);41                 //list.push(i);42             }43         }44     }45 }

list的类型为ArrayList时的结果，不管多少次基本没有等于200的

list的类型为Vector时的结果，不管多少次，都等于200.

ArrayList为什么会出现这种情况？

不管怎么执行，ArrayList的大小不会超过200。向ArrayList添加数据时有两步，首先加入到数组中，然后size++，假设添加第一条数据，此时size=0，ThreadA理所当然应该在0位置添加一个值，但是此时ThreadA被阻塞，ThreadB被执行，由于ThreadA还没来得及执行size++，所以size仍然等于0，那ThreadB也应该在0位置添加一个值，把ThreadA赋的值覆盖掉了，ThreadB继续执行size++，size=1。接着ThreadA继续执行，size++，size=2，；但现实中，我的list只有一个值，size等于1。因此，可以推断出来，ArrayList的大小不会超过200，是因为在某些时刻，ThreadA和ThreadB同时把数据写到了一个位置上，造成了数据的丢失。

怎么解决？

就像上面代码的第三行，在初始化时用Collections.synchronizedList（）函数，即可让ArrayList和LinkedList变成线程安全的集合。

这里强烈推荐一个博客，把集合介绍得很详细：http://www.VEVb.com/skywang12345/p/3308513.html