0%

介绍

Vector和ArrayList一样,内部都是通过数组实现。Vector是线程安全的,但是由于使用了synchronized方法,性能上比ArrayList差。

源码分析

继承

1
2
3
4
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

Vector继承于AbstractList,实现了List, RandomAccess, Cloneable这些接口。

成员变量

1
2
3
4
protected Object[] elementData;  //存放数据的对象数组
protected int elementCount; //记录存了多少个元素
protected int capacityIncrement; //当向量溢出时增加的数量
private static final long serialVersionUID = -2767605614048989439L;

构造函数

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
 //传入两个参数initialCapacity和capacityIncrement,initialCapacity是Vector初始化的容量,capacityIncrement是当Vector溢出时增加的数量
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}


public Vector(int initialCapacity) {
this(initialCapacity, 0);
}

//如果不规定向量大小,就默认为10
public Vector() {
this(10);
}

//将Collection转化为了数组
public Vector(Collection<? extends E> c) {
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

add

add函数和Arraylist差不多,ArrayList是扩容空间1.5倍,Vector是扩容了2倍。

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
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1); //判断空间是否够用
elementData[elementCount++] = e;
return true;
}
//minCapacity是需要最小空间的容量,低于这个值就存不进去数据
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0) //判断增加的大小是否在对象数组大小的范围内
grow(minCapacity); //如果空间不足,就需要扩容了
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前容器的大小
//如果增量capacityIncrement>0,就将容器增加capacityIncrement
//否则,容器增加一倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果空间还是不够用,直接扩容到需要的空间。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

其他

其余的方法也不介绍了,因为和ArrayList差不多。Vector的所有方法都是用synchronized修饰,从而保证了访问vector的所有方法都必须获得对象的锁。虽然vector内部实现了同步,但是外部调用时,如果一些线程连续调用两个或者两个以上的同步方法,也会引起混乱。因此,在使用vector时,连续调用两个或两个以上的同步方法仍然需要进行同步处理。

对象创建

对象创建过程

虚拟机遇到new指令,先去检查这个指令的参数是否在常量池中定位到一个类的符号引用并检查这个符号引用的类是否已经被加载、解析和初始化过。

  • 检查常量池中是否有将要创建对象所属类的符号引用
    • 常量池中没有类的符号引用,说明这个类还未定义,报ClassNotFoundException;
  • 检查这个符号引用的类是否已经被JVM加载
    • 类未加载,找打类的class文件,加载到方法区;
    • 类已经被JVM加载,则准备为对象分配内存
  • 对象所需的内存大小在类加载完成后便完全确定(类的所有对象的内存大小相同),把一块确定大小的内存在Java堆中划分出来。
  • 内存分配完成后,虚拟机需要将分配到的内存空间都初始化为零(不包括对象头)。
  • 设置对象头中的信息
  • 完成创建,可以调用对象的构造函数初始化。

    分配内存的两种方式

    用哪种方式由Java堆是否完整和gc收集器决定
  • 指针碰撞。(如果内存是规整的,用过的内存在一边,空闲的内存在另一边,中间放着一个指针作为分界点的指示器,分配内存就是将指针向空闲区域移动一段与对象相同的距离。)
  • 空闲列表,(已使用的内存和空闲的内存相互交错,虚拟机必须维护一个表,记录哪块内存是可用的,分配内存的时候就可以在列表中找到一块足够大的空间划分给对象。)

对象在虚拟机中的创建是非常频繁的行为,修改指针指向位置在并发下并不是线程安全的,虚拟机采用CAS来保证更新操作的原子性。

对象的内存布局

对象在内存中存储的布局可以分为3块区域:

  • 对象头(Header)
  • 实例数据(Instance Data)
  • 对齐填充(Padding)

对象头

对象头分为两部分,第一部分是存储对象自身运行时数据:哈希码、GC分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等。第二部分是对象所属类型指针,虚拟机通过这个指针来确定这个对象时哪个类的实例。
如果对象时一个Java数组,那么在对象头中还必须有一块用于记录数组长度的数据。

实例数据

实例数据就是对象真正存储的有效信息,包括父类的成员变量和本类的成员变量。

对齐填充

起占位符的作用,HotSpotVM的自动内存管理系统要求对象起始地址必须是8字节的整数倍,当对象实例数据部分没有对齐时,就需要通过对齐填充来补全。

对象的访问定位

主流访问方式有:使用句柄和直接指针两种。

  • 句柄访问方式(堆中需要有一块叫做“句柄池”的内存空间,用于存放所有对象的地址和所有对象所属类的类信息。
    引用类型的变量存放的是该对象在句柄池中的地址。访问对象时,首先需要通过引用类型的变量找到该对象的句柄,然后根据句柄中对象的地址再访问对象。)
  • 直接指针访问方式(引用类型的变量直接存放对象的地址,从而不需要句柄池,通过引用能够直接访问对象。
    但对象所在的内存空间中需要额外的策略存储对象所属的类信息的地址。)

