CAS 源码分析

摘要:CAS全称为compare and swap,是原子操作的一种,可用于在多线程编程中实现不被打断的数据交换操作,从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 该操作通过将内存中的值与指定数据进行比较,当数值一样时将内存中的数据替换为新的值。
from Wikipedia

查看更多

LinkedList 源码分析

TOP 带着问题看源码

  1. LinkedList 采用的数据结构是什么

1. 继承和实现关系

  • AbstractSequentialList 实现类

    提供一些围绕着iterator的基础方法

  • List 接口

    提供 list 功能

  • Deque 接口

    提供双端操作功能,以此可以猜出 LinkedList 数据结构是一个双向链表

  • Cloneable 接口

    标记该类对象能够被Object.clone()

  • Serializable 接口

    标记该类是可序列化的

2. 成员变量分析

1
2
3
4
5
6
// 容量
transient int size = 0;
// 首节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

接下来看节点 Node的成员变量

1
2
3
4
5
6
// 节点的值
E item;
// next 指针
Node<E> next;
// prev 指针
Node<E> prev;

回到 TOP 1 问题,根据实现可以明白其数据结构是一个双向链表

3. 构造方法分析

一个是默认无参,一个是带集合内容的。

把传来的集合新增入当前list

1
2
3
4
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

接下来看节点 Node的构造方法,根据入参默认维护两个指针。

1
2
3
4
5
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}

4. 核心方法分析

4.1 获取元素

先check,然后通过 node(index)方法取

1
2
3
4
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

node 方法通过判断索引 index 的范围(若是大于一半集合容量,则从尾结点向前遍历,若小于则从头结点向后遍历)来尽量高效的取到对应的节点

4.2 新增元素

4.2.1 add(E e)

尾插

1
2
3
4
public boolean add(E e) {
linkLast(e);
return true;
}

构建一个next指针是null,prev指针是尾结点的新节点newNode,如果尾结点不为空则将尾结点的next结点指向newNode,否则将头结点指向newNode

1
2
3
4
5
6
7
8
9
10
11
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

4.2.2 add(int index, E element)

先check,如果插入的还是尾部,则调用 linkLast 方法,否则先获取到索引 index 对应的节点然后调用 linkBefore 方法

1
2
3
4
5
6
7
8
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}

构建一个 prev 指针是索引 index - 1 对应节点,next节点是索引 index 对应节点的新节点newNode (图中绿色部分)。然后把index节点的prev指向newNode (图中蓝色部分),如果要插入的是第一个位置,则把 first 指针指向newNode,否则维护剩余的指针关系(index - 1 节点的next指向newNode)(图中红色部分)

4.3 更新元素

根据下标位置获取节点,然后把节点的值进行覆盖

1
2
3
4
5
6
7
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

4.4 删除元素

4.4.1 remove(int index)

先check,然后先获取index对应节点最后调用unlink方法

1
2
3
4
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

同按照下标新增那块逻辑差不多,去除一个节点(prev next item置null),重新维护指针关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

4.4.2 remove(Object o)

遍历要找的元素的index,然后调用unlink方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

4.4.3 clear()

遍历赋值null,size重置为0

ArrayList 源码分析

TOP 带着问题看源码

  1. List list = new ArrayList(20) 扩容了几次
  2. ArrayList 怎么实现数组动态扩容,扩容时机,扩容倍数
  3. ArrayList 怎么实现remove的
  4. 为什么remove具体元素性能差
  5. ArrayList 是怎么序列化的

1. 继承和实现关系

  • RandomAccess 接口

    标记该类具有快速随机访问能力。当一个集合拥有该能力时候,采用for循环遍历会很快;若没有则采用Iterator迭代器最快。参考ArrayList的indexOf(Object o)方法和AbstractList的indexOf(Object o)方法区别。

  • Serializable 接口

    标记该类是可序列化的。

  • Cloneable 接口

    标记该类对象能够被Object.clone()

    根据重写的clone方法实现主要分为如下两种克隆方式

    1. 浅克隆

      只copy对象本身和对象中的基本变量,不copy包含引用的对象

    2. 深克隆

      不仅copy对象本身,还copy对象包含的引用对象

  • AbstractList 抽象类

    ​ 提供一些基础方法: IndexOf、clear、addAll、iterator等

2. 成员变量分析

1
2
3
4
5
6
7
8
9
10
11
12
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组实例(为0时候)
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认大小时候的空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储数组
transient Object[] elementData;
// 数组大小
private int size;
// 数组最大容量,减8是因为可能一些VM会在数组保留一些header,防止OOM
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3. 构造方法分析

3.1 无参构造方法

默认赋值一个空数组实例

1
2
3
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

3.2 带初始化容量的构造方法

可以看到是由参数的大小来创建对应大小的 elementData 数组,回到 TOP 1 问题,可以看出来不会发生扩容,也就是0次

1
2
3
4
5
6
7
8
9
10
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);
}
}

3.3 带集合内容的构造方法

把传过来的集合转化为数组赋值给 elementData 数组

1
2
3
4
5
6
7
8
9
10
11
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 = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

4. 核心方法分析

4.1 获取元素

先 check ,再按照 index 取。check也是为了保证工程中不会出现奇奇怪怪的结果

1
2
3
4
5
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

使用 final 修饰的数组来接收存储数组,对其遍历。 modCount 变量和 final 修饰的 expectedModCount 进行对比来判断是否存在并发读写情况

1
2
3
4
5
6
7
8
9
10
11
12
13
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

4.2 新增元素

4.2.1 add(E e)

把一个元素新增到elementData,主要涉及如下几点

  1. modCount++ 声明我新增元素了,在并发情况下起到容量是否发生变化作用
  2. 如果容量不足,则扩容数组大小(参考下面grow方法)
