JDK & STL 源码分析计划

为了学好数据结构以及相关算法，同时也为了更好地理解 JDK 的底层实现，计划对 JDK 集合类的源码做一个系统的阅读分析。

欢迎随时提交 PR 或 Issue。建了一个 Gitter 聊天室，点击图标加入： 。

浏览请点击： JDK 源码分析。

Warning

本文档基于 OpenJDK 11.0.6 2020-01-14 LTS 的代码开展分析，请 PR 的小伙伴使用相同的 JDK。谢谢！

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

官网及版本库

本文档的版本库托管在 Github 上，另外单独发布。

“地瓜哥”博客网

https://www.diguage.com/ 。D瓜哥的个人博客。欢迎光临，不过，内容很杂乱，请见谅。不见谅，你来打我啊，😂😂

本文档官网

https://diguage.github.io/jdk-source-analysis/ 。为了方便阅读，这里展示了处理好的文档。阅读请点击这个网址。

本文档版本库

https://github.com/diguage/jdk-source-analysis 。欢迎大家发送 PR。

总体思路

1. 学习基本的数据结构认识。兵马未动粮草先行。先把基础理论搞清楚。

   1. 学Java的，可以从下面两本书中选一本：

      1. 数据结构与算法分析 — 这本书的优点在于和 Java JDK 的集合类很贴近。

      2. 算法（第4版） — 这本书胜在图很多。

   2. 学 C/C++ 的，可以看下面这套书：

      1. 算法：C语言实现 (第1～4部分)

      2. 算法：C语言实现 （第5部分）

2. 自己实现一遍基本的数据结构；

3. 阅读 JDK 或 STL 源码，做学习笔记。

   Tip	对比一下自己的实现和这些经典代码的实现，总结自己差距，提高自己的编码能力。

   1. STL源码剖析  — 阅读源码时，建议参考一下本书的内容。

   2. 建议把网上的源码分析笔记都看一看，取长补短，补充自己的分析。

   3. 建议把网上相关面试题也看一看，检验自己的学习成果。

4. 相关联的 LeetCode 上的题都刷掉。

Note	还有两个想法： 可以把 Redis 的实现也过一下，Redis 实现也有很多不错的思路。毕竟 Redis 是目前最常用的缓存解决方案。 Java 中有很多针对集合类做扩展的库，可以一并学了，这样就能更清楚了解 Java JDK 实现的不足，开阔自己的眼界： google/guava: Google core libraries for Java Apache Commons Collections Eclipse Collections - Features you want with the collections you need.

JDK 集合类

Base + Iterator

代码总行数： 103 + 135 + 302 + 195 + 838 + 127 + 734 + 480 = 2914 行，预计 5 个小时。

1. java.lang.Iterable

2. java.util.Iterator

3. java.util.PrimitiveIterator

4. java.util.ListIterator

5. java.util.Spliterator

6. java.util.Enumeration

7. java.util.Collection

8. java.util.AbstractCollection

List

代码总行数： 1063 + 942 + 253 + 1266 + 1509 + 141 + 1759 = 6933 行，预计 12 个小时。

1. java.util.List

2. java.util.AbstractList

3. java.util.AbstractSequentialList

4. java.util.LinkedList

5. java.util.Vector

6. java.util.Stack

7. java.util.ArrayList

Queue

代码总行数： 212 + 616 + 192 + 1233 + 987 = 3240 行，预计 6 个小时。

1. java.util.Queue

2. java.util.Deque

3. java.util.AbstractQueue

4. java.util.ArrayDeque

5. java.util.PriorityQueue

Set

代码总行数： 732 + 186 + 264 + 491 + 323 + 361 + 560 + 195 + 1395 = 4507 行，预计 8 个小时。

1. java.util.Set

2. java.util.AbstractSet

3. java.util.SortedSet

4. java.util.EnumSet

5. java.util.NavigableSet

6. java.util.HashSet

7. java.util.TreeSet

8. java.util.LinkedHashSet

9. java.util.BitSet

Map

代码总行数： 1687 + 284 + 424 + 857 + 3012 + 1339 + 812 + 1600 + 756 + 2444 + 155 + 1521 = 14891 行，预计 28 个小时。

1. java.util.Map

2. java.util.SortedMap

3. java.util.NavigableMap

4. java.util.AbstractMap

5. java.util.TreeMap

6. java.util.WeakHashMap

7. java.util.EnumMap

8. java.util.IdentityHashMap

9. java.util.LinkedHashMap

10. java.util.HashMap

11. java.util.Dictionary

12. java.util.Hashtable

来张总体结构图：

Tip	这里没有包含并发相关的集合类。这块内容放到并发中一起搞。

目录结构介绍

.
├── LICENSE
├── README.adoc
├── pom.xml
├── docs -- 这里存放阅读源码的文档。
│   └── images -- 这里存放相关图片
└── src
    ├── main
    │   └── java
    │       └── com
    │           └── diguage
    │               └── truman
    │                   └── App.java
    └── test
        └── java
            └── com
                └── diguage
                    └── truman  -- 这个目录存放相关测试代码。
                        └── AppTest.java

源码列表

查看文档，请移步： JDK 源码分析。

• ✓ 迭代器 Iterator、Enumeration、Spliterator 与 Iterable

• ❏ java.util.PrimitiveIterator

• ❏ java.util.ListIterator

• ❏ java.util.Spliterator

• ❏ java.util.Collection

• ❏ java.util.AbstractCollection

• ❏ java.util.List

• ❏ java.util.AbstractList

• ❏ java.util.AbstractSequentialList

• ❏ java.util.LinkedList

• ❏ java.util.Vector

• ❏ java.util.Stack

• ❏ java.util.ArrayList

• ❏ java.util.Queue

• ❏ java.util.Deque

• ❏ java.util.AbstractQueue

• ❏ java.util.ArrayDeque

• ❏ java.util.PriorityQueue

• ❏ java.util.Set

• ❏ java.util.AbstractSet

• ❏ java.util.SortedSet

• ❏ java.util.EnumSet

• ❏ java.util.NavigableSet

• ❏ java.util.HashSet

• ❏ java.util.TreeSet

• ❏ java.util.LinkedHashSet

• ❏ java.util.BitSet

• ❏ java.util.Map

• ❏ java.util.SortedMap

• ❏ java.util.NavigableMap

• ❏ java.util.AbstractMap

• ❏ java.util.TreeMap

• ❏ java.util.WeakHashMap

• ❏ java.util.EnumMap

• ❏ java.util.IdentityHashMap

• ❏ java.util.LinkedHashMap

• ❏ java.util.HashMap

• ❏ java.util.Dictionary

• ❏ java.util.Hashtable