两种方式各有优势,使用句柄访问最大好处是reference中存储的是稳定的句柄地址,对象移动时只会改变句柄中的实例数据指针,而reference本身不需要修改。直接指针方式最大的好处是速度更快,节省了一次指针定位的时间开销,对象访问在Java中非常频繁,因此这类开销积少成多后是一项非常可观的执行成本。

通过show status 了解SQL执行频率

1
mysql> show status like 'Com_%';
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
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| Com_admin_commands | 0 |
| Com_alter_db | 0 |
| Com_alter_db_upgrade | 0 |
| Com_alter_event | 0 |
| Com_alter_function | 0 |
| Com_alter_procedure | 0 |
| Com_alter_server | 0 |
| Com_alter_table | 0 |
| Com_alter_tablespace | 0 |
| Com_analyze | 0 |
| Com_assign_to_keycache | 0 |
| Com_begin | 0 |
| Com_binlog | 0 |
| Com_call_procedure | 0 |
| Com_change_db | 0 |
| Com_change_master | 0 |
| Com_check | 0 |
| Com_checksum | 0 |
| Com_commit | 0 |
| Com_compound_sql | 0 |
| Com_create_db | 0 |
| Com_create_event | 0 |
| Com_create_function | 0 |
| Com_create_index | 0 |
| Com_create_procedure | 0 |
| Com_create_role | 0 |
……

Com_xxx表示每个xxx语句执行了多少次。通常只关心:

1
2
3
4
Com_select: 执行select的次数,一次查询累加1
Com_insert: 执行insert的次数,批量插入只累加1
Com_update: 执行update操作次数
Com_delect: 执行delect的次数

上面参数对于所有存储引擎表的操作都会累计

1
show status like "Innodb_rows_%";
1
2
3
4
Innodb_rows_read
Innodb_rows_inserted
Innodb_rows_updated
Innodb_rows_delected
1
2
3
4
5
6
7
8
9
10
MariaDB [xxxx]> show status like "Innodb_rows_%";
+----------------------+-------+
| Variable_name | Value |
+----------------------+-------+
| Innodb_rows_deleted | 0 |
| Innodb_rows_inserted | 21335 |
| Innodb_rows_read | 41566 |
| Innodb_rows_updated | 0 |
+----------------------+-------+
4 rows in set (0.00 sec)

常用:

1
2
3
4
show status like 'uptime'; //mysql运行时间
show status like 'connections';//mysql连接数
show status like 'slow_queries'; //显示慢查询次数
show [session|global] status like ...; //默认是session,也就是当前窗口发生的,可以是用global,统计mysql启动后所有的统计信息。

定位执行效率低的SQL语句

通过两种方式:
1、通过慢查询日志定位执行效率低的SQL语句。
使用show variables like ‘long_query_time’;查看当前慢查询的时间,可以看到现在是10秒。(也就是说执行时间超过10秒的查询,才会被认为是慢查询,需要修改。)

1
2
3
4
5
6
7
MariaDB [(none)]> show variables like 'long_query_time';
+-----------------+-----------+
| Variable_name | Value |
+-----------------+-----------+
| long_query_time | 10.000000 |
+-----------------+-----------+
1 row in set (0.00 sec)

使用set long_query_time=1 ;设置慢查询时间为1秒。

1
2
MariaDB [(none)]> set long_query_time=1 ;
Query OK, 0 rows affected (0.00 sec)

重新查询,发现慢查询时间已经改为1秒

1
2
3
4
5
6
7
MariaDB [(none)]> show variables like 'long_query_time';
+-----------------+----------+
| Variable_name | Value |
+-----------------+----------+
| long_query_time | 1.000000 |
+-----------------+----------+
1 row in set (0.00 sec)

查看慢查询日志是否打开

1
2
3
4
5
6
7
8
MariaDB [(none)]> show variables like 'slow_query%';
+---------------------+-------------------+
| Variable_name | Value |
+---------------------+-------------------+
| slow_query_log | OFF |
| slow_query_log_file | Gavin-PC-slow.log |
+---------------------+-------------------+
2 rows in set (0.00 sec)

slow_query_log的值是OFF,未打开

1
set global slow_query_log='ON';  //打开慢查询日志 

my.ini中,记录了慢查询日志的位置:

1
datadir = "E:/mysql/data"

2、show processlist;查看当前MYSQL在进行的线程,包括线程的状态,是否锁表等等,可以实时查看SQL的执行情况

参考资料:《深入浅出MySQL–数据库开发、优化和管理维护》(第2版)

简介

Java虚拟机管理的内存包括下面五个运行时数据区域:
Alt text

  • 程序计数器
  • Java虚拟机栈
  • 本地方法栈
  • 方法区

程序计数器

