Collection

继承关系

所有：统称集合

然后大类分为:

• List，列表：ArrayList,LinkedList,Vector(很少用了)...
• Set，集：HashSet，LinkedHashSet，TreeSet...
• Queue,队列：PriorityQueue，ArrayBlockingQueue...

List是有序的，ArrayList，Linked都有序，只是内部实现不一样。

ArrayList基于数组实现，LinkedList基于链表实现。

常用的集合类关系图

先了解一下什么是数组？

数组是一段连续的内存空间，需要指定长度，一旦分配，不可以动态改变大小。

List

ArrayList

ArrayList就是基于数组结构的，但是我们平时使用的时候，ArrayList是动态添加的，自动扩展长度的。

它内部是如何做的呢？

1. 创建

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

数据对象赋值为

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

1. 添加元素

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

这个ensureCapacityInternal往下走的代码主要是这个

 elementData = Arrays.copyOf(elementData, newCapacity);

也就是copy数组，copy数组是会新创建数组的。

1. 删除元素

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

所以ArrayList的增删效率是相对比较低的，但是查询速度快，因为基于数组实现的。

LinkedList

LinkedList是基于双链表数据结构实现的

什么是双链表呢？

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

链表结构特点时，增删快，查询慢。

我们添加数据或者删除数据时，只要对节点里的next/pre进行指向修改即可。

所以LinkedList的特点就有了，增删快，查询慢。

List总结

List-有序，内容可以重复

数组实现的特点：查询快，增删慢

双链表实现的特点：查询慢，增删快

Set

什么是set?

它和List一样，都是继承自Collection接口

常用的有HashSet,TreeSet,LinkedSet

• HashSet

哈希表实现，无须，内容唯一。

如何确保唯一呢？通过hashCode和equals

• TreeSet

基于红黑树结构实现，唯一，有序

如何保证有序-->自然排序/比较器

如何保证唯一性？

根据比较值，返回值来决定

• LinkedHashSet

前面我们说了HashSet无序，唯一

那怎么确保唯一，又有序呢？

就有这个LinkedHashSet了

通过链表保证数据有序

通过Hash表确保数据唯一

Map

Map是单独的接口，Map则为映射，也就是Key->Value的关系

常用的Map类关系图

TreeMap

• 基于红黑树实现的Map集合
• 有序
• 线程不安全

HashMap

• 基于Hash表实现
• 线程不安全
• 无序

LinkedHashMap

• 基于链表和哈希表实现
• 有序
• 线程不安全

HashTable

• 基于哈希表实现
• 线程安全
• 无序

总结

• 是否有序，这里指的是添加的顺序

Linked ，Array，Tree有序

Hash无序

• 是否线程安全

HashTable, Vector线程安全

ArrayList，LinkedList，HashSet，TreeSet，LinkedHashSet，ArraySet线程不安全

• 效率

效率是相对来说的

查询：索引的比没索引要遍历的效率高 线程安全：线程不安全的比线程安全的效率高 增删：无索引的比有索引的增删快

• 是否可以存Null值

其实这个意义不在，只是说面试要问。

可以存null值：HashMap，HashSet，LinkHashSet，HashSet，ArrayList，LinkedList

不可以存null值：HashTable，TreeSet

• 是否去重

Hash和Tree会去重，也就是确保唯一

链表和数组实现的不会去重

如果说要有序，又去重可以结合起来实现。

除此以外，还要掌握遍历，自定义Bean的比较的两种实现方式。

有这些知识，基本上够用了。

如果想知道原理，就要学习数据结构。

以上提到的，比如说哈希表，双链表结构，红黑树，数组也是一咱数据结构，这个就不用说了，自古以来大家都知道数组的。