Java集合

概念

Java 是面向对象的语言，而面向对象语言对事物的描述是通过对象体现的，为了方便对多个对象进行操作，我们必须把多个对象进行存储。
已有的容器类型有：数组和 StringBuffer。但是，StringBuffer 的结果是一个字符串，不一定满足我们的要求，所以我们只能选择数组，这就是对象数组。而对象数组又不能适应变化的需求，因为数组的长度是固定的，此时，为了适应变化的需求，Java 就提供了集合类。

来自百度百科：集合框架（Java Collections Framework，JCF）是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。
合理地利用 Java 集合框架不但可以提高程序的运行速度和质量，而且还可以减少设计新的 API（Application Programming Interface，应用程序接口），设计者和实现者不需要在每次创建一种依赖于集合内容的 API 时重新设计，只需使用标准集合框架的接口即可。

与现代数据结构常见的类库一样，Java 集合类库将接口(interface)与实现(implementation)分离。

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

常用容器(图片来自Java 208 道面试题：第二模块答案)

数组和集合的区别

长度区别
数组的长度固定；集合长度可变。
内容区别
数组存储的是同一种类型的元素；集合可以存储不同类型的元素。
元素的数据类型
数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用类型。

Collection 接口

在 Java 类库中，集合类的基本接口是 Collection 接口。这个接口有两个基本方法：

public interface Collection<E>{

    boolean add(E element);
    Iterator<E> iterator();
    ...
}

add(): 用于向集合中添加元素，如果添加元素改变了集合就返回 true，集合没有变化就返回 false。
iterator(): 用于返回一个实现了 Iterator 接口的对象。可以使用这个迭代器对象依次访问集合中的元素。

迭代器

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

源码如下：

public interface Iterator<E> {

    E next();
    boolean hasNext();
    default void remove(){
      throw new UnsupportedOperationException("remove");
    };
    default void forEachRemaining(Consumer<? super E> action){
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    };
}

default:
Java 8 新增了接口的默认方法。
简单说，默认方法就是接口可以有实现方法，而且不需要实现类去实现其方法。
我们只需在方法名前面加个 default 关键字即可实现默认方法。

next(): 返回迭代器的下一个元素，并且更新迭代器的状态。
hasNext(): 检测集合中是否还有元素。
remove(): 将迭代器返回的元素删除。
forEachRemaining(): jdk1.8 新增默认方法。简单来说，就是对集合中剩余的元素进行操作，直到元素完毕或者抛出异常。

通过反复调用 next()方法，可以逐个访问集合中的每个元素，但是，如果到达了集合的末尾，next()方法将抛出NoSuchElementException。因此，需要在调用 next 之前调用 hasNext()方法，如果迭代器还有多个可访问对象，这个方法就返回 true。

next()方法说明(来自《Java 核心技术》)
Java 集合类库中的迭代器与其他类库中的迭代器在概念上有着重要的区别。在传统的集合类库中，例如，C++的标准模版库，迭代器是根据数组索引建模的。
如果给定这样一个迭代器，就可以查看指定位置上的元素，就像知道数组索引 i 就可以查看数组元素 a[i]一样。
不需要查找元素，就可以将迭代器向前移动一个位置。这与不需要执行查找操作就可以通过 i++将数组索引向前移动相同。
但是，Java 迭代器并不是这样操作的。查找操作与位置变更是紧密相连的。查找一个元素的唯一方法是调用 next. 而在执行查找操作的同时，迭代器的位置随之向前移动。
因此，应该将 Java 迭代器认为是位于两个元素之间。当调用 next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

用for each循环可以很简单的完成查看集合中每个元素的过程：

Collection c =  ... ;
for(String element : c){
  ...
}

也可以使用forEach() 方法遍历。forEach为 Iterable 接口的方法，源码如下：

public interface Iterable<T> {
    Iterator<T> iterator();
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
            for (T t : this) {
                action.accept(t);
            }
    }
    // Spilterator 可以让我们在多线程下遍历集合，基本思想就是把一个集合分割成多个小集合由多个线程遍历
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

例：list.forEach(System.out::println)可以输出 list 中的每个值。

Collection 接口扩展了 Iterable 接口。因此，对于标准类库中的任何集合都可以使用forEach循环。

Java SE 8 中，可以调用 forEachRemaining()方法并提供一个 lambda 表达式，他将对剩余所有元素调用这个表达式，直到没有元素位置。

