Java之线程安全

目录

一.上节回顾

1.Thread类常见的属性

2.Thread类中的方法

二.多线程带来的风险

1.观察线程不安全的现象

三.造成线程不安全现象的原因

1.多个线程修改了同一个共享变量

2.线程是抢占式执行的

3.原子性

4.内存可见性

5.有序性

四.解决线程不安全问题 ---synchronized

1.synchronize

2.synchronized解决的线程安全问题

1.解决了原子性问题

2.解决了可见性问题

3.不能解决有序性

3.synchronzied具体的使用方法

1.修饰普通方法

2.修饰静态方法

3.修饰代码块

4.synchronized使用的注意事项

5.synchronized的特性

1.互斥性

2.刷新内存

3.可重入

6.彻底搞懂synchronized锁对象

1.锁对象的记录的信息

2.多线程竞争的锁对象必须为同一个对象

3.锁对象可以为任意对象

五.解决线程不安全问题 ---volatile

1.volatile解决内存可见性

1.重现内存可见性

2.MESI缓存一致性协议

3.内存屏障

2.解决有序性

3.不能解决原子性

六.synchronized和volatile总结

七.wait()和notify()

1.wait()

2.notify()

3.wait()和notify()

八.Java中线程安全的类

1.线程安全的类

2.线程不安全的类

---

一.上节回顾

上节内容指路:Java之多线程初阶2

1.Thread类常见的属性

属性	获取方法
ID	getId()
名称	getName()
状态	getState()
优先级	getPriority()
是否后台线程	isDaemon()
是否存活	isAlive()
是否被中断	isInterrupted()

2.Thread类中的方法

1.后台进程isDaemon()

2.线程中断  ---interrupt()

3.线程等待  ----join()

4.获取当前线程  ---Thread.currentThread()

5.线程休眠    ---Thread.sleep()

6.start()和run()的区别 

1. start()方法是真正申请一个系统线程,run()方法是定义线程要执行的任务
2. 直接调用run()方法,不会去申请一个真正的系统线程(PCB),而是调用对象的方法

7.主动让出CPU   ---yield()

8.线程之间状态的转移图

二.多线程带来的风险

1.观察线程不安全的现象

用两个线程对一个共享的变量做自增操作

public class Demo17_Insecurity {static Counter counter = new Counter();public static void main(String[] args) {Thread thread1 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});Thread thread2 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});thread1.start();thread2.start();try {thread1.join();thread2.join();} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(counter.count);}
}class Counter {public int count = 0;public void increment() {count++;}}

打印的结果:

按我们的分析来说分别进行5w次的自增操作,最后count的值应该是10w,为什么会产生这种结果呢?

在单线程的情况下进行运行,我们都知道运行的结果为10w,但是多线程的情况下就不对了,当多线程的运行结果与单线程的运行结果不一致的时候,会造成线程不安全的现象

三.造成线程不安全现象的原因

1.多个线程修改了同一个共享变量

多个线程修改同一个共享变量会发生线程不安全的现象

多个线程修改不同的共享变量会发生线程不安全的现象

单线程环境下,也不会出现线程不安全的现象

2.线程是抢占式执行的

多个线程在CPU上的调度是不可知的.

3.原子性

原子性我们在数据库中也学习过,其实都是一样的,指令要么都执行,要么都不执行.但是仅以我个人的理解而言,在多线程中,我们不妨把原子性这样来理解,当发生线程不安全的时候,涉及到了修改了同一个共享变量,修改共享变量的命令可以看成一个整体(原子),也就是这些命令我们要么都一起执行,要么所有的暂时都不先执行,等待一下再执行,这样就保证多线程的安全,确保代码的原子性.

不妨我们就那上面的代码举例,可以有人会疑问,上面就一条代码,这不一定是原子的吗?那不一定,JVM要把这一条代码转换成CPU能看懂的指令,然后让CPU去执行,因此一条代码不一定就是原子性的,可能它由多条指令组成.

比如count++操作由以下操作做成

1. 从内存中将count的值读到CPU(LOAD)
2. 进行自增操作(ADD)
3. 将数据写入到内存中(STORE)

