Java集合框架

相比于C++ STL来说，Java的集合架构给我的感觉是更有条理。连源码看起来都很好看（还没到深入源码的地步），感觉自己的编码风格都要受到影响了 😦

先粗略过一遍吧，底层的结构等读完核心技术再来补充。

一、概述

与C++的STL的6大组件理念类似，Java的集合框架都包含如下内容：

• 接口：如Collection、List、Set、Map等
• 实现类：实现了特定接口的类。如ArrayList、LinkedList、HashSet、HaseMap等。
• 算法：主要由Collections工具类实现。类似STL种头文件alghorithm的作用。

Java中有两大类接口Collection，Map。接口之间的关系及其实现类的类图如下。

二、Collection接口

Collection接口没有直接实现的子类。但其子接口List或者Set有直接实现类。

Collection接口规定了一些简单的方法，并没有指明具体的存储结构，因此不提供取元素等方法(如get()、indexOf())

常用方法

• add remove contains size isEmpty clear

• addAll containsAll removeAll

  *All方法的参数必须是实现了Collection接口的对象。

遍历

Collection接口继承自Iterable接口，所以可以通过迭代器Iterator遍历。

迭代器有hasNext()与next()方法

顾名思义

不过要注意的是，调用next()前记得调用hasNext()方法，否则可能会抛出NoSuchElementException异常

通过调用Collection接口的iterator()方法，获得集合迭代器。

public static void main(String[] args) {
    Collection<Integer> list = new LinkedList<>();
    list.add(3);
    list.add(4);
    list.add(1);
    list.add(5);

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

当然也可以通过增强for循环去遍历。

三、List接口

List接口的实现类有一些特点：

• 集合中元素有序（添加顺序与取出顺序一致）。
• 可以存在重复元素。
• 每个元素都有对应的顺序索引，可以通过get方法返回

常用方法

除Collection提供的方法外(有一些重载，如add()，由于指明了具体的存储结构，因此可以在指定index处add了)，还有一些新增方法：

• get()

• indexOf()、lastIndexOf()

  c++没有欸

遍历

• 增强for
• 由于List是Collection的子接口，因此可以使用Iterator遍历
• 通过索引

三个主要的实现类

ArrayList

• 基于数组实现

• 存储元素的数组为

  transient Object[] elementData;

  transient修饰词以后再看吧

• 线程不安全

• 扩容机制与STL的Vector有一点不同，ArrayList每次扩容为原容量1.5倍

Vector

• 基于数组实现
• 线程安全，方法使用synchronized修饰
• 扩容机制与STL的Vector一致，2倍扩容。

LinkedList

• 底层实现了双向链表和双端队列的特点
• 线程不安全

这里和数据结构课上手撕的基于数组的顺序表与基于链式结构的顺序表类似，分别对应着ArrayList与LinkedList类。

可以根据插入/删除操作的频繁程度来决定使用哪一个类作为List接口的实现类。

Vector与ArrayList区别在于前者是线程安全的，因此必然会损失一定的时间效率。算法题目中几乎不用Vector类。

四、Set接口

Set接口的实现类的特点：

• 元素无序，不能通过索引访问

• 不允许有重复元素

  因此对于自定义类型，需要重写hashCode与equal方法

  这点很重要！

• 可以通过迭代器遍历

常用方法

• Set接口是Collection接口的子接口。

实现类：

HashSet

有趣的是，若我们执行下面的语句构造一个HashSet对象，

Set<String> s = new HashSet<>();

在HashSet的构造方法源码中，实际上构造了一个HashMap。

public HashSet() {
    map = new HashMap<>();
}

• 可以通过add方法的返回值判断要添加的元素是否已经存在于HashSet中了
• 与C++ unordered_set类似

TreeSet

• 与C++ set类似
• 有序。

LinkedHashSet

• 是HashSet的子类
• 底层是一个LinkedHashMap，额外维护了一个数组与双向链表
• 从而使元素看起来是以插入顺序保存的。

五、Map接口

实现了Map接口的实现类均维护了键值对的映射关系。

HashMap

• 线程不安全
• 底层基于红黑树

TreeMap

HashTable

• 线程安全