Java快速入门-04-Java.util包简单总结

你的名字 2022-05-07 03:54 132阅读 0赞

学Java的程序员，lang包和util包最好是要过一遍的。  
建议大家都序下载一个离线版开发文档，查阅非常方便，我给大家提供一个中文版 jdk1.8 离线文档，查看：[JAVA - JDK 1.8 API 帮助文档-中文版][JAVA - JDK 1.8 API _-]

# 1. **util包的框架** #

常用的集合类主要实现两个“super接口”而来：`Collection`和`Map`。

### 1.1 **`Collection`有两个子接口：`List`和`Set`** ###

![这里写图片描述][SouthEast]

`List`特点是**元素有序，且可重复**。实现的常用集合类有`ArrayList`、`LinkedList`，和`Vector`（线程安全）。

`Set`特点是**元素无序，不可重复**。实现的常用集合类有`HashSet`，`LinkedHashSet`，`TreeSet`（可排序）

### 1.2 **`Map`是key、value键值对的集合** ###

![这里写图片描述][SouthEast 1]

特点是**key值无序不可重复，value值可重复**（这样表述其实不太准确，因为实际上key和value是绑定在一起的）。常用的有`HashMap`，`HashTable`（线程安全），`TreeMap`（可排序）。

### 1.3 **其余重要接口和类** ###

上面是util包中的集合框架，一般Java教材里面都会讲到。但我们深入研究一下，会发现还有其余几个重要的内容：

*  **Iterator：迭代接口**  
    集合类实现该接口后便具有了迭代功能。最简单的迭代实现是`ArrayList`，迭代过程其实就是数组的迭代。`LinkedList`、`LinkedHashSet`和`LinkedHashMap`迭代过程就是链表的迭代。这两者的迭代效率都很高，迭代时间与容器里的元素数目成正比。但`HashSet`、`HashMap`迭代效率就略低了，因为采用了哈希表，所以元素是散列在数组中的，迭代时必须读完整个数组，迭代时间与容器的容量成正比。
 *  **Comparator：比较接口**  
    实现该接口后，集合内元素便可比较通过`compare()`方法实现元素排序
 *  **AbstractXXX：骨架类**  
    所谓骨架类，其实就是不同集合的核心代码实现，让继承这个抽象类的子类少干点活。例如`AbstarctList`代表“随机访问”集合（底层数组实现）的骨干代码实现。`AbstractSequentialList`代表“连续访问”（底层链表实现）集合的骨干代码实现。
 *  **Collections、Arrays**  
    集合工具类和数组工具类。Java中的工具类好像都喜欢在对应的接口或类名称后，加`S`来表示其工具类。

接下来给一张比较完整的util包框架图：

![这里写图片描述][SouthEast 2]

# 2. 常用集合类原理 #

### 2.1 ArrayList ###

`ArrayList`的实现最简单，采用的顺序表，底层就是一个`Object`数组，初始容量为10，每当元素要超过容量时，重新创建一个更大的数组，并把原数据拷到新数组中来。

### 2.2 LinkedList ###

`LinkedList`采用双向链表。集合中的每一个元素都会有两个成员变量`prev`和`next`，分别指向它的前一元素和后一元素。

`ArrayList`和`LinkedList`的区别这里就不详细讨论了，其实就是顺序表和链表两种数据结构的区别。之前写的博文中已经提到（包括`ArrayList`和`LinkedList`的详细实现）：  
[数据结构基础（一）线性表][Link 1]

### 2.3 Vector ###

`Vector`底层实现和`ArrayList`类似，区别在于在许多方法上加了`synchronized`关键字，来实现了多线程安全。但代价是性能的降低。由于加锁的是整个集合，所以并发情况下进行迭代会锁住很长时间。

### 2.4 HashMap ###

`HashMap`采用的是哈希表结构，用链表法来解决hash冲突。这里不详细讨论，之前的文章写过：  
[HashMap原理解析][HashMap]

### 2.5 HashTable ###

`HashTable`的底层实现和`HashMap`类似，区别也是在许多方法上加了`synchronized`关键字，来实现了多线程安全。

### 2.6 LinkedHashMap ###

在`HashMap`的基础上加了双链表，该集合中的每个元素也都保留了前一个元素和后一个元素的“指针”。这样便可以按照插入顺序来读取集合元素。也可设置为按照访问顺序来读取集合元素。  
由于要维护额外的双链表，`LinkedHashMap`增删操作会比`HashMap`慢，但迭代时会比`HashMap`快。