程序计数器(Program Counter Register)是一块较小的内存空间,可以看做当前所执行的字节码的行号指示器。字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令,也就是下一条字节码指令的地址。

  • 线程私有(多线程并发执行时每个线程必须有自己的程序计数器,用来记录自己执行字节码的位置,方便CPU时间片轮询切换后继续执行)。
  • 如果执行的是Native方法(指本地方法:一般使用C/C++在另外文件中编写),这个计数器值记为空。
  • 此区域是唯一一个在Java虚拟机规范中没有规定任何OutOfMemoryError情况的区域(程序计数器存放当前线程下一条指令所在的位置,可以预见其大小,所以不会内存溢出)。

Java虚拟机栈

Java虚拟机栈是线程私有,生命周期与线程相同。

  • 栈描述的是方法执行的内存模型。每个方法被调用都会创建一个栈帧(存储局部变量表、操作数栈、动态链接、方法出口等)
  • JVM为每个线程创建一个栈,用于存放该线程执行方法的信息(实际参数、局部变量等)
  • 栈属于线程私有,不能实现线程间的共享!
  • 栈的存储特性是“先进后出,后进先出”(每一个方法从调用直到执行完成的过程,就对应一个栈帧在虚拟机栈中入栈到出栈的过程。)
  • 局部变量表的创建是在方法被执行的时候,随着栈帧的创建而创建。而且,局部变量表的大小在编译时期就确定下来了,在创建的时候只需分配事先规定好的大小即可。此外,在方法运行的过程中局部变量表的大小是不会发生改变的。
  • Java虚拟机栈会出现两种异常:StackOverFlowError和OutOfMemoryError。
    • StackOverFlowError:若Java虚拟机栈的内存大小不允许动态扩展,那么当线程请求栈的深度超过当前Java虚拟机栈的最大深度的时候,就抛出StackOverFlowError异常。
    • OutOfMemoryError:若Java虚拟机栈的内存大小允许动态扩展,且当线程请求栈时内存用完了,无法再动态扩展了,此时抛出OutOfMemoryError异常。

本地方法栈

  • 本地方法栈和Java虚拟机栈实现的功能类似,只不过本地方法区是本地方法运行的内存模型。
  • 本地方法被执行的时候,在本地方法栈也会创建一个栈帧,用于存放该本地方法的局部变量表、操作数栈、动态链接、出口信息。
  • 方法执行完毕后相应的栈帧也会出栈并释放内存空间。
  • 也会抛出StackOverFlowError和OutOfMemoryError异常。

    Java堆

  • 堆用于存储创建好的对象和数组(数组也是对象)
  • JVM只有一个堆,所有的线程都访问同一个堆。而程序计数器、Java虚拟机栈、本地方法栈都是一个线程对应一个的。
  • 所有的线程都访问同一个堆,进行对象内存的分配均需要进行加锁,所以new对象操作开销比较大
  • 在虚拟机启动时创建
  • 垃圾回收的主要场所。
  • 可以进一步细分为:新生代、老年代。
  • 新生代又可被分为:Eden、From Survior、To Survior。
  • 不同的区域存放具有不同生命周期的对象。这样可以根据不同的区域使用不同的垃圾回收算法,从而更具有针对性,从而更高效。
  • 堆的大小既可以固定也可以扩展,但主流的虚拟机堆的大小是可扩展的,因此当线程请求分配内存,但堆已满,且内存已满无法再扩展时,就抛出OutOfMemoryError。
    QQ20190129231959jpg

方法区

  • JVM只有一个方法区,被所有线程共享!
  • 方法区实际也是堆(堆的一个逻辑部分),只是用于存储类、常量相关的信息!
  • 用来存放程序中永远是不变或唯一的内容。(类信息【Class对象】、静态变量、字符串常量等)
    线程共享
  • 永久代 方法区中的信息一般需要长期存在,而且它又是堆的逻辑分区,因此用堆的划分方法,我们把方法区称为老年代。
  • 内存回收效率低 方法区中的信息一般需要长期存在,回收一遍内存之后可能只有少量信息无效。
  • 对方法区的内存回收的主要目标是:对常量池的回收 和 对类型的卸载。
  • Java虚拟机规范对方法区的要求比较宽松。
    和堆一样,允许固定大小,也允许可扩展的大小,还允许不实现垃圾回收。

    运行时常量池

  • 运行时常量池是方法区的一部分
  • 方法区中存放三种数据:类信息、常量、静态变量、即时编译器编译后的代码。其中常量存储在运行时常量池中。
  • 我们一般在一个类中通过public static final来声明一个常量。这个类被编译后便生成Class文件,这个类的所有信息都存储在这个class文件中。
  • 当这个类被Java虚拟机加载后,class文件中的常量就存放在方法区的运行时常量池中。而且在运行期间,可以向常量池中添加新的常量。如:String类的intern()方法就能在运行期间向常量池中添加字符串常量。
  • 当运行时常量池中的某些常量没有被对象引用,同时也没有被变量引用,那么就需要垃圾收集器回收。