这样我们的一条代码才算是执行完毕.

接下来我们模拟两条线程情况下如何不保证原子性可能会发生的情况(并发)

 

 以上三种情况,除了第一种情况,其他三种都会发生线程不安全的现象,具体原因拿其中一幅图来进行分析.

首先线程1被调入CPU,将count的值加载到自己的工作内存中(LOAD),然后进行自增操作(ADD),此时线程1的工作内存中count=1,但是还没有进行STORE操作,主内存的值还没有改变

然后线程2抢占到了CPU,它将主内存count=0加载到自己的工作内存,然后自增操作,然后将工作内存中count=1的值store到主内存中,此时主内存中count=1;

 

最后线程2被调离CPU,线程1被调入CPU,此时线程1将工作内存中的值保存到主内存中,此时主内存的值被修改为1(未发生改变).

 分析了以上我们就可以知道为什么之前我们代码执行的结果和我们预期的结果不一样了.

这就是我们没有确保原子性会带来多线程不安全现象.其最主要的原因还是因为线程是抢占式执行的,CPU调度的随机性

如何上段代码可以保证代码的原子性(也就是修改共享变量的这段代码可以一起执行,或者等待一会再一起执行),就可以解决这个问题了.其实我们可以把这段代码加锁,让之后的线程无法抢占资源,就可以避免这个问题了(具体等到之后演示).

4.内存可见性

在多线程的情况下,一个线程修改了共享变量的值,另一个线程却没有拿到最新的值.

所谓的可见性就是一个线程修改了共享变量的值,能够及时地被其他线程看到.

Java 内存模型 (Java Memory Model)(JMM): Java虚拟机规范中定义了Java内存模型.

1.为什么Java要引入JMM呢?

我们都知道Java是一个跨平台的语言,不同平台的计算设备和操作系统是不同的,JMM对内存管理进行了统一的封装.

下图是一个CPU,不同的平台可能不一样,比如没有缓存.其中寄存器保存代码运行的结果,比如int c=a+b;计算出c的结果保存到寄存器中,下一次CPU需要c的值做其他的运算,我们不必从内存条中进行获取,直接从寄存器中进行获取,这样运行的速度更快.

2.主内存和工作内存

1. 主内存,指的是硬件中的内存条,进程在启动的时候会申请一些资源,申请到的内存就包括主内存和工作内存,用来保存所有的变量.
2. 工作内存,指的是每个线程独有的内存,他们之间不能互相访问,起到了线程之间内存隔离的作用.
3. JMM规定,一个线程在修改某个变量的值的时候,必须要把这个变量的值从主内存中加载到工作内存,修改完成后再刷新到主内存
4. 每个工作内存之间是相互隔离的.
5. JMM可以保证原子性,可见性,有序性.

5.有序性

有序性是指,编译过程中,JVM调用本地接口,CPU执行指令过程中,指令的有序性.

现在举一个现实中的例子,一段代码是这样的进行编写的：

1. 去前台取下 U 盘 (到前台)

2. 去教室写 10 分钟作业 (到教室)

3. 去前台取下快递 (到前台)

我们按照这个顺序编写成功并执行了代码,但是JVM在执行的过程中,并不是按照这个顺序进行执行的,因为这样的效率很低,所以CPU进行了指令的重排序,重排序之后代码是按照1-->3-->2的顺序进行执行的,但是这个代码的逻辑不发生改变,也就是重排序前和重排序后的代码运行的结果是一样的,但提高了程序的效率.

这样进行了指令的重排序,在单线程的情况下100%是正确的,但是在多线程的情况下就未必是正确的

四.解决线程不安全问题 ---synchronized

1.synchronize

synchronize关键字相当于给这个方法加了一把锁,当一个线程要执行这个方法的时候,他首先要获取锁,获取到锁之后就执行相应的代码,另一个线程要执行这个方法的时候,他也要先获取锁,但是前一个线程持有锁的时候他就要等待(前面所说的线程的BLOCK状态),直到前一个线程执行完相应的代码释放锁的时候

