博客

前言:这个问题主要是考察集合框架的问题,主要考察三者之间设计的区别,以及使用时如何抉择。

• Vector线程同步(安全),ArrayList、LinkedList线程不同步(不安全)
• Vector是java早期提供的线程安全的动态数组;Arraylist也是动态数组,但不是线程安全的;而LinkedList与前者不同 ,LinkedList是使用双向链表存储的,也不是线程安全的。
• Vector是因为是线程安全的,所以在使用时性能要比ArrayList要差。
• Vector和ArrayList可以根据需要自动增加容量,Vector在扩容的时候是增加一倍,ArrayList在扩容时是增加50%。
• Vector和ArrayList的初始容量都是10,Vector扩容规则是加一倍,即扩容后为20。ArrayList扩容规则在jdk1.7以前是加原大小的1.5倍加一,即10+10/2+1=16。jdk1.7(包含jdk1.7)以后更改为原大小的1.5倍。
• List中的元素有序、允许有重复的元素,Set中不允许有重复元素,其中HashSet的元素无序,LinkedHashSet和TreeSet是有序的。
• LinkedList使用的是双向链表,每个数据节点都有两个指针,分别指向直接前驱和直接后继。删除和插入的时候更改数据节点的后继指针和前驱指针就行,所以速度比数组结构更快。但是随机访问的速度比ArrayList慢。
• Vector和ArrayList内部元素都是以数组形式存储的,所以适合随机访问。除了在头部和尾部插入数据或者删除数据会快一点,其它位置性能会相对较差。比如在中间插入一个元素,需要移动后面所有元素。

详细介绍:

在java的集合框架中,Connection接口是所有集合的根,Connection继承Iterable。

然后扩展开提供三大类集合,List、Set、Queue。

• List是有序的集合,也是Vector、ArrayLsit、LinkedList实现的接口。允许有相同的元素。
• Set是无序的集合,不允许存在重复的元素,这是和List最大的区别。
• Queue是java标准队列的实现,除了集合的基本功能,还支持类似先入先出或者后入后出的特定行为。

List集合

java.util.List接口继承自Collection接口,是单列集合的一个重要分支,习惯性的会将实现了List接口的对象称为List集合。在List集合中允许出现重复的元素,所有的元素是以一种线性方式存储的,在程序中可以通过索引来访问集合中的指定元素。另外,list集合还有一个特点就是元素有序,即元素的存入顺序和取出顺序一致。

List接口特点:

1. 它是一个有序的集合。如:存入的元素为”11″、“33”、“22”。那么集合中就是按照”11″、“33”、”22″的顺序完成的。
2. 它是一个带有索引的集合,通过索引就能精确的操作集合中的元素(与数组索引是一个道理)。
3. 集合中可以有重复的元素,通过equals方法,来比较是否为重复的元素。

List集合的子类

–List有序,可重复

1.ArrayList

java.util.ArraList集合数据存储的是数组结构。线程不安全,但是效率高。元素增删慢,查询快,由于日常开发中使用最多的功能为查询数据、遍历数据,所以ArrayList是最常用的集合。

2.LinkedLsit

java.util.LinkedList集合数据存储的是链表结构。方便元素添加、删除的集合。线程不安全,效率高、查询慢,但是增删快。

3.Vector

java.util.Vector集合数据存储的是数组结构。和ArrayList区别在于它是线程安全的,效率上会低很多。

Set集合

java.util.set接口和java.util.ArrayList接口一样,同样继承于Collection接口,它与Connection接口中的方法基本一致,并没有做功能上的扩充,只是更加严格了。与List接口不同的是,Set接口中元素无序,并且都会以某种规则保证存入的元素不出现重复。

1.HashSet

java.util.HashSet是Set接口的一个实现类,它所存储的元素是不可重复的,并且元素都是无序的(即取出顺序不一致)。

java.util.HashSet底层的实现其实是一个java.util.HashMap支持。

HashSet是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找功能。保证元素唯一性的方式依赖于:hashCode与equals方法。

hashSet结合存储数据的结构**

什么是哈希表?


在JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理冲突,同一哈希值的数据都存在一个链表中。但当位于一个链表中的元素较多,即hash值相等的元素较多时,通过key依次查找效率偏低。而JDK1.8中,哈希表存储策略改为:数组+链表+红黑树实现,当链表长度超过阈值(大于8)时,将链表转换为红黑树,这样大大减少了查找时间。简单来讲,hash表是由数组+链表+红黑树(JDK1.8增加的红黑树)实现的,如图:

那么是如何存储呢?




总而言之,JDK1.8引入了红黑树大程度的优化了HashMap的性能,那么对于我们来讲保证HashSet集合元素的唯一,其实就是根据对象的HashCode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一,就必须复写HashCode和equals方法建立属于当前对象的比较方式。

2.LinkedHashSet

LinkedHashSet底层的数据结构是链表+hash表,由链表保证元素有序(先进先出),由哈希表保存元素唯一。底层是链表实现的，是set集合中唯一一个能够保证怎么存就怎么取的集合对象。

3.TreeSet

TreeSet底层数据结构是红黑树。(唯一且有序)

那么它是如何排序呢?

1.自然排序

Comparble自然排序,实体类实现Comparble接口,可以去重写compareTo()方法,解决实际排序问题。把元素放到TreeSet里面去,就会自动调用compareTo()方法;但是这个comparable并不是专门为了TreeSet设计的;只是说TreeSet顺便利用而已;就像HashCode和equals也一样,不是说为了HashSet设计的 ;只是其中顺便利用而已。

2.比较器排序

Compartor是第三方的比较接口,也不是专门为了TreeSet设计 。用法:设计一个比较器,创建一个类实现这个接口,重写compare()方法,解决不同问题的需求。

参考文章1:

Java集合（Connection）体系


参考文章2:

Java集合中List,Set以及Map等集合体系详解(史上最全)


参考文章3:

TreeSet ——自然排序与定制排序（比较器）