回顾基础-集合框架

Java 提供的集合类都在 Java.utils 包下，其中包含了很多 List, Set, Map, Queue 它们的关系如下面这张类图所示：

集合框架是一个代表并能操作集合的框架，它包括

1.接口接口通常用来形成规范

2.实现类集合接口的具体实现，是重用性很高的 *数据结构

3.算法用来根据需要对实体类中的对象进行计算，比如查找，排序

迭代器

可以看到，Java 集合主要分为两类：Collection 和 Map. 而 Collection 又继承了 Iterable< E > 接口，Iterable 接口内只有一个 iterator 方法，返回一个 Iterator 迭代器,在介绍 Iterator 之前不得不提一下被它替代的 Enumeration< E >:

Enumeration< E >接口

Enumeration 是一个很古老的迭代器，有两个方法：

hasMoreElements() //是否还有元素

nextElement() //返回下一个元素

Enumeration 的实现类会生成一系列子元素，比如 StringTokenizer；通过 Enumeration 的上述两个方法可以用来遍历它实现类的元素

Iterator接口

Iterator 是一个集合上的迭代器，用来替代 Enumeration 进行遍历、迭代。 for-each内部也是使用迭代器遍历

我们在迭代时如果增删了元素导致数量变化会进行判断期待的数量和实际数量与期待值不符合会触发迭代器的fail-fast机制抛出ConcurrentModificationException

具体使用代码:

 Iterator iterator = list.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }

缺点：只能挨个遍历

ListIterator接口

E - Element (在集合中使用，因为集合中存放的是元素)

ListIterator是继承自Iterator的接口，在Iterator基础上增加了以下功能:

1.允许我们向前、向后两个方向遍历; boolean hasPrevious(); E previous();

2.在遍历时修改 List 的元素； void set(E e); void add(E e); void remove();

3.遍历时获取迭代器当前游标所在位置。 int nextIndex(); int previousIndex(); 返回的int即游标位置

ListIterator 的具体实现？

在abstractList中的

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {//当游标不在初始位置（-1）时返回true
            return cursor != 0;
        }

        public E previous() {//游标前面一个元素
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {//游标后面的元素索引，就是游标 +1
            return cursor;
        }

        public int previousIndex() {//游标前面元素的索引，就是游标的位置
            return cursor-1;
        }

        public void set(E e) {//更新之前迭代的元素为 object
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {//在游标前面添加元素
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

Collection接口集合

继承自Iterator接口,作为集合的根接口提供了许多规范因为几乎所有集合类集都实现了 Collection接口，所以熟悉它对于清楚地理解框架是必要的。

包括

1.对集合的基础操作 int size() boolean contains(Object element) boolean add(E element)

2.一些操作整个集合的方法 boolean containsAll(Collection<?> c)

3.对数组操作的方法 Object[] toArray()

从集合获取连续的或者并行流 Stream stream()

在 JDK 8 以后，推荐使用聚合操作对一个集合进行操作

例如

myShapesCollection.stream()
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

List接口序列

List是 Collection 的子接口,一个 List 是一个元素有序的、可以重复、可以为 null 的集合

List 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。

List 中除了继承 Collection 的一些方法，还提供以下操作:

1.搜索：从 list 中查找某个对象的位置 int indexOf(Object o);

2.迭代：使用 Iterator 的拓展版迭代器 ListIterator 进行迭代操作; ListIterator listIterator();

3.范围性操作：使用 subList 方法对 list 进行任意范围的操作。 List subList(int fromIndex, int toIndex);

4.位置相关：List 和数组一样，都是从 0 开始，我们可以根据元素在 list 中的位置进行操作 E get(int index);

还有排序，替换等等

AbstractCollection 各个需求的公共部分

它实现了一些方法，也定义了几个抽象方法留给子类实现，因此它是一个抽象类。

public abstract Iterator<E> iterator();

public abstract int size();

public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }

 public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

AbstractCollection 中默认不支持添加单个元素，如果直接调用 add(E) 方法，会报错, 如果你想修改一个不可变的集合时这样设置是准从标准的

AbstractList实现类序列实现

AbstractList 继承自 AbstractCollection 抽象类，实现了 List 接口，是 ArrayList 和 AbstractSequentiaList 的父类。

它实现了 List 的一些位置相关操作(比如 get,set,add,remove)，是第一个实现随机访问方法的集合类，但不支持添加和替换。

在 AbstractCollection 抽象类中我们知道，AbstractCollection 要求子类必须实现两个方法：iterator() 和 size() AbstractList实现了iterator()方法：

public Iterator<E> iterator() {
        return new Itr();
    }
public abstract E get(int location);

abstract public E get(int index);

因此子类必须要实现 get(), size() 方法

与其他集合实现类不同，AbstractList 内部已经提供了 Iterator, ListIterator 迭代器的实现类，分别为 Itr, ListItr, 不需要我们去帮他实现。

Itr 只是简单实现了 Iterator 的 next, remove 方法。 ListItr 是 Itr 的增强版在 Itr 基础上多了向前和 set 操作。

我们还发现了两个内部类 SubList 和RandomAccessSubList

1.SubList

extends AbstractList

其实就是截取父序列的子序列其他函数实现都是用父类的实现

2.RandomAccessSubList

表明他可以支持随机访问而已，别无他尔

ArrayList 具有完备功能有序序列

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

继承自AbstractList 具有随机访问可复制可序列化集合的功能，还有以下特点

1.容量不固定，想放多少放多少

2.元素可以为 null

3.有序的（元素输出顺序与输入顺序一致）

4.数组的特性易读写o(1) 其他都是o(n)

底层实现 transient Object[] elementData; 为数组

具有三个构造函数

1.初始为空数组

2.根据指定容量，创建个对象数组

3.直接创建和指定集合一样内容的 ArrayList

刚才讲到 AbstractList子类必须要实现 get(), size() 方法因为arraylist具备增删改查的功能需要自己实现交由父类会报错

这些操作的特性是由数组决定的依靠子类具体的数据结构实现

另外，由于 ArrayList 不是同步的，所以在并发访问时，如果在迭代的同时有其他线程修改了 ArrayList, fail-fast 的迭代器 Iterator/ListIterator 会报 ConcurrentModificationException 错。

因此我们在并发环境下需要外部给 ArrayList 加个同步锁，或者直接在初始化时用 Collections.synchronizedList 方法进行包装：

List list = Collections.synchronizedList(new ArrayList(…));

AbstractSequentialList

继承自AbstractList的抽象类只支持按次序访问

子类必须实现抽象方法

public abstract ListIterator listIterator(int index);

AbstractSequentialList 把父类 AbstractList 中没有实现或者没有支持的操作都实现了，而且都是调用的 ListIterator 相关方法进行操作

LinkedList 具有完备功能有序序列

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

底层基于链表实现，定义了节点数据结构实现Deque 具有双向链队功能

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;
        }
    }
    
    transient Node<E> first;
    transient Node<E> last;