public class Demo18_Synchronized {static Counter18 counter = new Counter18();public static void main(String[] args) {Thread thread1 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});Thread thread2 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});thread1.start();thread2.start();try {thread1.join();thread2.join();} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(counter.count);}
}class Counter18 {public int count = 0;public synchronized void increment() {count++;}}

打印结果:

 上面的代码我们可以看出,打印的结果是正确的.

加入synchronize关键字之后,我们可以观察到由多线程操作变为了单线程,虽然效率降低了,但是确保了安全性,所以还是很有必要的.

总结单线程和多线程使用的场景

1.涉及到获取变量的值的时候,考虑使用多线程提高效率.

2.涉及到修改变量值的时候,使用单线程来保证安全性.

线程1获取到锁之后执行了对应的代码,线程2也要执行这个方法,但是检查锁的状态已经被持有,所以它处在堵塞(BLOCK)的状态,当线程1执行完方法之后,线程2才有可能获得到锁(并不一定),因为线程是抢占式执行的,可能线程1再次执行这个方法,再次先获得到了锁.

现在举一个形象点的例子,小人1去上厕所,它获取到了锁,进入到上厕所,其他的小人要想上厕所,因为现在已经上了锁,所以他们只能处在等待堵塞的状态,当小人1出来之后,他们又在一起竞争(小人1也参与竞争),竞争到锁的就可以先上厕所,其它的小人又需要等待,

注意: 只要线程没有释放锁(即使被调离CPU),其它线程还是无法执行这个方法(代码块)的.

2.synchronized解决的线程安全问题

1.解决了原子性问题

通过以上分析不难看出来,通过加锁解决了原子性的问题.保证synchronized圈住的代码块一定是作为一个整体一起执行的,即使被调离CPU,其他的线程也不会打破线程1代码执行的原子性,其他线程一直会等待线程1释放完锁之后才会执行.

2.解决了可见性问题

synchronized通过加锁,将多线程变为单线程,并行变为串行的操作,可以保证线程1修改到最新的值一定会被其他的线程获取到.

3.不能解决有序性

sychronized不能解决有序性,后面有其他的关键字可以解决.

3.synchronzied具体的使用方法

1.修饰普通方法

修饰方法直接在方法命名前加入synchronzied关键字即可.上面已经演示,这里不做过多的叙述,此时的锁对象为Counter18对象,也就是this对象

class Counter18 {public int count = 0;public synchronized void increment() {count++;}}

2.修饰静态方法

这里的锁对象是Counter18类对象,可以就是Counter18.class

class Counter18 {public static int count = 0;public static synchronized void increment() {count++;}}

3.修饰代码块

当一个方法内不仅涉及到变量的修改操作的时候,还涉及到获取变量的值的操作的时候,我们没有必要将所有的代码都加上锁,只需要把修改变量的代码块加上锁即可,因为获取变量值的操作不涉及线程安全的问题,这样既可以保证安全性,也可以保证效率.

