List集合解析

| 分类于

前言

在Collection接口下,有两大接口,List和Set,List可以存放重复元素,Set不能存放重复元素.一直以来都只是使用它们,并没有仔细去看过他们的实现.直到前不久瞄了瞄他的底层.竟然发现了不得了的事情,身为Collection的孩子List的兄弟,Set竟然有Map的血缘…..

Collection接口

在Java的类集里面(java.util包)提供了两个最为核心的接口:Collection、Map接口。其中Collection接口的操作形式
与之前编写链表的操作形式类似，每一次进行数据操作的时候只能够对单个对象进行处理。
collection是单个集合保存的最大父接口
collection接口定义如下:

1
public interface Collection<E> extends Iterable<E>

他继承了Iterable接口,所有实现该接口的类都可以使用迭代
在开发中很少直接使用Collection,他只是一个存储数据的标准,并不能区分存储类型,在平时往往使用它的实现类
List(可以存储重复数据)
Set(不能够存储重复数据)

List接口

List接口是Collection接口的一个子接口,这个类型的数据结构中可以存储重复的数据.与Collection相比,List的不同在于他扩充了两个方法.

1
2
E get(int index);
E set(int index, E element);

get()方法可以根据索引取得索引处的数据内容
set()方法可以根据所以改变索引出的数据内容
List也是一个接口,也就意味着想要实现这个接口,还需要有具体的实现类
List有三个实现类,ArrayList,LinkedList,Vector

ArrayList

底层的实现是动态数组,类似于我们顺序表,能够自动扩容,长度可变
他的优势在于查找效率高,可以通过下标以O(1)的时间复杂度直接进行数据的查找get(index)
他的缺点在于插入和删除数据的时候过于麻烦,需要移动数组中的其他对象,时间复杂度过高,但是如果数据的频繁插入删除是在尾部进行,实际上也是使用ArrayList多一点
另外,ArrayList的所有方法都是默认在单一线程下进行的,所以该类是线程不安全的,在多线程的环境下使用需要加锁

ArrayList和Vector底层都是动态数组,他们的区别在于ArrayList数组的创建采用的是懒加载的方式,在第一次调用add方法的时候才进行数组的初始化工作 ; 而Vector数组的初始化是在构造方法中进行的 ,两个集合默认的数组初始化大小都是10 ;
在扩容方面他们还有一个区别,ArrayList每次扩容为原来的1.5倍,而Vector扩容为原来的2倍

ArrayList中的一个大坑

ArrayList中有一个重载方法remove

1
2
3
4
//删除该列表中指定位置的元素
remove(int index) 
//从列表中删除指定元素的第一个出现（如果存在）
boolean remove(Object o)

如果现在创建一个int类型的List集合,想要删除其中元素,一定要注意此时传的参数,如果直接传一个int值,那么删除的就是下标.如果想要删除指定元素第一次出现的位置,那么需要把这个int类型包装一下,否则是不能够删除的

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Test {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(5);
        list.add(6);
        list.add(8);
        list.remove(new Integer(8));
        System.out.println(list);
    }
}

否则会报出数组下标越界的异常

LinkedList

可以认为是一个双向的链表,不同于ArrayList以数组作为单位,他是以每一个单一节点作为单位的
他的优势在于可以随意在任何位置插入或删除数据,且执行的效率非常的高.
他的缺点在于由于是双向链表的缘故,他的查找效率比较低下
LinkedList也是线程不安全的,对于数据频繁出入,并且要求操作灵活度高的数据,一般使用LinkedList.对于数据变动不大,经常用于查询的数据元素,一般使用ArrayList

Vector

Vector和ArrayList实现的方式基本相同,底层都是动态数组,唯一不同的一点在于,Vector中的方法基本都使用了synchronized修饰保证了线程安全.所以在单一线程的操作中可以使用ArrayList来代替Vector从而提高效率.而在多线程程序中可以使用Vector代替ArrayList来保证数据的同步和一致性

Set集合接口

Set集合接口和List集合接口的最大区别在于他不能存储重复的数据元素.同时,Set接口没有对Collection接口进行扩充,所以他的里面没有get()方法
在Set接口中有两个常用的实现类: HashSet(无需存储),TreeSet有序存储

HashSet

HashSet的底层就是一个HashMap,看看源码

1
2
3
public HashSet() {
        map = new HashMap<>();
    }

并且HashSet中的方法基本也都是直接调用map中的方法的
例如HashSet的add操作

1
2
3
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

可以看到使用HashSet的add操作实际上是调用了map的put操作,然而只是put了键值,value处的值使用了PRESENT,看看他的定义

1
2
// Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

通过有道词典的翻译”中的对象关联的虚值”…呵呵,大概可以知道这是一个虚值.也就是说HashSet底层使用了HashMap,但是仅仅使用了键域,而没有使用值域,这也就解释了为什么HashSet存储的元素不能重复
在实际使用中如果存储了重复的元素,也不会进行报错,但在打印的时候会发现重复添加进去的元素实际上只有一个