MySQL 优化的思路

  • 1、表的设计要合理,符合三范式
  • 2、添加适当索引(index):普通索引、主键索引、唯一索引 unique、全文索引(有时候加上:空间索引)
  • 3、分表技术(水平分割、垂直分割)
  • 4、读写(写:updata/dalete/add)分离
  • 5、存储过程(不建议)[模块化编程,不用编译,提高速度]
  • 6、对 MySQL 文件修改配置文件(my.ini: max_connections = 100,可以调整到 1000 左右)
  • 7、MySQL 服务器硬件升级
  • 8、定时清除不需要的数据,定时进行碎片整理(MyISAM)

3NF(范式)

第一范式

有主关键字、主键不能为空、主键不能重复,、字段不可以再分

id name sex contact
1 john male email:kkkk@xx.com,phone:222456
2 mary famale email:kkk@xx.com phone:123455
上面这个不符和一范式,因为 contact 字段可以再分,改为下面即可符合一范式:
id name sex email phone
1 john male kkkk@xx.com 222456
2 mary famale kkk@xx.com 123455

第二范式

  • 是表必须有一个主键;
  • 二是没有包含在主键中的列必须完全依赖于主键,而不能只依赖于主键的一部分。也就是说消除了传递依赖
学生 id 院系 id 姓名 院系名 院系地址 学生手机号
1 003 张三 计科系 xxx 路 123456
2 004 李四 数学系 aaa 路 222222
上面这个也是不符和二范式的,因为存在传递依赖。院系名和院系地址依赖院系 id,而院系 id 依赖学生 id,因此不符合二范式
学生 id 院系 id 姓名 学生手机号
1 003 张三 123456
2 004 李四 222222
院系 id 院系名 院系地址
003 计科系 xxx 路
004 数学系 aaa 路
这样消除了传递依赖,符合二范式。

三范式

任何非主键字段不能依赖于其他非主键字段

学生 id 课程 id 课程名称 学生名称 学生成绩 课程学分
1 003 计算机导论 张三 98 3
2 004 数据结构 李四 99 4
上面的表结构是符合二范式的,由学生 id 和课程 id 组成的联合主键,因此不存在依赖传递,但不符合三范式
学生表:
学生 id 学生名称
1 张三
2 李四
课程表:
课程 id 课程名称 课程学分
003 计算机导论 3
004 数据结构 4
学生-课程 成绩表:
学生 id 课程 id 学生成绩
1 003 98
2 004 99

这样就符合三范式。

反范式

以前数据库设计都是用时间换空间,现在出现了用空间换时间,通过一些冗余设计,来达到快速响应的目的

介绍

Alt text
LinkedList是一个双向链表,可以从头部和尾部对LinkedList进行遍历。

源码

定义

1
2
3
4
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}

LinkedList继承了AbstractSequentialList类,实现了List、Deque(双端队列)、Cloneable(克隆)和java.io.Serializable接口;

Node结点

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
E item; //存储的数据
Node<E> next; //后继结点
Node<E> prev; //前驱结点

Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

从Node结点可以看出来,定义了前驱和后继结点,并且存在带参数的构造函数,也就是说创建一个Node结点必须提供元素值和前驱和后继的结点。

成员变量

1
2
3
4
5
transient int size = 0;//LinkedList中元素个数

transient Node<E> first;//LinkedList第一个结点

transient Node<E> last;//LinkedList最后一个结点

构造方法

1
2
public LinkedList() {
}

不带参数的构造函数。创建了一个空的LinkedList。

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

带Collection参数的构造方法。首先this()调用无参的构造函数,创建一个空的LinkedList,然后执行addAll()函数,接下来看一下然后执行addAll()函数。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
  public boolean addAll(Collection<? extends E> c) {
return addAll(size, c); //继续看下面的addAll()函数
}
/**
* @param index 要插入数据的位置
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//验证index的参数是否合法

Object[] a = c.toArray(); //Collection集合转为对象数组
int numNew = a.length;
if (numNew == 0) //判断要插入数据的长度
return false;

//这里是两种情况,一个是在链表最后追加数据,一个是在链表内插入数据
Node<E> pred, succ;//pred是前驱结点,succ是后继结点
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}

for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)//如果添加的结点是第一个结点,first指向这个结点
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//这里也是两种情况的处理,succ对应上面,表示在链表最后追加的数据,直接将last指向最后一个即可。另一种情况是在链表中间插入数据,这里需要将链表后面的数据连接上。
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}

size += numNew; //改变链表大小
modCount++; //表示链表已经修改过
return true;
}
//返回下标为index的结点
Node<E> node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

继续向下看:

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
37
38
39
40
41
42
43
/**
* 将e插入在链表的开头
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);//创建一个新的结点
first = newNode;
if (f == null) //如果原来的链表是null,表示插入的这个结点是头结点也是尾结点
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* 将e插入在链表的队尾
*/
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++;
}
/**
* 将e插入在succ结点之前
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* 删除第一个结点,默认f == first && f != null;
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; //获取出来第一个结点的数据
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next; //将first指向第二个结点
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* 删除最后一个结点
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}

/**
* 删除结点x
*/
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;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
* Returns the first element in this list.
* 返回第一个结点值
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