class Counter19 {public int count = 0;public void increment() {//获取到数据的操作   ---这部分的操作没必要加锁//getUserName()//get...()//修改数据的操作  ---这部分代码一定要加锁synchronized (this){count++;}}}

synchronized加到代码块上去需要一个对象(锁对象),作用是当多个线程竞争时候判断竞争的是否为同一把锁,如果是就参与竞争,不是就各自执行各自的内容.

4.synchronized使用的注意事项

1.从并行到串行:首先要保证正确，才是效率
2.加锁与CPU调度:加锁后对一个方法加锁并不说是这个线程一直把这个方法执行完才被调度走，而是被调度走时，不释放这个锁，别的线程需要一直等待，就好比图书馆占座
3.加锁的范围(粒度):加在for循环外面就和串行是一模一样的了，但是加在外面两个for 循环之间就是并发执行的，这个写仍然比两个for循环分别执行要快很多，加锁的范围，这个要根据实际情况考虑，加锁的范围越大称为锁的粒度大，加锁的范围小称为锁的粒度小
4.只给一个线程加锁:不会产生竞争，结果还是错的                                                                        比如一共有两个方法,代码的操作都是一样的,但是一个方法加了synchronized,一个没有加,两个线程一个调用synchronized方法,另一个调用没有加的方法,此时结果还是错的

5.给代码块加锁:如果要加锁的代码只是一段代码怎么办? synchronized中以修饰方法也可以修饰代码块，修饰代码块时要传入一个参数，这个参数就是要锁哪个对象
6.锁对象:竞争的锁都必须是针对同一个对象的，可以自定义一个单独的对象表示锁，也可以使用this，通常使用this就可以了，我们写多线程代码时不关心锁对象到底是谁，只关心他们竞争的是不是同一把锁(同一个对象)，如果是同一把锁就可以产生锁竞争，不是同一个对象就不会产生锁竞争,锁对象可以使Java中任意的对象.

5.synchronized的特性

1.互斥性

synchronized 会起到互斥效果 , 某个线程执行到某个对象的 synchronized 中时 , 其他线程如果也执行到同一个对象 synchronized 就会 阻塞等待 .

• 进入到synchronized代码块相当于加锁(LOCK)
• 离开synchronized代码块相当于解锁(UNLOCK)

理解阻塞等待

针对每一把锁都维护一个堵塞等待队列,当A拿到锁执行的时候,其他线程(比如B,C线程)尝试获取到锁,因为A已经获取到了锁,B,C进入堵塞等待队列,当线程A执行完释放锁的时候,操作系统唤醒其他的线程(B,C出列),竞争同一把锁,不一定B先出列一定B就先竞争到锁.

2.刷新内存

synchronized内的代码执行完毕直接将新的值刷新到主内存中,解决了多线程的可见性的问题.

3.可重入

synchronized 同步块对同一条线程来说是可重入的，不会出现自己把自己锁死的问题；

    理解把自己锁死

指的是一个线程加了一把锁之后,又加了同一把锁(因为上一把锁没有释放,所以这一把锁一之处在堵塞的状态,而且是不可能释放上一把锁的),这时候就会 死锁                    ----这样的锁成为不可重入锁

而synchronized是可重入锁,不会出现死锁的现象.

6.彻底搞懂synchronized锁对象

1.锁对象的记录的信息

Java虚拟机中,对象在内存中结构可以分为4个区域

markword和类型指针统称为对象头

• markword    ---------主要描述了当前是哪个线程获取到锁资源，记录的是线程对象信息

• 类型指针(_class)

• 实例数据(instance_data)  类中的属性

• 对齐填充(padding)  每一个类对象占用的字节必须为8字节的整数倍

1. 当线程来争抢锁资源时，会检查锁对象的对象头
2. 如果锁对象，对象头中的信息为空，那么直接获取到锁资源
3. 如果对象头中的信息不为空，那么先判断一下记录的是不是当前线程，如果不是就阻塞等待，如果是那么就直接拿到锁

2.多线程竞争的锁对象必须为同一个对象

当把count定义为类属性(static),并且将increment加上synchronized关键字.定义两个不同的Counter20对象,然后调用各自的increment方法,他们对同一个count进行自增操作(因为count是类属性).

public class Demo20_Synchronized {static Counter20 counter = new Counter20();static Counter20 counter2 = new Counter20();public static void main(String[] args) {Thread thread1 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});Thread thread2 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter2.increment();}});thread1.start();thread2.start();try {thread1.join();thread2.join();} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(counter.count);}
}class Counter20 {public static int count = 0;public synchronized void increment() {count++;}}

打印的结果:

 由打印的结果可以看出并不符合我们预期的结果,但是我们明明都加了synchronized关键字了,为什么会出现这种结果呢?因为他们竞争的不是一个锁对象,前面我们已经提过了加在方法上的锁对象是this,也就是new出来的count和count2对象,他们竞争的不是一个锁,运行出来的肯定无法是预期结果.

这样和上面运行出来的结果都不是100000,他们的锁对象都是一样的

class Counter20 {public static int count = 0;public void increment() {synchronized (this) {count++;}}}

如何要运行出预期的结果,可以做以下修改

class Counter20 {public static int count = 0;public void increment() {synchronized (Counter20.class) {count++;}}}

我们将锁对象换成了Counter20 .class,Counter20在内存中只有一份,因此两个线程竞争的锁对象是一样的,结果自然也是预期的.