关键的内部方法：

1.链头增删

2.链尾增删

3.获取指定节点，指定节点的添加删除

因为底层由链表实现增删的操作为o(1) 其他的o(n)

linkedList 和 ArrayList 一样，不是同步容器。所以需要外部做同步操作，或者直接用 Collections.synchronizedList 方法包一下 List list = Collections.synchronizedList(new LinkedList(…));

Vector

Vector 是线程安全的 ArrayList

底层也是数组

从源码中可以发现对数组的操作都被套上了同步锁

如果没有线程安全的需求，一般推荐使用 ArrayList，而不是 Vector，因为每次都要获取锁，效率太低

Stack

继承自 Vector是线程安全的有序序列采用数组实现

头进尾出的数据结构基本操作为push pop

链栈可以用linkedlist实现

Map接口

Java 中的 Map 接口是和 Collection 接口同一等级的集合根接口，它表示一个键值对 (key-value) 的映射

Map 接口提供了三种角度来分析 Map:

1.KeySet KeySet 是一个 Map 中键（key）的集合，以 Set 的形式保存不允许重复

2.Values Values 是一个 Map 中值 (value) 的集合，以 Collection 的形式保存，因此可以重复

3.Entry Entry 是 Map 接口中的静态内部接口，表示一个键值对的映射

AbstractMap 各个需求的公共部分

使得我们以后要实现一个 Map 不用从头开始，只需要继承 AbstractMap, 然后按需求实现/重写对应方法即可。

唯一的抽象方法

public abstract Set<Entry<K,V» entrySet();

若实现可变map重写put等方法即可

内部类：

1.SimpleEntry 表示可变的键值对

2.SimpleImmutableEntry 表示不可变的键值对

Map 的实现类主要有 4 种

HashMap

HashMap 是一个采用哈希表实现的键值对集合，继承自 AbstractMap，实现了 Map 接口

HashMap 采用拉链法进行解决哈希碰撞因此 HashMap 的底层实现是数组+链表

具有以下特点：

1.实现了 Map 全部的方法

2.key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法

3.元素是无序的，而且顺序会不定时改变

4.插入、获取的时间复杂度基本是 O(1)

5.两个关键因子：初始容量、加载因子（决定了 HashMap 中的元素占有多少比例时扩容）

默认初始容量：16 默认加载因子的大小：0.75

因为是链表+数组的组合

数据结构为 transient Node<K,V>[] table;

当 HashMap 中有大量的元素都存放到同一个桶中时这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

线程安全的map Map m = Collections.synchronizedMap(new HashMap(…));

Hashtable

Hashtable 不允许同步和null值其他与hashmap一样

LinkedHashMap

继承自hashmap

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

链表与链表的组合

TreeMap

是一个有序的key-value集合，它是通过红黑树实现的。

实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合

创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

TreeMap是非同步的

Reference

集合框架

源码解析

迭代器

Enumeration< E >接口

Iterator接口

ListIterator接口

ListIterator 的具体实现？

Collection接口集合

List接口序列

AbstractCollection 各个需求的公共部分

AbstractList实现类序列实现

ArrayList 具有完备功能有序序列

AbstractSequentialList

LinkedList 具有完备功能有序序列

Vector

Stack

Map接口

AbstractMap 各个需求的公共部分

HashMap

Hashtable

LinkedHashMap

TreeMap

Reference

CATALOG

FEATURED TAGS

FRIENDS

迭代器

Enumeration< E >接口

Iterator接口

ListIterator接口

ListIterator 的具体实现？

Collection接口 集合

List接口 序列

AbstractCollection 各个需求的公共部分

AbstractList实现类 序列实现

ArrayList 具有完备功能有序序列

AbstractSequentialList

LinkedList 具有完备功能有序序列

Vector

Stack

Map接口

AbstractMap 各个需求的公共部分

HashMap

Hashtable

LinkedHashMap

TreeMap

Reference

CATALOG

FEATURED TAGS

FRIENDS

Collection接口集合

List接口序列

AbstractList实现类序列实现