/**
* Returns the last element in this list.
* 返回最后一个结点值
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

/**
* Removes and returns the first element from this list.
* 删除第一个结点
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

/**
* Removes and returns the last element from this list.
* 删除最后一个结点
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}

/**
* Inserts the specified element at the beginning of this list.
* 添加元素到第一个结点
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}

/**
* Appends the specified element to the end of this list.
* 添加元素到最后一个结点
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}

/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
* 判断o是否存在LinkedList中
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}

public int indexOf(Object o) {
int index = 0;
if (o == null) { //如果o是null,也要找链表里面是否存在null值
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}

/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}

介绍

Alt text
ArrayList是一个动态数组,可以动态增长。ArrayList不是线程安全的,因此不建议在多线程中使用,可以选择Vector或者CopyOnWriteArrayList。

源码

定义

1
2
3
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

ArrayList继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable接口。

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static final long serialVersionUID = 8683452581122892189L;
//默认的初始容量
private static final int DEFAULT_CAPACITY = 10;
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储对象的数组
transient Object[] elementData; // non-private to simplify nested class access
//实际存储的数量
private int size;
//数组最大数量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

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

无参数的构造函数。调用无参数的构造函数,elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

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

指定参数的构造函数。默认三种情况:当参数大于0,则直接初始化相同大小的对象数组;当参数等于0,用EMPTY_ELEMENTDATA初始化elementData;当参数小于0,抛出异常。

1
2
3
4
5
6
7
8
9
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}

Collection作为参数的构造函数。直接将Collection转化为数组复制给elementData,当c.toArray不返回Object[],进行数组拷贝。如果Collection为空,将EMPTY_ELEMENTDATA赋给elementData。

add

1、add(E e)

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

看一下ensureCapacityInternal()函数:

1
2
3
4
//minCapacity为对象数组所需的最小空间值
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
1
2
3
4
5
6
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

calculateCapacity()判断elementData是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,如果是则返回DEFAULT_CAPACITY和minCapacity中最大的值(其实这里可以理解为调用无参构造函数的默认大小为10,因为调用add(E e),minCapacity的大小为1,并且elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,会返回初始容量DEFAULT_CAPACITY)。

再继续看ensureExplicitCapacity()函数:

1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
  • modCount 可以理解为修改次数,用于非线程安全的ArrayList,LinkedList,HashMap等等,主要用于迭代遍历中,当迭代器开始遍历时会获取这个值,遍历过程中如果其他线程修改modCount,迭代器会发现,并报异常。所以在遍历非线程安全的数据结构,尽量使用迭代器。
  • ensureExplicitCapacity()函数判断elementData的空间能否满足minCapacity,不满足则调用grow()函数扩容

继续看grow()函数:

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
private void grow(int minCapacity) {
// overflow-conscious code
//oldCapacity是当前elementData的实际长度
int oldCapacity = elementData.length;
//oldCapacity >> 1,表示oldCapacity/2。也就是说newCapacity的长度为oldCapacity的1.5倍。
int newCapacity = oldCapacity + (oldCapacity >> 1);
//扩充了1.5倍,如果超过了int的最大值,就会变成负数,这里是检测是否溢出;
//如果扩充了1.5倍,还不够用,直接扩充到当前需要的数量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 复制数据到新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//newCapacity超出了MAX_ARRAY_SIZE,就返回Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
  • MAX_ARRAY_SIZE的问题。MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8,数组作为一个对象,需要一定的内存存储对象头信息,对象头信息最大占用内存不可超过8字节。

2、add(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//在列表的指定位置插入指定元素
public void add(int index, E element) {
//判断界限是否有效
rangeCheckForAdd(index);
//判断数组是否够用
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index后面的数据向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1
2
3
public static native void arraycopy(Object src,  int  srcPos,
Object dest, int destPos,
int length);
  • Object src : 原数组
  • int srcPos : 从原数据的起始位置开始
  • Object dest : 目标数组
  • int destPos : 目标数组的开始起始位置
  • int length : 要copy的数组的长度

其他重要的函数

1
2
3
4
5
6
7
8
9
10
//清理多余未用的空间,假如elementData的实际大小是15,size此时为10,执行该方法后,elementData的实际大小变为10;
public void trimToSize() {
//modCount并不是添加元素后才变化,清理完空间后,modCount也发生变化。
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
1
2
3
4
//返回数组元素的数量
public int size() {
return size;
}
1
2
3
4
//判断是否为空
public boolean isEmpty() {
return size == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。
public int indexOf(Object o) {
//如果参数为null,则遍历数组,判断是否存在null
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
1
2
3
4
//如果列表包含指定的元素,则返回 true。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。
//逆序遍历
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
//返回此 ArrayList 实例的浅表副本。(克隆)
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
1
2
3
4
//按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
//如果a.length < size,则创建一个a数组,大小为arraylist的大小
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
//如果a数组大小够用,直接复制elementData到a中
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

1
2
3
4
5
6
7
8
9
10
11
//返回此列表中指定位置上的元素。
public E get(int index) {
//检查边界
rangeCheck(index);

return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1
2
3
4
5
6
7
8
9
//用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
//返回旧值
return oldValue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//移除此列表中指定位置上的元素。
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

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

return oldValue;
}
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
//移除此列表中首次出现的指定元素
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;
}
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
}
1
2
3
4
5
6
7
8
9
10
//移除此列表中的所有元素。
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}
1
2
3
4
5
6
7
8
9
//按照指定 collection 的迭代器所返回的元素顺序,将该 collection 中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//从指定的位置开始,将指定 collection 中的所有元素插入到此列表中。
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

整体框架

Alt text

Iterator

Iterator是一个接口,是集合的迭代器,集合可以使用Iterator来遍历集合中的元素。

1
2
3
4
5
6
7
8
public interface Iterator<E> {

boolean hasNext(); //是否存在下一个元素

E next(); //返回迭代的下一个元素。

void remove(); //从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。每次调用 next 只能调用一次此方法。如果进行迭代时用调用此方法之外的其他方式修改了该迭代器所指向的 collection,则迭代器的行为是不确定的。
}

Collection

Collection继承了Iterable,Iterable

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
public interface Collection<E> extends Iterable<E> {
int size(); //返回此 collection 中的元素数。如果此 collection 包含的元素大于 Integer.MAX_VALUE,则返回 Integer.MAX_VALUE。

boolean isEmpty(); //如果此 collection 不包含元素,则返回 true。

boolean contains(Object o); //如果此 collection 包含指定的元素,则返回 true。

Iterator<E> iterator(); //返回在此 collection 的元素上进行迭代的迭代器。

Object[] toArray(); //返回包含此 collection 中所有元素的数组。

<T> T[] toArray(T[] a); //返回包含此 collection 中所有元素的数组;返回数组的运行时类型与指定数组的运行时类型相同。

boolean add(E e); //确保此 collection 包含指定的元素。

boolean remove(Object o); // 从此 collection 中移除指定元素的单个实例,如果存在的话

boolean containsAll(Collection<?> c);//如果此 collection 包含指定 collection 中的所有元素,则返回 true。

boolean addAll(Collection<? extends E> c);//将指定
collection 中的所有元素都添加到此 collection 中

boolean removeAll(Collection<?> c);//移除此 collection 中那些也包含在指定 collection 中的所有元素

boolean retainAll(Collection<?> c);//仅保留此 collection 中那些也包含在指定 collection 的元素

void clear(); //移除此 collection 中的所有元素

boolean equals(Object o); //比较此 collection 与指定对象是否相等。

int hashCode(); //返回此 collection 的哈希码值。
}

AbstractCollection

AbstractCollection的定义如下:

1
public abstract class AbstractCollection<E> implements Collection<E> {}

AbstractCollection是一个抽象类,它实现了除iterator()和size()之外的函数,方便其它类实现Collection,比如ArrayList、LinkedList等,它们这些类想要实现Collection接口,通过继承AbstractCollection就已经实现了大部分的接口。

List

List继承于Collection的接口,List是有序的队列。List包含了Collection中的全部接口,也有自己的API接口。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public interface List<E> extends Collection<E> {
//Collection的API
int size();

boolean isEmpty();

boolean contains(Object o);

Iterator<E> iterator();

Object[] toArray();

<T> T[] toArray(T[] a);

boolean add(E e);

boolean remove(Object o);

boolean containsAll(Collection<?> c);

boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);

boolean retainAll(Collection<?> c);

void clear();

boolean equals(Object o);

int hashCode();

ListIterator<E> listIterator();

//新增的API
boolean addAll(int index, Collection<? extends E> c); //将指定 collection 中的所有元素都插入到列表中的指定位置
/**
* @since 1.8 jdk1.8引入
*/
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);//判断对象是否为空,空的时候报空指针异常
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}

