> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/programming-language/java/ji-he.md).

# 集合

数据结构分为：

1. 逻辑结构：线性表（数组、链表）、图、树、栈、队列
2. 物理结构：顺序结构、链式结构

以线性表为例，其顺序结构表现就是数组，而链式结构表现就是链表。

顺序结构特点：

1. 寻址快，通过下标
2. 但是删除、增加元素效率低

链式结构的特点：

1. 删除、增加元素快
2. 寻址慢
3. 数组长度是固定的，为了保存不定量的数据(Collection)，以及具有关系映射的数据(Map)。

因为数组拥有下面的缺点，无法满足所有的场景，故引出集合：

1. 数组元素长度固定
2. 添加、删除元素效率很低
3. 数组只能存放同一类型的数据
4. 数组不能完成不可重复元素的功能

## Java 集合的继承结构

在Java中，集合API又分为两大体系： `Collection` 和 `Map`

![容器](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-36a9d92310e6ab2f2b1c7debcd358a49d118796c%2F%E5%AE%B9%E5%99%A8.jpg?alt=media)

## Collection

![image-20220303161246610](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-a487943b167e1deb957a3042eeed684bf3cab539%2Fimage-20220303161246610.png?alt=media)

### Queue

![image-20220303161044916](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-1228fbcd05bcb543329760a0692bb0fc78f57a29%2Fimage-20220303161044916.png?alt=media)

全是一些与队列相关的方法：

| 操作 | 抛出异常        | 返回特殊值      |
| -- | ----------- | ---------- |
| 插入 | `add(e)`    | `offer(e)` |
| 删除 | `remove()`  | `poll()`   |
| 检查 | `element()` | `peek()`   |

### List

![image-20220303161056999](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-0e513abeb2cbacc05905ef7f3439327a0d656523%2Fimage-20220303161056999.png?alt=media)

List 主要提供了根据**索引**操作、查看元素的接口方法。

### Set

![image-20220303161153477](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-5b8275807fb6b852308856522f70f78a5786a492%2Fimage-20220303161153477.png?alt=media)

Set没有特有的方法。不同于List，他是无序（无序不是随机，是按照一种特殊的顺序）存储的。

## Map

Map（也称作字典，关联数组）通常用于具有映射关系的数据，所以在Map中存放着两组值，一组存放key，一组存放value，key不允许重复，key和value是一对一的关系。

Set则是由Map包装实现的，Set本质上是一个value相同的Map的key集合。

![image-20220303162036416](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-a2e872c35c4e456b6c2ea070c2c37023ef7cc677%2Fimage-20220303162036416.png?alt=media)

Map的实现上与Set惊人的相似。

| Map           | Set           |
| ------------- | ------------- |
| HashMap       | HashSet       |
| LinkedHashMap | LinkedHashSet |
| SortedMap     | SortedSet     |
| TreeMap       | TreeSet       |
| EnumMap       | EnumSet       |

性能比较：

* HashTable 与 HashMap 类似，但是HashTable 线程安全，古老，所以比较慢
* TreeMap 比 HashTable与HashMap慢，尤其插入删除时，需要维护顺序（底层使用红黑树管理key-value）
* LinkedHashMap 相比于 HashMap稍慢一点，因为需要链表维护添加顺序
* EnumMap最优，但是功能有限

推荐HashMap。