1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

####4.2.2 add(int index, E element)

按照index位置来插入元素,和上面方法同理。

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

####4.2.3 grow(int minCapacity)

第4行可以看到,使用位运算扩容了 1.5 倍大小空间,至于为啥是1.5倍,我猜是经验值。

回到 TOP 2 问题,可以明白了扩容机制是通过数组 copy方式,时机就是容量不够的时候,倍数是1.5倍

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}

4.3 更新元素

直接数组下标覆盖,返回旧值,至于为什么返回的是旧值,可能一方面是根据下标查询不是很影响性能索性给查询出来,另一方面下标和新值请求者都清楚也没必要返回。

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

4.4 删除元素

4.4.1 remove(int index)

计算要删除的下标后一位到数组末尾的长度,然后通过copy这段长度覆盖到原数组的位置,最后把最后一位置null,实现删除。

回到 TOP 3 问题,可以明白删除机制也是通过数组copy覆盖的思想来实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);
// 计算长度
int numMoved = size - index - 1;
if (numMoved > 0)
// param1: 源数组
// param2: 源数组要复制的起始位置
// param3: 目标数组
// param4: 目标数组放置的起始位置
// param5: 复制的长度
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

####4.4.2 remove(Object o)

首先分为两个场景,第一个是要删除的元素是null,第二个是要删除的是非null的。

主要是遍历要找的元素,找到该元素对应的index,然后使用 fastRemove(index) 去快速删除

回到 TOP 4 问题,可以明白计算某个元素下标的时间复杂度是 O(n) 的,所以性能没有直接根据下标删除好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

4.4.3 fastRemove(int index)

因为调用该方法都是内部计算index后调用的,所以不需要再校验index是否越界,也不需要返回oldValue。

1
2
3
4
5
6
7
8
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}

4.4.4 clear()

遍历赋值null,size重置为0

5. 序列化

首先我们在最开始就有介绍 ArrayList 类实现的有 Serializable 接口,但是我们在成员变量那一节看到的存储数组 elementData 是有 transient 修饰的,也就是elementData不会参与默认序列化,那实现这个 Serializable 接口还有意义么?

其实仔细观察类里的方法你会发现有两个与序列化的流有关系的方法:writeObjectreadObject

在序列化过程中如果有这两个方法,会默认调用这两个方法进行用户自定义的序列化和反序列化,如果没有才走默认序列化。

那么我们知道作者的序列化是自定义了,那为什么这样做呢,为什么不直接使用默认序列化呢?

我们可以想下,每次扩容1.5倍,那这个数组实际会有一些空间扩容后还未被填充,如果使用默认序列化则会将null也给序列化进去。

接下来我们来看一下自定义序列化方法具体的实现:

###5.1 writeObject

写入数组大小,遍历写入数组元素,检查并发冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();

// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);

// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

5.2 readObject

初始化存储数组elementData,读取写入的数组大小,构造数组并写入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;

// Read in size, and any hidden stuff
s.defaultReadObject();

// Read in capacity
s.readInt(); // ignored

if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);

Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}

回到 TOP 5 问题,可以明白 ArrayList 序列化采用的是自定义序列化方式

5.3 自定义序列化的原理

通过跟踪ObjectOutputStream的writeObject()方法,调用链路如下所示:

writeObject -> writeObject0 -> writeOrdinaryObject -> writeSerialData

代码如下所示,可以看到会先判断是否有 writeObject 方法,如果有的话,会通过反射的方式调用序列化对象的writeObject方法,如果没有则使用默认序列化方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private void writeSerialData(Object obj, ObjectStreamClass desc)
throws IOException
{
ObjectStreamClass.ClassDataSlot[] slots = desc.getClassDataLayout();
for (int i = 0; i < slots.length; i++) {
ObjectStreamClass slotDesc = slots[i].desc;
if (slotDesc.hasWriteObjectMethod()) {
PutFieldImpl oldPut = curPut;
curPut = null;
SerialCallbackContext oldContext = curContext;

if (extendedDebugInfo) {
debugInfoStack.push(
"custom writeObject data (class \"" +
slotDesc.getName() + "\")");
}
try {
curContext = new SerialCallbackContext(obj, slotDesc);
bout.setBlockDataMode(true);
slotDesc.invokeWriteObject(obj, this);
bout.setBlockDataMode(false);
bout.writeByte(TC_ENDBLOCKDATA);
} finally {
curContext.setUsed();
curContext = oldContext;
if (extendedDebugInfo) {
debugInfoStack.pop();
}
}

curPut = oldPut;
} else {
defaultWriteFields(obj, slotDesc);
}
}
}

很方便的密码加密算法BCrypt

摘要:用户表的密码一般都不是使用明文,使用明文坏处可以参考之前CSDN数据库被黑导致用户密码泄露造成的影响。虽然使用明文也有一定的方便之处(毕竟现在的加密都是单向的,比如客户打电话问密码、老大或者上级问密码),但是我们完全可以根据用户提供的其他信息(比如密保让客户自己输入密码进行更改而不是直接告诉用户密码),无论怎么样明文存储密码的坏处一定大于好处。下面将介绍使用Spring Security时候遇到的默认密码加密算法BCrypt:

查看更多

Spring Boot中使用Swagger2构建强大的RESTful API文档

摘要:Swagger2,它可以轻松的整合到Spring Boot中,并与Spring MVC程序配合组织出强大RESTful API文档。它既可以减少我们创建文档的工作量,同时说明内容又整合入实现代码中,让维护文档和修改代码整合为一体,可以让我们在修改代码逻辑的同时方便的修改文档说明。另外Swagger2也提供了强大的页面测试功能来调试每个RESTful API。

查看更多