E get(int index);//返回列表中指定位置的元素

E set(int index, E element); //用指定元素替换列表中指定位置的元素

void add(int index, E element);//在列表的指定位置插入指定元素

E remove(int index);//移除列表中指定位置的元素

int indexOf(Object o);//返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。

int lastIndexOf(Object o);//返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。

ListIterator<E> listIterator(int index);//返回列表中元素的列表迭代器(按适当顺序),从列表的指定位置开始。

List<E> subList(int fromIndex, int toIndex);//返回列表中指定的 fromIndex(包括 )和 toIndex(不包括)之间的部分视图。

@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}

AbstractList

AbstractList的定义如下:

1
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {}

AbstractList继承于AbstractCollection,实现了List接口的抽象类,实现了List中除size()、get(int location)之外的函数(实现了iterator()接口),从而方便其它类继承List。

Set

Set是一个继承于Collection的接口,Set也是集合中的一种。Set是没有重复元素的集合,和数学定义一样。
Set的API和Collection的API完全一样。

1
public interface Set<E> extends Collection<E>{}  //定义

AbstractSet

AbstractSet的定义如下:

1
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {}

AbstractSet继承于AbstractCollection,Set也就没有自己单独的API,和AbstractCollection一样,它实现了List中除iterator()和size()之外的函数。

