关键词：
Java基础知识之什么是集合框架，前面的文章，我们已经学习了Java的一些基础知识，比如泛型、注解等等内容，接着本博客继续学习Java中一个很常见的内容，集合。
1、什么是Java中的集合框架？
Java Collections 框架由接口和类组成，集合框架是用于存储数据和操作一组对象的统一架构。
集合框架提供了很多接口，比如Set、List、Queue、Deque、… ， 实现类的有ArrayList、Vector、LinkedList、PriorityQueue、HashSet、LinkedHashSet、TreeSet、… ，这些实现类都是数据架构和算法的应用，比如链表、红黑树、二叉树等等，集合框架的类可以在java.util这里package里找到
2、Java 集合层次结构
Java Collection提供了很多类，功能比较强大，这里画图简单描述一下Java中的主要类图，先画一个简版，只画一些最重要的接口，如图，Java中的集合类比如HashSet、ArrayList、LinkedList等等都是继承自Set、List、Queue、Deque这些接口，HashMap就是继承自Map接口
用idea软件画出uml图：
继承自Map接口的uml类图：
对集合框架有一个大概了解之后，下面挑几个比较常用的进行描述
3、ArrayList
3.1、uml类图结构
ArrayList是用的比较多的列表List，看一下ArrayList的类图结构：
3.2、声明的属性
简单列表ArrayList源码里声明的几个比较重要的属性
| 属性 | 作用 |
|---|---|
| DEFAULT_CAPACITY | 默认的数组容量 |
| EMPTY_ELEMENTDATA | 用于共享的Empty实例数组 |
| DEFAULTCAPACITY_EMPTY_ELEMENTDATA | 也是一个空的实例数组 |
| elementData | ArrayList中真实存储数据的容器 |
| size | 集合中的元素个数 |
下面简单跟一下ArrayList源码
3.3、构造方法
public ArrayList()
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
public ArrayList(int initialCapacity)
if (initialCapacity > 0)
this.elementData = new Object[initialCapacity];
else if (initialCapacity == 0)
this.elementData = EMPTY_ELEMENTDATA;
else
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
public ArrayList(Collection<? extends E> c)
// 将传入的集合转换为数组
elementData = c.toArray();
if ((size = elementData.length) != 0)
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
// 赋值给elementData
elementData = Arrays.copyOf(elementData, size, Object[].class);
else
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
3.4、add方法
| 方法名 | 作用 |
|---|---|
public boolean add(E e) | 将指定的元素添加到此列表的末尾 |
public void add(int index, E element) | 在指定的index位置加上元素 |
public boolean addAll(Collection<?> c) | 将指定集合的所有元素添加到list末尾 |
public boolean addAll(int index,Collection<? extends E> c) | 在指定位置加上集合的所有元素 |
ArrayList add方法
public boolean add(E e)
// 校验内部容量
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
校验内部容量
private void ensureCapacityInternal(int minCapacity)
// calculateCapacity计算内部容量
// ensureExplicitCapacity继续校验
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
calculateCapacity计算内容容量
private static int calculateCapacity(Object[] elementData, int minCapacity)
// 判断集合是否微empty数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 比较最小容量和默认容量，得出最大值，做第一次扩容
return Math.max(DEFAULT_CAPACITY, minCapacity);
return minCapacity;
ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity)
// 实际修改集合的次数
modCount++;
// overflow-conscious code
// 判断最小容量是否大于数组长度
if (minCapacity - elementData.length > 0)
// 将计算出来的最小容器传值给grow核心扩容方法
grow(minCapacity);
核心的扩容方法：
private void grow(int minCapacity)
// overflow-conscious code
// 记录数组的实际长度
int oldCapacity = elementData.length;
// 扩容方法，原来容量的1.5倍，oldCapacity >> 1右移运算, 也即oldCapacity * (1/2)^1
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断新的容量是否小于最小容量
if (newCapacity - minCapacity < 0)
// 将最小容量直接赋值给新容量
newCapacity = minCapacity;
// 判断新的容量是否大于最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 这种情况，计算出超大容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 创建数组，将数组地址赋值
elementData = Arrays.copyOf(elementData, newCapacity);
下面继续跟一下其它类型的add方法
public void add(int index, E element)
public void add(int index, E element)
// 校验index合法性
rangeCheckForAdd(index);
// 校验内部容量
ensureCapacityInternal(size + 1); // Increments modCount!!
// index+1的目的是在指定index，后面再空出一个index+1的位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 数组赋值
elementData[index] = element;
// 计数器加1
size++;
public boolean addAll(Collection<? extends E> c)添加集合方法：
public boolean addAll(Collection<? extends E> c)
// 将集合转换为Object类型的数组
Object[] a = c.toArray();
// 计算要新增集合的数组长度
int numNew = a.length;
// 加上新集合之后，校验是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 将数组a的元素复制到elementData
System.arraycopy(a, 0, elementData, size, numNew);
// 计算器加上新增集合的元素数量
size += numNew;
// 新增数组的元素个数不为0的情况就是新增成功
return numNew != 0;
public boolean addAll(int index, Collection<? extends E> c)在指定的位置新增集合
public boolean addAll(int index, Collection<? extends E> c)
// 校验index是否合法
rangeCheckForAdd(index);
// 将集合转换为object数组
Object[] a = c.toArray();
// 数组的长度
int numNew = a.length;
// 校验新增元素之后，是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算数组要加到集合的index下标
int numMoved = size - index;
if (numMoved > 0)
// 调整elementData中数据的位置，给新插入的数据腾出空间
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 复制数组a的数据到elementData的指定位置
System.arraycopy(a, 0, elementData, index, numNew);
// 加上新增集合的元素数量
size += numNew;
// numNew不等于0说明新增成功
return numNew != 0;
4、Vector
4.1、UML类图
4.2、Vector和ArrayList的区别
这里可以尝试着翻下Vector的源码，发现其本质也是一个数组，这点是和ArrayList是一样的。不同点是Vector是线程安全的。翻了源码发现很多方法都是有都是有加上同步锁的synchronized
public synchronized void insertElementAt(E obj, int index)
modCount++;
if (index > elementCount)
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
Vector实现逻辑和ArrayList很像，所以就不过多描述
5、HashSet
5.1、Uml类图
5.2、HashSet本质？
这里还是要跟下源码，在idea里点到源码里去，可以看出其实HashSet是通过HashMap实现的，所以后面看下hashMap实现就行
public HashSet()
map = new HashMap<>();
public HashSet(Collection<? extends E> c)
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
6、TreeSet
6.1、uml类图
6.2、TreeSet本质
跟下源码，可以发现TreeSet实现还是通过TreeMap实现的，所以待会再看看TreeMap怎么实现的就可以
public TreeSet()
this(new TreeMap<E,Object>());
7、TreeMap
7.1、uml类图
7.2、TreeMap实现
翻下源码，从源码看起来似乎很熟悉，没错，TreeMap就是通过红黑树实现的，对红黑树比较熟悉的，应该可以马上看出来，不熟悉的读者可以参考我之前的博客数据结构系列之Java手写实现红黑树
- TreeMap成员变量
// 比较器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
/**
* The number of entries in the tree 树节点数量
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree. 记录修改次数
*/
private transient int modCount = 0;
定义一棵红黑树信息，一棵红黑树都会有左节点left、右节点right、父节点parent、红黑树节点的颜色color、同时会保存key和value
static final class Entry<K,V> implements Map.Entry<K,V>
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK
// ...
- put方法，新增节点
public V put(K key, V value)
Entry<K,V> t = root;
// 第一次put，将新节点直接设置为root节点
if (t == null)
compare(key, key); // type (and possibly null) check
// 构建root节点
root = new Entry<>(key, value, null);
size = 1;
// 修改次数
modCount++;
return null;
// cmp比较的值
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 进行比较，找到哪个节点作为新节点的parent节点
if (cpr != null)
do
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
// 新节点值比当前节点值小，继续找左节点
t = t.left;
else if (cmp > 0)
// 找右节点
t = t.right;
else
//插入的值在容器中有相同的值 直接覆盖
return t.setValue(value);
while (t != null);
else
if (key == null)
throw new NullPointerException();
//比较器为空就创建一个比较器
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 找到一个节点作为新节点的parent节点
do
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
while (t != null);
// 新增节点的父节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
// 新节点作为左子节点
parent.left = e;
else
// 作为右子节点
parent.right = e;
// 变色和旋转
fixAfterInsertion(e);
size++;
modCount++;
return null;
前面的逻辑其实就是和二叉搜索树的逻辑是很相似的，只是红黑树新增节点之后要通过变色或者是左旋右旋来保持红黑树的平衡
具体逻辑看一下fixAfterInsertion(node);，这个逻辑比较关键，这里做一下比较详细的描述，这里分情况分析
-
场景1： 红黑树是Empty的，这是最简单的场景，直接将新节点作为根节点就行，不过红黑树有个特性，根节点都是黑色的，所以将新节点涂黑就行
-
场景2：新增节点的父节点是黑节点，由于新增的节点都是红色的节点，所以这种情况不会影响平衡，直接新增就行
-
场景3：新增结点的父结点为红结点且为祖父节点的左子节点
-
场景3.1：新节点的叔叔节点是红色的
这种情况，如图005是新增节点，其叔叔节点是009是红色的，这种情况，需要做下变色，祖父节点008变为红色，父亲节点006变为黑色，叔叔节点009也变为黑色，这样整棵红黑色就可以平衡
-
场景3.2：叔叔节点是黑色，且新增节点作为右子节点
这种情况要做的是将新节点008指向父节点003，同时做左旋
-
场景3.3：叔叔节点是黑色，且新增节点作为左子节点
这种情况，需要将父节点008变黑色，祖父节点011变为红色，同时围绕祖父节点011做右旋
-
-
场景4：新增结点的父结点为红结点，且为祖父节点的右子节点
这种场景也有3种情况，不过和场景3是相反的，这种不做详细描述
private void fixAfterInsertion(Entry<K,V> x)
// 新增的节点都是红色的
x.color = RED;
// 父节点是红色的情况才需要调整红黑树
while (x != null && x != root && x.parent.color == RED)
// 父节点作为祖父节点的左子树
if (parentOf(x) == leftOf(parentOf(parentOf(x))))
// 找到叔叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// case1 : 叔叔节点也是红色
if (colorOf(y) == RED)
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
else
// case2 ： 叔叔节点是黑色，且新增节点是右子节点
if (x == rightOf(parentOf(x)))
// 将父节点和新增节点调换
x = parentOf(x);
// 从父节点处做左旋
rotateLeft(x);
// case 3 : 叔叔节点是黑色，且新增节点是左子节点
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
else //情况与上面逻辑对称
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED)
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)),java基础总结二（集合）(代码片段)
文章目录Java基础总结二（集合）集合概述什么是集合集合和数组的区别使用集合框架的好处常见的集合类有哪些简述List、Set、Map三者区别集合框架底层数据结构哪些集合类是线程安全的集合的快速失败机制“fail-fast”Col... 查看详情
mybatis框架之入门(代码片段)
什么是框架 框架就是一个架子，表演节目，舞台已经搭建好，表演什么节目，看自己的需求了。 框架是一个半成品，对于Java语言来说，框架就是封装了别人的代码。在框架的基础上我们在进一步开发，拿来主义。框架... 查看详情
java基础篇之面向对象(代码片段)
一、类和对象什么是类类：是一组相关属性和行为的集合。可以看成是一类事物的模板，使用事物的属性特征和行为特征来描述该类事物。现实中，描述一类事物：属性：就是该事物的状态信息。行为：就是该事物能够做什么。... 查看详情
java知识面试题复习集合容器概述(代码片段)
集合容器概述什么是集合集合框架：用于存储数据的容器。集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。接口：... 查看详情
java知识面试题复习集合容器概述(代码片段)
集合容器概述什么是集合集合框架：用于存储数据的容器。集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。接口：... 查看详情
夜斗大数据之java篇：不同集合对应不同数据结构(代码片段)
...;day01笔记：动力节点一：集合概述(一）：什么是集合？有什么用？数组其实就是一个集合，集合实际上是一个容器。可以用来容纳其它类型的数据。(二）：集合为什么在开发中使用较多？... 查看详情
夜斗大数据之java篇：不同集合对应不同数据结构(代码片段)
...;day01笔记：动力节点一：集合概述(一）：什么是集合？有什么用？数组其实就是一个集合，集合实际上是一个容器。可以用来容纳其它类型的数据。(二）：集合为什么在开发中使用较多？... 查看详情
死磕java集合之linkedtransferqueue源码分析(代码片段)
问题（1）LinkedTransferQueue是什么东东？（2）LinkedTransferQueue是怎么实现阻塞队列的？（3）LinkedTransferQueue是怎么控制并发安全的？（4）LinkedTransferQueue与SynchronousQueue有什么异同？简介LinkedTransferQueue是LinkedBlockingQueue、SynchronousQueue（ 查看详情
死磕java集合之linkedtransferqueue源码分析(代码片段)
问题（1）LinkedTransferQueue是什么东东？（2）LinkedTransferQueue是怎么实现阻塞队列的？（3）LinkedTransferQueue是怎么控制并发安全的？（4）LinkedTransferQueue与SynchronousQueue有什么异同？简介LinkedTransferQueue是LinkedBlockingQueue、SynchronousQueue（ 查看详情
jdk源码阅读笔记之java集合框架（基础篇）
结合《jdk源码》与《thinkinginjava》，对java集合框架做一些简要分析（本着实用主义，精简主义，遂只会挑出个人认为是高潮的部分）。 先上一张java集合框架的简图： 会从以下几个方面来进行分析：java数组;ArrayL... 查看详情
java修炼之道--集合框架(代码片段)
...作地址：https://github.com/frank-lam/2019_campus_apply前言 Java集合框架(JavaCollectionsFramework,JCF)也称容器，这里可以类比C++中的STL，在市面上似乎还没能找到一本详细介绍的书籍。在这里主要对如下部分进行源码分析，及在面试中常见... 查看详情
java集合框架-综述(代码片段)
目录什么是java集合框架使用类型安全的容器集合框架简图集合类库主要接口简述Collection接口方法概览 什么是java集合框架其实就是java类库提供的一套相当完整的各种数据结构的实现。通常也可以叫做“容器”。比如Lis... 查看详情
java基础之结合源码理解集合（非concurrent）(代码片段)
集合常用接口和类java中的集合非常重要，是一种容器，也是一种引用数据类型，集合相关的接口和类非常多，不考虑concurrent中的情况下，最常见的有如下这些：从上图也可以看到主要分为两大阵营，... 查看详情
java基础之结合源码理解集合（非concurrent）(代码片段)
集合常用接口和类java中的集合非常重要，是一种容器，也是一种引用数据类型，集合相关的接口和类非常多，不考虑concurrent中的情况下，最常见的有如下这些：从上图也可以看到主要分为两大阵营，... 查看详情
第五节：java集合框架之优先级队列priorityqueue（堆）(代码片段)
文章目录一：堆基本概念（1）什么是堆（2）堆存储方式二：堆的模拟实现（1）重点操作说明A：堆的初始化B：堆的向下调整C：堆的构造D：堆的插入E：堆的删除（2）代码... 查看详情
java-基础（集合）(代码片段)
JAVA-基础（集合Collection）1.什么是集合?集合是java中提供的一种容器，可以用来存储多个数据。有点类似于数组。2.集合与数组的区别？数组的长度是固定的。集合的长度是可变的。数组中存储的是同一类型的元素，可以存储基本... 查看详情
java基础之集合(代码片段)
集合开发中使用数组的弊端数组中能够使用的方法非常少，功能方法需要程序员自己完成数据类型单一化，不支持多种情况数组容量定义之后不能改集合的优势方法多样，功能完善数据类型多样化容量可变集合架构Jav... 查看详情
java基础之集合框架
1：String类：字符串(重点) (1)多个字符组成的一个序列，叫字符串。 生活中很多数据的描述都采用的是字符串的。而且我们还会对其进行操作。所以，java就提供了这样的一个类供我们使用。 ... 查看详情