示例代码参考forEachRemaining()方法的用法

remove()方法会删除上次调用 next()方法返回的元素。对 next()方法和 remove()方法的调用具有依赖性，如果调用 remove()之前没有调用 next()是不合法的，会抛出IllegalStateException异常。

示例：

public static void main(String[] args) {
        // 创建元素类型为Integer的集合
        Collection<Integer> collection = new ArrayList<>();
        // 添加数据
        for (int i = 0; i < 5; i++) {
            collection.add(i);
        }
        // 获取该集合的迭代器
        Iterator<Integer> it = collection.iterator();
        // 删除集合中的第一个元素(先越过第一个元素  ,再删除)
        it.next();
        it.remove();
        // 连续删除两个元素(类似于删除第一个元素,删除第二个元素也需要先越过)
        it.next();
        it.remove();
        // for each输出集合剩余元素
        for (Integer i : collection) {
            System.out.print(i+" ");
        }
        // 输出结果：2 3 4
    }

集合常用方法

// 用于将元素e放入当前集合中。
boolean add(E e)
// 用于将参数指定集合中的所有元素放入当前集合中。
boolean addAll(Collection<? extends E> c)
// 用于从当前集合中删除参数指定的元素。
boolean remove(Object o)
// 用于从当前集合中删除参数指定集合中的所有元素
boolean removeAll(Collection<?> c)
// 用于将当前集合中的所有元素移除。
void clear()
// 用于判断当前集合中是否包含参数指定的单个元素。
boolean contains(Object o)
// 用于判断当前集合中是否包含参数指定集合中的所有元素。
boolean containsAll(Collection<?> c)
// 用于判断当前集合是否为空。
boolean isEmpty()
// 用于返回当前集合中元素的个数。
int size()
// 用于获取当前集合和参数集合的交集并保留到当前集合中。
// 若当前集合中的内容发生了更改则返回true，否则返回false。
boolean retainAll(Collection<?> c)

具体集合

Collection 接口继承树,来自Java：集合，Collection 接口框架图

List

列表特有且常用方法:

public interface List<E> extends Collection<E> {
    // 在指定位置添加元素
    void add(int index, E element);
    // 用于将集合c中所有元素插入到当前集合中index指向的位置。
    boolean addAll(int index, Collection<? extends E> c)
    // 获取指定位置的元素
    E get(int index);
    // 用于将index位置的元素从当前集合移除。
    // 返回被删除的元素值，下标不合理时会产生下标越界异常。
    E remove(int index)
    // 使用element元素替换当前集合中index位置的元素，返回被替换的元素。
    E set(int index, E element)
    // 用于返回当前集合中从fromIndex(包含)到toIndex(不包含)之间的部分视图。
    // 返回的集合和当前集合共用同一块内存区域。
    List<E> subList(int fromIndex, int toIndex)
    // List集合特有迭代器
    ListIterator<E> listIterator();
}

listIterator

此部分内容来自Java 实用方法整理（五）——集合类常用方法

ListIterator listIterator()：List 集合特有的迭代器。该迭代器继承了 Iterator 迭代器，所以，就可以直接使用 hasNext()和 next()方法。

特有功能：

Object previous()：获取上一个元素；
boolean hasPrevious()：判断是否有元素。

注意：ListIterator 可以实现逆向遍历，但是必须先正向遍历，才能逆向遍历，所以一般无意义，不使用该方法进行集合的迭代。

Iterator 和 ListIterator 区别

Iterator 可用来遍历 Set 和 List 集合，但是 ListIterator 只能用来遍历 List。
Iterator 对集合只能是前向遍历，ListIterator 既可以前向也可以后向。
ListIterator 实现了 Iterator 接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

应用示例:

/*
 * 需求：有如下集合，请判断该集合里面是否包含“java”这个元素，如果有，就添加一个“love”元素
 */

List list = new ArrayList();
list.add("hello");
list.add("java");
list.add("world");

/*
 * 1，展示一个会出错的代码
 * 出错提示：ConcurrentModificationException：当方法检测到对象的并发修改，但不允许这种修改时，抛出此异常。
 * 也就是说：迭代器遍历元素的时候，通过集合是不能修改元素的（不能调用集合方法）
 */