### 2.7 TreeMap ###

采用了红黑树数据结构，从而实现了有序集合。这个比较复杂，以后单独开出一篇来讨论，此处略。

### 2.8 HashSet、LinkedHashSet、TreeSet ###

Set和Map有千丝万缕的联系呀。例如`HashSet`底层实现其实就是一个固定value的`HashMap`。LinkedHashSet就是一个value固定的`LinkedHashMap`，`TreeSet`就是一个value固定的`TreeMap`。

# 3. 集合的并发 #

### 3.1 并发类的选择 ###

讲到并发的集合，一般都想到util包中的两个类：`HashTable`和`Vector`。然而实际使用情况中，并不推荐使用这两个类。

首先，`HashTable`和`Vector`是从JDK1.0便存在的“古老”类，当时`Collection`、`Map`接口都还没。这样导致的问题是，当后来`HashTable`和`Vector`实现`Map`，`Collection`接口时，出现了许多无用而重复的方法。例如`Vector`原本有一个`addElement()`的方法，当实现了`Collection`接口后，又出现了一个`add()`方法。而实际上，这两个方法一模一样。

替代的这两个并发类的常见方法是`Collections.synchronizedXXX(…)`，这个方法可以把`ArrayList`，`HashMap`等集合变为线程安全的集合类。

那么，`Vector`和`Collections.synchronizedXXX(…)`的底层实现有什么区别呢？

我们来看看两者的`add()`方法实现：

//Vector
        public synchronized boolean add(E e) {
            modCount++;
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = e;
            return true;
        }
    
        //Collections.SynchronizedList
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12

可以看出， 两者实现多线程的方式都是对集合的方法加锁，区别在于，`Vector`是对方法加锁，锁的是本对象，而`Collections.synchronizedXXX(…)`是对一个变量加锁。区别并不大。

那么，既然`Collections.synchronizedXXX(…)`比较好，用它创建出线程安全的集合类是不是就一劳永逸的满足我们所有的需求了呢？很不幸，不完全是。

`Collections.synchronizedXXX(…)`和`HashTable`、`Vector`在高并发时都有着很大的性能缺陷。因为它们的增、删、取都会锁住整个集合。想一想，一个线程在迭代十万个元素的Vector，其余线程对集合的操作时不时就阻塞了，受到了多大的影响啊。

为了解决这两种方法在高并发下的性能的低下。我们查找一下Java的API，发现在`java.util.concurrent`里面有许多针对高并发设计的类，例如：`CopyOnWriteArrayList`和`ConcurrentHashMap`。

`ConcurrentHashMap`的优化原理在于，采用了`Segment`的机制：

![这里写图片描述][SouthEast 3]

可以看成，`ConcurrentHashMap`底层每一个Segment都是一个`HashMap`,这样增删取时只需要锁住一段的`Segment`，而不是整个集合。从而优化了高并发下的性能。

`CopyOnWriteArrayList`主要是对高并发下的读、迭代做优化。实现原理在于每次`add`,`remove`操作都是重新创建一个新的数组，等操作结束再把引用指向新的数组。`add`,`remove`都是加了锁的，而`get`方法没有加锁，因为每次迭代时都是在旧的数组上迭代。所以`CopyOnWriteArrayList`适用于读多写少的并发场景。

### 3.2 迭代`fail-fast`机制 ###

之前写的博文：[Java迭代foreach原理解析（java.util.ConcurrentModificationException的原因）][Java_foreach_java.util.ConcurrentModificationException]

[JAVA - JDK 1.8 API _-]: https://blog.csdn.net/qq_40147863/article/details/83051268
[SouthEast]: /images/20220506/8fafe42204674ef19ae5b69f7dddc5d8.png
[SouthEast 1]: /images/20220506/ba70118002ec4510b5c59269a7aa444f.png
[SouthEast 2]: /images/20220506/dcc859cfdac34669b061561a218a0fef.png
[Link 1]: http://blog.csdn.net/z55887/article/details/50365338
[HashMap]: http://blog.csdn.net/z55887/article/details/50596588
[SouthEast 3]: /images/20220506/8f73125e9efd41b6849590cc3a84c487.png
[Java_foreach_java.util.ConcurrentModificationException]: http://blog.csdn.net/z55887/article/details/50676548