注意: 由于HashSet没有实现ComParable接口,所以想要比较放入其中的对象,那么在对象类的定义时就要实现接口Comparable,并且覆写其中的两个方法,这有这两个方法都判断相等,那么这两个对象才是相等的,否则不能消除

1
2
1. hash码： public native int hashCode();
2. 对象比较：public boolean equals(Object obj);

若想实现对象比较,这两个方法都需要覆写

TreeSet

TreeSet部分底层源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
   
    private transient NavigableMap<E,Object> m;

    
    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

   
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

从源码中可以看到TreeSet中有一个构造器

1
2
3
TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

而TreeSet默认的构造方法是调用这个构造器的,并且实例化对象为TreeMap. 那么也就是说,TreeSet的底层实现其实就是TreeMap,但是在实例化赋值的时候转换成了NavigableMap接口的实现类,之所以可以这样转换其实是因为TreeMap类本来就实现了接口 NavigableMap ,而NavigableMap接口继承自SotredMap
接口,实现这两个接口意味着它支持一系列的导航方法。比如返回有序的key集合。而TreeMap的底层实现就是一个红黑树,该映射根据其键的自然顺序进行排序，如果想用自己实现的排序规律就要在对象类实现Compareable接口,覆写比较的具体方法。
treeMap中有排序接口,使得treeSet可以进行不同方式的排序

1
2
3
4
5
6
7
8
9
10
11
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;

TreeMap底层的红黑树中的每一个节点都是一个k-v对,以下是treeMap中节点源码的定义

1
2
3
4
5
6
7
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

可以很明显的看出来就是红黑树

(补充一点: NavigableMap对象被关键字transient修饰,意味着该对象不能进行序列化和反序列化操作)

hashSet和TreeSet的区别

1.treeSet自动排序,hashSet是无序的
2.treeSet比较重复元素是通过实现接口Compareable,hashSet比较重复元素是通过Object类中的hashCode()和equlas方法
3.hashSet底层实现是hashmap,treeSet底层实现是treeMap;hashmap就是哈希表,treeMap的底层实际上是红黑树

遍历集合

迭代器

Collection接口继承了Iterable接口,所以Collection下的所有子类都可以使用迭代器

1
public interface Collection<E> extends Iterable<E>

不能在迭代器中使用集合引用对象删除或添加元素个数

例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test {

    public static void main(String[] args) {

        //底层实现是一个线性表
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            Integer i = (Integer) iterator.next();
            System.out.println(i);
//            iterator.remove();
            if(i.equals(1)){
                list.remove(i);
            }
        }
    }
}

此例中,使用list的迭代器遍历list集合中的元素时,想要删除元素值为1的元素,于是在遍历时拿各个元素和1做比较,找到后使用list的remove删除. 看似逻辑没有什么问题,但实际上真正运行起来会报 java.util.ConcurrentModificationException 异常
原因: 每当集合发生一次add或remove等类似会改变集合内部结构(元素个数)的方法时,集合内部记录修改次数的modcount属性就会+1,当整个集合创建完毕,结构不在发生变化的时候(即集合创建完毕,该调用迭代器的时候),调用迭代器,迭代器中有一个expectedModCount属性,他会被赋值为modCount,只有当这个值相等的时候,迭代器才能够进行正常的迭代输出,所以,当在迭代器中遍历集合时,使用集合的删除或添加操作,此时modCount会被+1,与expectedModCount属性值就会不同,此时就会抛出异常
该异常位于迭代器中的方法

1
2
3
4
5
final void checkForComodification() {
		//如果修改的值和期望的值不同则抛出异常   
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }

双向迭代接口

ListIerator继承自Iterator,专门针对List,可以从俩个方向遍历List,同时支持元素的修改
有一点需要注意: 如果想要实现从后向前遍历,就要先实现从前向后遍历,否则从后向前遍历是没有结果的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//双向迭代器的使用范例
public class Test {

    public static void main(String[] args) {
        //底层实现是一个线性表
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        
        //双向迭代器
        ListIterator iterator1 = list.listIterator();
        //先实现从前向后遍历
        while(iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
        //从后向前遍历
        while(iterator1.hasPrevious()){
            System.out.println(iterator1.previous());
        }
    }
}

foreach

所有类型都可以使用foreach进行遍历
需要注意的是,foreach循环中也不可以使用集合对象删除集合中的元素,否则也会出异常 java.util.ConcurrentModificationException

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Test {

    public static void main(String[] args) {

        //底层实现是一个线性表
        List<Integer> list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        //错误的删除方式
        for(Integer i:list){
            if(i.equals(2)){
                list.remove(i);
            }
        }

        for(Integer i:list){
            System.out.println(i);
       }

    }
}