Iterator it = list.iterator();
while(it.hasNext()){
    String s = (String)it.next();
    if(s.equals("java")){
      list.add("love");
    }
}

System.out.println(list);

/*
 * 2，当遇到以上错误时，给出两种解决办法
 * 首先展示第一种解决办法：使用ListIterator的add()方法
 */

ListIterator lit = list.listItertor();
while(lit.hasNext()){
    String s = (String)lit.next();
    if(s.equals("java")){
      lit.add("love");//注意：此处是利用迭代器进行添加元素，刚添加的元素处于刚才迭代的元素的后面。
    }
}

/*
 * 3，给出另一种解决办法：
 * 使用普通循环方法，即使用get()和size()的方法
 */
for(int i = 0;i<list.size();i++){
    String s = (String)list.get(i);
    if(s.equals("java")){
        list.add("love");//注意：此处是将新的元素添加到了集合的最后
    }
}

List 子类特点

ArrayList：底层数据结构是数组，查询快，增删慢；线程不安全，效率高。
Vector：底层数据结构是数组，查询快，增删慢；线程安全，效率低。现在已不常用。
LinkedList：底层数据结构是链表，查询慢，增删快。线程不安全，效率高。

LinkedList

如继承树中所示,LinkedList 既可以实现 Queue 接口,也可以实现 List 接口。只不过, Queue 接口窄化了对 LinkedList 的方法的访问权限（即在方法中的参数类型如果是 Queue 时，就完全只能访问 Queue 接口所定义的方法了，而不能直接访问 LinkedList 的非 Queue 的方法），以使得只有恰当的方法才可以使用。

LinkedList 常用方法

添加
- public void addFirst(Object e)
- public void addLast(Object e) //和 add()功能一样，所以不常用此方法
获取
- puclic Object getFirst()
- public Object getLast()
删除
- public Object removeFirst()
- public Object removeLast()

Set

Set 接口的特点是不能包含重复的元素。对 Set 中任意的两个元素 element1 和 element2 都有 elementl.equals（element2）= false。另外，Set 最多有一个 null 元素。此接口模仿了数学上的集合概念。

AbstractSet 是一个实现 Set 接口的抽象类，Set 接口有三个具体实现类，分别是散列集 HashSet、链式散列集 LinkedHashSet 和树形集 TreeSet。
SortedSet 是个接口，它里面的（只有 TreeSet 这一个实现可用）中的元素一定是有序的。

Set 常用方法参考 Collection 接口即可。

HashSet

散列集 HashSet 是一个用于实现 Set 接口的具体类，可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。

查看散列集 HashSet 的源码实现可以看到它内部是使用一个 HashMap 来存放元素的，因为 HashSet 的元素就是其内部 HashMap 的键集合，所以 HashSet 可以做到元素不重复。

示例:

Set<String> set = new HashSet<>();
set.add("11111");
set.add("22222");
set.add("33333");
set.add("44444");
set.add("22222");
System.out.println(set.size()); // 4

for (String e : set) {
    System.out.println(e);
}
// 44444
// 33333
// 11111
// 22222

可以看到只输出 4 个结果,并且无序。

HashSet 总结

实现原理（面试）
1. 底层数据结构是哈希表。(无序,唯一)
2. HashSet 的值存放于 HashMap 的 key 上。
3. HashMap 的 value 统一为 PRESENT。
依赖 hashCode()和 equals()(hashcode 相等不代表 equals 也相等)保证数据唯一性(所以加入的元素要注意 hashCode()方法的实现)
不能保证元素的排列顺序
HashSet 不是同步的，多线程访问同一步 HashSet 对象时，需要手工同步。
集合元素值可以是 null

LinkedHashSet

LinkedHashSet 是继承自 HashSet 的，支持对规则集内的元素排序。HashSet 中的元素是没有被排序的，而 LinkedHashSet 中的元素可以按照它们插入规则集的顺序提取。

LinkedHashSet 总结

底层数据结构是链表和哈希表。(FIFO 插入有序,唯一)
1. 由链表保证元素有序
2. 由哈希表保证元素唯一
对集合迭代时，按增加顺序返回元素。
性能略低于 HashSet，因为需要维护元素的插入顺序。但迭代访问元素时会有好性能，因为它采用链表维护内部顺序。

TreeSet

TreeSet 类是 SortedSet 接口的实现类。因为需要排序，所以性能肯定差于 HashSet。底层数据结构是红黑树。(唯一，有序),这样就能从 Set 里面提取一个有序序列了