其实我们做如下修改也是一样的

class Counter20 {public static int count = 0;public synchronized static void increment() {count++;}}

这样锁对象也是Counter20.class,因此竞争的也是一个锁对象.

3.锁对象可以为任意对象

这里可以为Object类对象,当然可以为其他类对象

    public void increment() {synchronized (Object.class) {count++;}}

也可以是new出来的普通对象.

class Counter20 {public static int count = 0;public Object locker=new Object();public void increment() {synchronized (locker) {count++;}}}

 当然这样不会产生预期的结果

也可以是new出来的类对象(static)

class Counter20 {public static int count = 0;public static Object locker=new Object();public void increment() {synchronized (locker) {count++;}}}

这样结果就是正确的.

总结:synchronized可以解决原子性,可见性,但不能解决有序性

五.解决线程不安全问题 ---volatile

synchronized解决了原子性,内存可见性,但是没有解决有序性问题..

synchronized没有通过线程间通信真正解决内存可见性.只是并行变串行粗暴的解决.

1.volatile解决内存可见性

1.重现内存可见性

public class Demo21_volatile {private static int flag = 0;public static void main(String[] args) throws InterruptedException {// 定义第一个线程Thread t1 = new Thread(() -> {System.out.println("t1线程已启动.");// 循环判断标识位while (flag == 0) {}System.out.println("t1线程已退出.");});// 启动线程t1.start();// 定义第二个线程，来修改flag的值Thread t2 = new Thread(() -> {System.out.println("t2线程已启动");System.out.println("请输入一个整数：");Scanner scanner = new Scanner(System.in);// 接收用户输入并修改flag的值flag = scanner.nextInt();System.out.println("t2线程已退出");});// 确保让t1先启动TimeUnit.SECONDS.sleep(1);// 启动t2线程t2.start();}}

当我们输入一个非0值的时候,预期结果应该是t1线程退出循环,0值的时候,不退出循环

但是实际输出却不一样,等待很长时间都没有t1线程已退出的信息

1.在执行的过程中,线程1将变量的值从主内从中加载到自己的工作内存,也就是寄存器和缓存器中

2.CPU对执行过程中做了一定优化:既然线程没有对变量进行修改,而从工作内存中读取的速度是从主内存中读取速度的1万倍以上,所以每次变量的值就从工作内存中读取

3.此时线程2修改了变量的值,但是没有一种机制来通知线程1来获取最新的值.

此时volatile就出现了,我们使用volatile来修饰flag变量

private static volatile int flag = 0;

可以看到线程1成功退出,这样就成功的保证了内存可见性.

接下来分析实现内存可见性的原因,

2.MESI缓存一致性协议

 当某个线程对共享变量进行修改时,通知其他CPU对该变量的缓存值置为失效状态

当其他CPU从缓存中获取该共享变量值的时候,发现这个值被置为失效状态,那么就需要重新从主内存中加载最新的值

3.内存屏障

Load 表示读操作,Store表示写操作

1.在每个volatile写操作前插入StoreStore屏障，这样就能让其他线程修改A变量后，把修改的值对当前线程可见
2.在写操作后插入StoreLoad屏障，这样就能让其他线程获取A变量的时候，能够获取到已经被当前线程修改的值
3.在每个volatile读操作前插入LoadLoad屏障，这样就能让当前线程获取A变量的时候，保证其他线程也都能获取到相同的值，这样所有的线程读取的数据就一样了
4.在读操作后插入LoadStore屏障;这样就能让当前线程在其他线程修改A变量的值之前，获取到主内存里面A变量的的值。

注意:volatile关键字只能对变量添加

2.解决有序性

有序性是指在保证程序运行正确的前提下,编译期CPU对指令进行重排序优化的过程.

用volatile修饰的变量,就是告诉编译器不要对这个变量涉及的操作进行重排序,从而解决了有序性的问题.

3.不能解决原子性

用以下代码进行验证

public class Demo22_Volatile2 {static Counter22 counter = new Counter22();public static void main(String[] args) {Thread thread1 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});Thread thread2 = new Thread(() -> {for (int i = 0; i < 50000; ++i) {counter.increment();}});thread1.start();thread2.start();try {thread1.join();thread2.join();} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(counter.count);}
}class Counter22 {public volatile int count = 0;public void increment() {count++;}}