简介

链表在Redis中应用广泛,比如列表键的底层实现之一就是链表。当列表键包含了比较多元素,或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。(其余情况使用ziplist压缩列表)

链表实现

每个链表的节点使用adlist.h中的listNode来表示:

1
2
3
4
5
6
7
8
9
10
11
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;

使用adlist.h中的list持有整个链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* 双端链表结构
*/
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数,用于复制链表节点所保存的值
void *(*dup)(void *ptr);
// 节点值释放函数,用于释放链表节点所保存的值
void (*free)(void *ptr);
// 节点值对比函数,用于对比链表节点所保存的值与另一个输入值是否相等
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
  • 表头节点prev和表尾节点next都指向NULL,对链表的访问以NULL为终点。
    image.png

链表API

函数 作用 时间复杂度
listSetDupMethod 将给定的函数设置为链表的节点值复制函数。 O(1)
listGetDupMethod 返回链表当前正在使用的节点值复制函数。 复制函数可以通过链表的 dup 属性直接获得, O(1)
listSetFreeMethod 将给定的函数设置为链表的节点值释放函数。 O(1)
listGetFree 返回链表当前正在使用的节点值释放函数。 释放函数可以通过链表的 free 属性直接获得, O(1)
listSetMatchMethod 将给定的函数设置为链表的节点值对比函数。 O(1)
listGetMatchMethod 返回链表当前正在使用的节点值对比函数。 对比函数可以通过链表的 match 属性直接获得, O(1)
listLength 返回链表的长度(包含了多少个节点)。 链表长度可以通过链表的 len 属性直接获得, O(1)
listFirst 返回链表的表头节点。 表头节点可以通过链表的 head 属性直接获得, O(1)
listLast 返回链表的表尾节点。 表尾节点可以通过链表的 tail 属性直接获得, O(1)
listPrevNode 返回给定节点的前置节点。 前置节点可以通过节点的 prev 属性直接获得, O(1)
listNextNode 返回给定节点的后置节点。 后置节点可以通过节点的 next 属性直接获得, O(1)
listNodeValue 返回给定节点目前正在保存的值。 节点值可以通过节点的 value 属性直接获得, O(1)
listCreate 创建一个不包含任何节点的新链表。 O(1)
listAddNodeHead 将一个包含给定值的新节点添加到给定链表的表头。 O(1)
listAddNodeTail 将一个包含给定值的新节点添加到给定链表的表尾。 O(1)
listInsertNode 将一个包含给定值的新节点添加到给定节点的之前或者之后。 O(1)
listSearchKey 查找并返回链表中包含给定值的节点。 O(N) , N 为链表长度
listIndex 返回链表在给定索引上的节点。 O(N) , N 为链表长度
listDelNode 从链表中删除给定节点。 O(1)
listRotate 将链表的表尾节点弹出,然后将被弹出的节点插入到链表的表头, 成为新的表头节点。 O(1)
listDup 复制一个给定链表的副本。 O(N) , N 为链表长度
listRelease 释放给定链表,以及链表中的所有节点。 O(N) , N 为链表长度

学习资料:
[1] 黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.

简介

Redis构建了一种名为简单动态字符串(simple dynamic string ,SDS)的抽象类型,用来保存字符串。

SDS 实现

shs.h文件中sdshdr结构体表示了一个SDS的值:

1
2
3
4
5
6
7
8
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};