TreeSet 总结

新增方法:
- first()：返回第一个元素
- last()：返回最后一个元素
- lower(Object o)：返回指定元素之前的元素
- higher(Obect o)：返回指定元素之后的元素
- subSet(fromElement, toElement)：返回子集合
如何保证元素排序的呢?
- 自然排序
- 比较器排序
如何保证元素唯一性的呢?
根据比较的返回值是否是 0 来决定

Queue

Queue 接口是 Collection 接口的子接口，与 List 接口是平级关系。
该接口主要描述具有先进先出特性的数据结构，简称为 FIFO(first in first out)，叫队列。
该接口的主要实现类是 LinkedList 类，因此该类在增删方面有一定的优势。

Queue 接口并未定义阻塞队列的方法，而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

常用方法

// 将元素加入到队尾
boolean add(E e);
// 将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。推荐使用此方法取代add
boolean offer(E e);
// 移除队列头部的元素，队列为空时抛出异常
E remove();
// 移除队列头部的元素，队列为空时返回null。推荐使用此方法取代remove
E poll();
// 获取但是不移除此队列的头，
E element();
// 获取队列头部元素却不删除元素，队列为空返回null。
E peek();

PriorityQueue

PriorityQueue 保存队列元素的顺序并不是按照加入队列的顺序，而是按队列元素的大小重新排序。当调用 peek()或者是 poll()方法时，返回的是队列中最小的元素。当然你可以与 TreeSet 一样，可以自定义排序。自定义排序的一个示范：

@Test
public void testPriorityQueue() {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(20, new Comparator<Integer>() {
        public int compare(Integer i, Integer j) {
            // 对数字进行奇偶分类，然后比较返回；偶数有较低的返回值（对2取余数然后相减），奇数直接相减。
            int result = i % 2 - j % 2;
            if (result == 0)
                result = i - j;
            return result;
        }
    });

    // 倒序插入测试数据
    for (int i = 0; i < 20; i++) {
        pq.offer(20 - i);
    }

    // 打印结果，偶数因为有较低的值，所以排在前面
    for (int i = 0; i < 20; i++) {
        System.out.println(pq.poll());
    }
}

Deque 子接口与 ArrayDeque 类

Deque 代表一个双端队列，可以当作一个双端队列使用，也可以当作“栈”来使用，因为它包含出栈 pop()与入栈 push()方法。

ArrayDeque 类为 Deque 的实现类，数组方式实现。

常用方法：

// 元素增加至队列开头
addFirst(E e);
// 元素增加至队列末尾
addLast(E e)；
// 获取并删除队列第一个元素，队列为空返回null
poolFirst()；
// 获取并删除队列最后一个元素，队列为空返回null
poolLast()；
// “栈”方法，出栈，相当于removeFirst()
pop()；
// “栈”方法，入栈，相当于addFirst()
push(E e)；
// 获取并删除队列第一个元素
removeFirst()；
// 获取并删除队列最后一个元素
removeLast()；

Map 接口

来自Java 集合中 List,Set 以及 Map 等集合体系详解(史上最全)

java.util.Map<K,V>接口主要用于存放一对一对元素，分别叫做 key(键)和 value(值)。
类型参数：
K - 此映射所维护的键的类型
V - 映射值的类型
该集合中 key 是不允许重复的，而且每个 key 对应唯一的 value。

Map 接口有三个比较重要的实现类，分别是 HashMap、TreeMap 和 HashTable。
HashMap 对键进行散列，TreeMap 用将的整体顺序对元素进行排序，并将其组织成搜索值。
散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

TreeMap 是有序的，HashMap 和 HashTable 是无序的。
Hashtable 的方法是同步的，HashMap 的方法不是同步的。这是两者最主要的区别。
其他区别：
- Hashtable 是线程安全的，HashMap 不是线程安全的。
- HashMap 效率较高，Hashtable 效率较低。
  如果对同步性或与遗留代码的兼容性没有任何要求，建议使用 HashMap。查看 Hashtable 的源代码就可以发现，除构造函数外，Hashtable 的所有 public 方法声明中都有 synchronized 关键字，而 HashMap 的源码中则没有。
- Hashtable 不允许 null 值，HashMap 允许 null 值（key 和 value 都允许）
- 父类不同：Hashtable 的父类是 Dictionary，HashMap 的父类是 AbstractMap