打印结果:

 因此我们可以总结出volatile不可以解决原子性.

六.synchronized和volatile总结

下表展示了synchronized和volatile可以解决和不可以解决的问题,Y=可以解决,N=不可以解决

	原子性	可见性	有序性
synchronized	Y	Y	N
volatile	N	Y	Y

七.wait()和notify()

wait()和notify()方法是Object类中定义的方法,每个对象都会默认继承Object,所以每个类都可以使用wait()和notify()方法

1.wait()

wait()是让线程死等,此时线程的状态为WAITING

wait(long)是让线程等待一段时间,过了时间就不等了,过时不候,此时线程的状态为TIMED_WAITING

之前我们学习过join()方法也是等待一段时间,但是wait和join不一样,join是让调用方去等,wait是让执行方去等.

2.notify()

notify()和notifyAll()都是唤醒等待的线程

notify()只唤醒一个线程,并参与锁竞争.

notifyAll()一次性唤醒所有的进程,线程共同去参与锁竞争

3.wait()和notify()

我们创建两个线程,一个线程等待,让另一个线程唤醒前一个线程.

public class Demo23_Wait_Notify {private static Object locker = new Object();public static void main(String[] args) {Thread thread1 = new Thread(() -> {while (true) {System.out.println(Thread.currentThread() + ":wait方法之前");try {//等待资源,线程堵塞locker.wait();} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(Thread.currentThread() + ":wait方法之后");System.out.println("============================");// 等待一会try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}}, "t1");thread1.start();Thread thread2 = new Thread(() -> {while (true) {System.out.println(Thread.currentThread() + ":notify方法之前");locker.notify();System.out.println(Thread.currentThread() + ":notify方法之后");}}, "t2");thread2.start();}
}

打印结果:

 可以看到报了非法的监视器状态异常,一般是与synchronized相关.

做如下修改之后可以观察到正确的结果

public class Demo23_Wait_Notify {private static Object locker = new Object();public static void main(String[] args) throws InterruptedException {Thread thread1 = new Thread(() -> {while (true) {System.out.println(Thread.currentThread().getName() + ":wait方法之前");try {synchronized (locker) {//等待资源,线程堵塞locker.wait();}} catch (InterruptedException e) {throw new RuntimeException(e);}System.out.println(Thread.currentThread().getName() + ":wait方法之后");System.out.println("============================");}}, "t1");thread1.start();Thread thread2 = new Thread(() -> {while (true) {System.out.println(Thread.currentThread().getName() + ":notify方法之前");synchronized (locker) {//等待资源,线程堵塞locker.notify();}System.out.println(Thread.currentThread().getName() + ":notify方法之后");// 等待一会try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}}, "t2");thread2.start();}
}

打印的结果:

根据这个代码的内容和打印的结果我们不难看出线程1的synchronized在执行wait方法等待的时候,为什么线程2能够进入并且进行notify操作呢?synchronized方法在没有执行完代码块的时候不释放锁资源,其他的线程是不可以进入执行代码的,这我们上面看到的内容不一样,因此我们可以大胆的猜测,在wait和notify方法执行的时候会释放锁资源.

总结:从执行的结果可以看出,wait()和notify()方法执行后会释放锁资源.wait()和notify()要对于同一个锁搭配使用.

 面试题:说一下wait()和sleep()的区别

1.本质上都是让线程等待,但是两个方法没什么关系

2.wait()是Object类中定义的方法,sleep()是Thread类中定义的方法

3.wait()必须与synchronized搭配使用,调用之后会释放锁.sleep()只是让线程进入堵塞等待,和锁没有什么区别

八.Java中线程安全的类

1.线程安全的类

• Vector (不推荐使用)
• Stack
• HashTable (不推荐使用)
• ConcurrentHashMap
• StringBuffer

2.线程不安全的类

• ArrayList
• LinkedList
• HashMap
• TreeMap
• HashSet
• TreeSet
• StringBuilder