carpenterlee/jcfinternals

深入理解Java集合框架

Java Collections Framework Internals

Authors

Name	Weibo Id	Blog	Mail
李豪	@计算所的小鼠标	CarpenterLee	[email protected]

Introduction

关于*C++标准模板库(Standard Template Library, STL)的书籍和资料有很多，关于Java集合框架(Java Collections Framework, JCF)*的资料却很少，甚至很难找到一本专门介绍它的书籍，这给Java学习者们带来不小的麻烦。我深深的不解其中的原因。虽然JCF设计参考了STL，但其定位不是Java版的STL，而是要实现一个精简紧凑的容器框架，对STL的介绍自然不能替代对JCF的介绍。

本系列文章主要从数据结构和算法层面分析JCF中List, Set, Map, Stack, Queue等典型容器，结合生动图解和源代码，帮助读者对Java集合框架建立清晰而深入的理解。本文并不特意介绍Java的语言特性，但会在需要的时候做出简洁的解释。

Contents

具体内容安排如下：

1. Overview 对Java Collections Framework，以及Java语言特性做出基本介绍。
2. ArrayList 结合源码对ArrayList进行讲解。
3. LinkedList 结合源码对LinkedList进行讲解。
4. Stack and Queue 以AarryDeque为例讲解Stack和Queue。
5. TreeSet and TreeMap 结合源码对TreeSet和TreeMap进行讲解。
6. HashSet and HashMap 结合源码对HashSet和HashMap进行讲解。
7. LinkedHashSet and LinkedHashMap 结合源码对LinkedHashSet和LinkedHashMap进行讲解。
8. PriorityQueue 结合源码对PriorityQueue进行讲解。
9. WeakHashMap 对WeakHashMap做出基本介绍。

jcfinternals's Issues

WeekHashMap弱引用

”WeekHashMap 的这个特点特别适用于需要缓存的场景“ —— 针对博主说的这句话想到的：既然WeekHashMap是弱引用，那么不管内存是否紧张value都有可能会被回收 ; 而软引用，只有当内存不足时才会被回收，那岂不是用软引用更合适，而弱引用在内存泄漏方面更合适一些，博主怎么看？

关于 2019_campus_apply 引用 JCFInternals 说明

博主你好，我在我的仓库 2019_campus_apply 中引用了一些本仓库的一些源码分析和部分示例图，无商业用途，开源免费。也欢迎群主能够加入一起交流，QQ 1002039945

ArrayDequeue中疑问.

易理解

關於PriorityQueue的remove情況2應該還有其他情形需要處理?

以範例那張圖為例
假設remove的是15 也就是index=5的那個元素
在siftDown後那個位置會變成9, heap不對, 因此應該還需要檢查

if (queue[i] == moved) {
    siftUp(i, moved);
 }

博主什么时候更新Java8的HashMap

Java8的HashMap做了相当多的优化,当桶上的链表节点大于8的话就转换为红黑树了,测试在hash极不均匀的情况下相比JDK7有明显的性能提升,等待你的分析博客了

发现错别字

• 位于JCFInternals/markdown/5-TreeSet and TreeMap.md
• 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪

图裂了

PNG图片完全都打不开

LinkedList 标示图箭头问题

add(int index, E element)，方法的 解释箭头 有两个下一个。

5-TreeSet and TreeMap.md

寻找节点后继
t的右孩子为空，则t的后继是其第一个向左走的祖先。
->
虽然代码是ch == p.right 表述是否应换为"第一个向右走的祖先"?

另外 文中所说的情况1~6 是哪些呢?望答主不吝赐教

Stack & Queue

Stack Method	Equivalent Deque Method	说明
push(e)	addFirst(e)	向栈顶插入元素，失败则抛出异常
无	offerFirst(e)	向栈顶插入元素，失败则返回false
pop()	removeFirst()	获取并删除栈顶元素，失败则抛出异常
无	pollFirst()	获取并删除栈顶元素，失败则返回null
peek()	peekFirst()	获取但不删除栈顶元素，失败则抛出异常
无	peekFirst()	获取但不删除栈顶元素，失败则返回null

Stack Method	Equivalent Deque Method	说明
push(e)	addFirst(e)	向栈顶插入元素，失败则抛出异常
无	offerFirst(e)	向栈顶插入元素，失败则返回false
pop()	removeFirst()	获取并删除栈顶元素，失败则抛出异常
无	pollFirst()	获取并删除栈顶元素，失败则返回null
peek()	getFirst()	获取但不删除栈顶元素，失败则抛出异常
无	peekFirst()	获取但不删除栈顶元素，失败则返回null

Stack and Queue

由于官方更推荐使用AarryDeque用作栈和队列，加之上一篇已经讲解过LinkedList，本文将着重讲解ArrayDeque的具体实现。

拼写错误