SDS结构

  • SDS和C字符串一样,使用空字符结尾,保存空字符串的1字节空间不包含在SDS的len属性里面,因此需要分配N+1个字节空间来保存数据。
  • len属性表示SDS保存字符串的长度,不包含字符串结尾的空字符串。
  • free属性表示数组中未使用的字节数量
  • buf属性是char类型的数组,用来保存SDS字符串数据。

    SDS 特点

    常数复杂度获取字符串长度

    在更新和添加字符串到SDS的过程中,SDS的API会自动更新SDS的len属性,不需要手动更改,因此获取字符串长度的时间复杂度是O(1)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /*
    * 返回 sds 实际保存的字符串的长度
    *
    * T = O(1)
    */
    static inline size_t sdslen(const sds s) {
    //// 取出 sdshdr
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
    }

    防止缓存区溢出

    C字符串不记录自身的长度,容易发生缓冲区溢出。SDS的free属性记录数组中未使用的字节数量,SDS的API操作SDS会首先检查剩余空间是否满足要求,所以不会发生缓冲区溢出的情况。

    内容重分配策略

    空间预分配

    需要对SDS进行空间扩展时,程序不仅会为SDS分配所必须的空间,还会分配额外未使用的空间。
  • 对SDS修改之后,SDS的长度小于1MB,那么程序分配和len属性同样大小的空间,假设修改后SDS的大小是13字节,那么将分配13+13+1=27个字节。
  • 如果对SDS修改之后,SDS的长度大于等于1MB,将分配1M未使用空间。假设修改后SDS的长度是30MB,那么程序会分配1MB未使用空间,实际大小为:30MB+1MB+1byte.
    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
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    /*
    * 最大预分配长度
    */
    #define SDS_MAX_PREALLOC (1024*1024)
    /*
    * 对 sds 中 buf 的长度进行扩展,确保在函数执行之后,
    * buf 至少会有 addlen + 1 长度的空余空间
    * (额外的 1 字节是为 \0 准备的)
    *
    * 返回值
    * sds :扩展成功返回扩展后的 sds
    * 扩展失败返回 NULL
    *
    * 复杂度
    * T = O(N)
    */
    sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);
    size_t len, newlen;
    // s 目前的空余空间已经足够,无须再进行扩展,直接返回
    if (free >= addlen) return s;
    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    // s 最少需要的长度
    newlen = (len+addlen);
    // 根据新长度,为 s 分配新空间所需的大小
    //判断分配后的总长度是否小于1MB
    if (newlen < SDS_MAX_PREALLOC)
    // 如果新长度小于 SDS_MAX_PREALLOC
    // 那么为它分配两倍于所需长度的空间
    newlen *= 2;
    else
    // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
    newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    // 内存不足,分配失败,返回
    if (newsh == NULL) return NULL;
    // 更新 sds 的空余长度
    newsh->free = newlen - len;
    // 返回 sds
    return newsh->buf;
    }

    惰性空间释放

    惰性空间释放是指不通过内存重分配回收缩短后多出来的字节,而是通过改变free属性,惰性的释放空间。下面的代码就是在不释放空间的情况下,重置SDS字符串为空字符串,也就是惰性空间释放:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /*
    * 在不释放 SDS 的字符串空间的情况下,
    * 重置 SDS 所保存的字符串为空字符串。
    *
    * 复杂度
    * T = O(1)
    */
    /* Modify an sds string on-place to make it empty (zero length).
    * However all the existing buffer is not discarded but set as free space
    * so that next append operations will not require allocations up to the
    * number of bytes previously available. */
    void sdsclear(sds s) {

    // 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0;

    // 将结束符放到最前面(相当于惰性地删除 buf 中的内容)
    sh->buf[0] = '\0';
    }

    二进制安全

    C字符串除了字符串的未尾之外,字符串里面不能包含空字符,否则最先被程序读入的空间将被误认为是字符串结尾,这些限制了C字符串只能保存文本数,不能保存图片等二进制数据。SDS没有这种限制,可以保存文本或者二进制数据

    SDS API

    函数 作用 算法复杂度
    sdsnewlen 创建一个指定长度的 sds ,接受一个 C 字符串作为初始化值 (O(N))
    sdsempty 创建一个只包含空白字符串 “” 的 sds (O(1))
    sdsnew 根据给定 C 字符串,创建一个相应的 sds (O(N))
    sdsdup 复制给定 sds (O(N))
    sdsfree 释放给定 sds (O(N))
    sdsupdatelen 更新给定 sds 所对应 sdshdr 结构的 free 和 len (O(N))
    sdsclear 清除给定 sds 的内容,将它初始化为 “” (O(1))
    sdsMakeRoomFor 对 sds 所对应 sdshdr 结构的 buf 进行扩展 (O(N))
    sdsRemoveFreeSpace 在不改动 buf 的情况下,将 buf 内多余的空间释放出去 (O(N))
    sdsAllocSize 计算给定 sds 的 buf 所占用的内存总数 (O(1))
    sdsIncrLen 对 sds 的 buf 的右端进行扩展(expand)或修剪(trim) (O(1))
    sdsgrowzero 将给定 sds 的 buf 扩展至指定长度,无内容的部分用 \0 来填充 (O(N))
    sdscatlen 按给定长度对 sds 进行扩展,并将一个 C 字符串追加到 sds 的末尾 (O(N))
    sdscat 将一个 C 字符串追加到 sds 末尾 (O(N))
    sdscatsds 将一个 sds 追加到另一个 sds 末尾 (O(N))
    sdscpylen 将一个 C 字符串的部分内容复制到另一个 sds 中,需要时对 sds 进行扩展 (O(N))
    sdscpy 将一个 C 字符串复制到 sds (O(N))

学习资料:
[1] 黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.