Map 常用方法

// 用于将参数指定的key和value组成一对放入当前集合中。
// 增加key和value时则返回null，修改key和value时则返回key之前对应的value。
V put(K key, V value)
// 用于从当前集合删除key关联的键值对。
// 若key不存在则返回null，否则返回key对应的value。
V remove(Object key)
// 用于判断当前集合中是否存在参数指定的key。
boolean containsKey(Object key)
// 用于判断当前集合中是否包含参数指定的value。
boolean containsValue(Object value)
// 用于根据参数指定的key来返回对应的value。
V get(Object key)
// 用于返回当前集合中包含映射关系的Set视图，通俗来说，就是把Map转换为Set。
Set<Map.Entry<K,V>> entrySet()
// 用于返回当前集合中包含key的Set视图。
Set<K> keySet()
// 接口代表键值对，提供的方法有：
java.util.Map.Entry<K,V>
      // 用于获取当前键值对中key的数值并返回。
      K getKey()
      // 用于获取当前键值对中value的数值并返回。
      V getValue()

HashMap

HashMap 概述： HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap 的数据结构：在 java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

当我们往 Hashmap 中 put 元素时,首先根据 key 的 hashcode 重新计算 hash 值,根据 hash 值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。

需要注意 Jdk 1.8 中对 HashMap 的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的 O(n)到 O(logn)

图片来自Java - 集合框架完全解析

HashMap 容量的初始化

1. 为什么要指定 HashMap 的容量？

HashMap 的默认容量为 16，如果不指定 HashMap 的容量，要插入 768 个元素，第一次容量为 16，需要持续扩容多次到 1024，才能保存 1024*0.75=768 个元素。
所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。

2. HashMap 指定容量初始化后，底层 Hash 数组已经被分配内存了吗？

默认情况下，当我们设置 HashMap 的初始化容量时，实际上 HashMap 会采用第一个大于该数值的 2 的幂作为初始化容量。比如指定容量为 1000，则初始化容量为 1024。
但是指定 HashMap 的初始化容量后，底层的数组并没有被初始化，依然为 null。当第一次 put 元素时，才会初始化底层 Hash 数组

第一次调用 put 方法插入 key-value，会调用 resize 方法，由于指定了 HashMap 的容量，那么这里会将底层的 Hash 数组 Node<K,V>[] table 初始化容量为上面所说的 2 的整数次幂;

3. HashMap 中初始容量的合理值是多少？

在阿里巴巴 Java 开发手册中：initialCapacity = （需要存储的元素个数 / 负载因子）+ 1，负载因子（loadFacotr）默认为 0.75。

当我们使用 HashMap(int initialCapacity)来初始化容量的时候，jdk 会默认帮我们计算一个相对合理的值当做初始容量。但是这个值并没有参考 loadFactor 的值。
也就是说，如果我们设置的默认值是 7，经过 Jdk 处理之后，会被设置成 8，但是，这个 HashMap 在元素个数达到 8*0.75 = 6 的时候就会进行一次扩容，这明显是我们不希望见到的。

如果我们通过 expectedSize / 0.75F + 1.0F 计算，7 / 0.75 + 1 = 10 ,10 经过 Jdk 处理之后，会被设置成 16，这就大大的减少了扩容的几率。

当 HashMap 内部维护的哈希表的容量达到 75%时（默认情况下），会触发 rehash，而 rehash 的过程是比较耗费时间的。所以初始化容量要设置成 expectedSize/0.75 + 1 的话，可以有效的减少冲突也可以减小误差。

所以，我可以认为，当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

LinkedHashMap

LinkedHashMap 继承自 HashMap，它主要是用链表实现来扩展 HashMap 类，HashMap 中条目是没有顺序的，但是在 LinkedHashMap 中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。

TreeMap

TreeMap 基于红黑树数据结构的实现，键值可以使用 Comparable 或 Comparator 接口来排序。TreeMap 继承自 AbstractMap，同时实现了接口 NavigableMap，而接口 NavigableMap 则继承自 SortedMap。SortedMap 是 Map 的子接口，使用它可以确保图中的条目是排好序的。

在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用 HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用 LinkedHashMap，如果需要使图按照键值排序，就使用 TreeMap。

参考

HashMap和Hashtable区别