集合框架的总结1

总体结构：

 

 

List,Set,Map三者的区别？

• List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象

• Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。

• Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

Collection和Map

1、Collection是一个接口，它包含了集合的基本操作和属性，Collection包含了List和Set两大分支。

• List是一个有序的队列，每一个元素都有它对应的索引，第一个元素的索引值为0,。List的实现类有LinkedList、ArrayList、Vector、stack。

• Set是一个不允许重复元素的集合。Set的实现类有HashSet、TreeMap。HashSet依赖于HashMap，HashSet底层源代码实际上通过实际上通过HashMap来实现的；TreeSet依赖于TreeMap，TreeSet底层源代码实际上通过实际上通过TreeMap来实现的。

2、Map实际上是一个映射接口，即键值对。Map中的每一个元素都包含一个key和key对应的value，AbstractMap是个抽象类，它实现了Map接口中的大部分API，而HashMap、TreeMap都继承于AbstractMap。

3、Iterator是遍历集合的工具，即我们通常使用iterator迭代器来遍历集合，我们说Collection依赖于Iterator，是因为Collection的实现类都要实现iterator()方法，返回一个 Iterator对象，ListIterator是专门为了遍历List而存在的。

Collection

Collection接口是处理对象集合的根接口，也就是顶级接口，Collection接口有两个子接口，分别为List和Set，注意Map不是Collection子接口。

其中有几个比较常用的方法，比如add添加一些元素到集合当中，addAll将指定集合中所有集合添加到另一个集合当中，contains方法检测集合中是否包含指定的元素，toArray将指定的集合转换为数组发返回。Collection中有一个iterator()方法，它作用是返回一个Iterator接口，通常Iterator迭代对象。

List接口

List表示的是一个有序集合，集合中每个元素都有与之对应的的顺序索引，List集合允许使用 重复元素，可以通过索引来访问指定位置的集合元素

List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过索引来访问List中的元素。List接口为Collection直接接口，List代表的是有序Collection，即它用的某种特定插入顺序来维护元素顺序。用户可以对列表中每一个元素的插入位置进行精确控制，同时可以根据元素的索引访问元素，并且搜索列表中的元素。实现List接口的集合主要有ArrayList、LinkedList、vector、Stack。

1）ArrayList

ArrayList是一个动态数组，也是我们常用集合。

它允许任何符合规则的元素插入甚至包括null；

构造器：

每一个ArrayList有三种不同的构造器 ：第一个构造方法就是自定义初始容量。第一个无参的构造方法初始化一个空数组，采用的是延迟初始化数组的策略，这里给elementData数组赋值为空数组，当第一次添加元素时才进行数组的初始化操作；第三个Collection元素列表后，构造方法首先会将其转化为数组，将其索引赋给elementData。。

第一个：public ArrayList(int initialCapacity) { 参数是初始化容积值
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;  空数组
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }
    
第二个：public ArrayList() {  使用的是延迟初始化数组的策略，这里给elementData数组赋值为空数组，当第一次添加元素时才进行数组的初始化操作
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
    }
第三个：public ArrayList(Collection<? extends E> c) { 用于集合类型数据的准换
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

扩容机制分两种情况：

第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

1.无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容，每次扩大到原来的1.5倍。

2.传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容，扩大到原来的1.5倍

3.传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容，扩大到原来的 1.5倍。

第二种情况，当ArrayList的容量大于0，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

2）LinkedList

同样实现LinkedList和ArrayList不同的是，ArrayList底层是一个elementData数组，而LinkedList是一个双向链表，所以它除了ArrayList的基本操作方法之外还额外提供了get、remove、insert方法在LinkedList的首部或者尾部。

由于LinkedList底层是一个双向链表，所以不能随机访问，它所有的操作都是按照双向链表的需要执行。在链表中索引的操作将从头开始或者从尾部开始遍历整个链表，这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

LinkedList和ArrayList一样都是非同步的，如果多个线程同时访问一个List，则必须自己实现访问的同步，一种解决方法是在创建List时构造一个同步的List：

2）LinkedList

同样实现LinkedList和ArrayList不同的是，ArrayList底层是一个elementData数组，而LinkedList是一个双向链表，所以它除了ArrayList的基本操作方法之外还额外提供了get、remove、insert方法在LinkedList的首部或者尾部。

由于LinkedList底层是一个双向链表，所以不能随机访问，它所有的操作都是按照双向链表的需要执行。在链表中索引的操作将从头开始或者从尾部开始遍历整个链表，这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

LinkedList和ArrayList一样都是非同步的，如果多个线程同时访问一个List，则必须自己实现访问的同步，一种解决方法是在创建List时构造一个同步的List：

List list=collections.synchronized(new LinkedList);

 属性：

transient int size = 0;
transient Node<E> first; 头指针
transient Node<E> last; 尾指针

内部类

transient int size = 0;
transient Node<E> first; 头指针
transient Node<E> last; 尾指针

增加add方法

LinkedList执行添加add方法的时候，在链表的尾部添加数据，首先last指向链表最后一个节点，然后新建一个节点对象，其前驱节点为原来的尾节点，后续节点为null；last指向新创建的node对象，如果原来的尾指针指向为null，表示链表中并没有存储数据，使头指针指向新创建的node对象， 如果原来的链表中有数据，则使原来的最后一个节点指向新创建的节点

在指定位置新增数据

针对索引需要进行合法性检查，如果是在末尾追加数据，则使用linkLast，在指定位置的node对象之前添加数据

3) Vector

与ArrayList相似，底层都是由数组来实现的，但是Vector是线程安全的动态数组，但是它的操作与方法和ArrayList几乎一样