你的位置:首页 > Java教程

[Java教程]java的集合对比


之前一直没有弄清楚过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中添加一条数据时,

image

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

image

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的

image

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

image

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.cnblogs.com/skywang12345/p/3308513.html