Java集合框架(一)

引言

我们可以将集合可以看作是一种容器,用来存储对象信息。Java为了不同类型的集合定义了大量接口,而两大基本接口为:CollectionMap。对于Collection而言,存储的是元素集合,而Map存储的是键值对/值对映射。所有集合类都位于java.util包下,但支持多线程的集合类位于java.util.concurrent包下。

我们需要注意的是,数组并不是集合,数组和集合有两个很大的区别:

  1. 数组长度固定,一旦创建便没有办法再次改变容量,而集合可以动态的改变容量。
  2. 数组元素既可以是基本类型的值,也可以是对象,而集合只能保存对象类型。

1、具体集合

java.util.Collection下的接口和继承类关系简易结构图:

img

java.util.Map下的接口和继承类关系简易结构图:

img

(我们可以通过Idea的快捷键清晰的梳理集合类之间的继承和实现关系:选中某个集合类后配合快捷键Ctrl+H便可以看见该集合类与其他类的继承和实现关系,再配合Ctrl+Shift+Alt+N 查找类效率更佳)。

2、Collection

Collection常见方法:

img

2.1 List

我们常用的ListArrayListLinkedList,而对于VectorStack并不推荐使用,因为

  1. 首先,而Vector是JDK 1.0的产物,为了保证同步在很多方法都加上了synchronized 关键字,在单线程情况下效率不高。

  2. Vector底层依然是依靠数组实现,而不是链表,也就是说Vector依然需要对数组进行扩容。不过值得注意的是相比ArrayList每次扩容至原来的1.5倍,Vector直接扩容到原来的两倍。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //Vector扩容机制
    private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
    capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //ArrayLst扩容机制
    private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
  3. Stack是继承自Vector,因此Stack 可以复用 Vector 大量方法,这使得 Stack 在设计上不严谨。

所以更多情况下,我们更推荐使用双端队列Deque接口来实现栈,Deque可以满足Vector需要的FIFO,同时,Deque既支持有容量限制的双端队列,也支持没有固定大小限制的双端队列,并且在性能上优于Vector

而对于ArrayListLinkedList,前者是底层是数组,而后者底层数据结构就是链表。这也就说明两者各有春秋:

  1. 在查询效率上,ArrayList无论是通过下标查找还是对于排序好的数据集(二分查找)进行值查找效率都明显高于需要逐个遍历的LinkedList,即使对于无序数据集的值查找,ArrayList性能依旧优于LinkedList,虽然两者查询时间复杂度都为O(n),但因为数组的连续内存,会有一部分或者全部数据一起进入到CPU缓存,而链表还需要在去内存中根据上下游标查找,,CPU缓存比内存块太多。
  2. 但是,在插入和删除的效率上,ArrayList在添加元素时需要通过数组扩容来动态改变状态,在删除时又需要移动所有后续元素才能实现,而LinkedList只需要改变指针指向便可以很简单的实现容量改变,而不需要移动数据。

2.2 Queue

队列通常以 FIFO(先进先出)的方式排序各个元素。不过优先级队列PriorityQueue和 LIFO(后进先出) 队列(或堆栈)例外,前者根据提供的比较器或元素的自然顺序对元素进行排序,后者按 LIFO的方式对元素进行排序。

2.3 Set

Set是用来存储无序元素的集合,并且元素之间的值不能相同。Java提供了HashSetLinkedHashSetTreeSet三种常用的Set实现方式。

  • 对于HashSet而言,其实就是依赖HashMap来实现,将要放入HashSet的值作为HashMap的key,而值使用一个不可变的PRESENT对象。所以HashSet的查找效率达到了O(1),但没办法有序遍历。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //HashSet部分源码
    private transient HashMap<E,Object> map;

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

    public boolean add(E e) {
    return map.put(e, PRESENT)==null;
    }
  • 对于LinkedHashSet而言,LinkedHashSet正好介于HashSetTreeSet之间,它依然继承了HashSet,但它同时维护了一个双链表来记录插入的顺序,所以基本方法的复杂度为O(1)。但是因为相比于HashSet它还需要维护一个链表,所以性能会不如HashSet

  • 对于TreeSet而言,TreeSet是采用树结构实现(称为红黑树算法),元素是按顺序进行排列,主要有add()remove()以及contains()等方法,它们都是复杂度为O(log (n))的方法;它还提供了一些处理排序的set方法,如first(), last(), headSet(), tailSet()等。

3、Map

Map存储的key-value键值对形式的对象,我们平时使用最广的必定是HashMap了,这个我们之后会着重讲,所以在这就不多赘述了。

Map常见方法

img