• 1. 集合回顾
  • 1.1 List
  • 1.2 Set
  • 1.3 Map
  • 1.4 HashMap与TreeMap的区别
• 2. HashMap底层原理分析
  • 2.1 HashMap定义
  • 2.2 红黑树
    • 2.2.1 概念
    • 2.2.2 特点
  • 2.3 HashMap底层代码解析
  • 2.4 存值put(K key,V value)
  • 2.5 取值get(Object key)
• 2.6 遍历方式
• 3. 多线程
  • 3.1 线程和进程介绍
    • 3.1.1 进程
    • 3.1.2 线程
  • 3.2 实现多线程的三种方式
  • 3.3 一个线程的生命周期
  • 3.4 线程同步
  • 3.5 线程通信
  • 3.6 线程安全的实现方法
  • 3.7 锁
    • 3.7.1 锁的类型和优化
    • 3.7.2 锁的一些概念
    • 3.7.3 synchronized的优化（jdk 1.6之后引入）
  • 3.8 ThreadLocal

1. 集合回顾

1.1 List

们用的比较多List包括ArrayList和LinkedList

1. ArrayList的底层的通过数组实现，所以其随机访问的速度比较快，但是对于需要频繁的增删的情况，效率就比较低了。
2. LinkedList的底层通过链表来实现，所以增删操作比较容易完成，但是对于随机访问的效率比较低。
3. Vector是ArrayList的线程安全版本。

1.2 Set

1. Set与List的主要区别：
   • Set是不允许元素重复的
   • List可以允许元素重复的。
2. 判断元素的重复需要根据对象的hash方法和equals方法来决定。这也是我们通常要为集合中的元素类重写hashCode方法和equals方法的原因。
3. TreeSet的区别在于其排序是按照Comparator来进行排序的，默认情况下按照字符的自然顺序进行升序排列。

1.3 Map

1. Map类型的集合最大的优点在于其查找效率比较高，理想情况下可以实现O(1)的时间复杂度。
2. LinkedHashMap与HashMap的区别在于前者能够保证插入集合的元素顺序与输出顺序一致。，LinkedHashMap与HashMap的区别在于前者能够保证插入集合的元素顺序与输出顺序一致。

1.4 HashMap与TreeMap的区别

1. HashSet与TreeSet的区别是一致的，HashSet和TreeSet本质上分别是通过HashMap和TreeMap来实现的，所以它们的区别自然也是相同的
2. HashTable现在已经很少使用了，与HashMap的主要区别是HashTable是线程安全的，不过由于其效率比较低，所以通常使用HashMap，在多线程环境下，通常用CurrentHashMap来代替。

2. HashMap底层原理分析

2.1 HashMap定义

1. 默认的初始容量是16
2. 当桶(bucket)上的结点数大于8时会转成红黑树
3. 当桶(bucket)上的结点数小于6时树转链表

注意：transient：java语言的关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程。

2.2 红黑树

2.2.1 概念

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

2.2.2 特点

1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色
3. 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4. 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。如果有删除或者插入节点,使用左旋和右旋;

2.3 HashMap底层代码解析

HashMap提供了4个构造函数：

1. HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
2. HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
3. HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
4. HashMap(Map<? extends K, ? extends V> m)：传入一个map以构造一个新的map，使用默认加载因子（0.75）。

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

2.4 存值put(K key,V value)

1. 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
5. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
7. 如果在遍历过程中找到 key 相同时直接退出遍历。
8. 如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
9. 最后判断是否需要进行扩容。

2.5 取值get(Object key)

1. 首先将 key hash 之后取得所定位的桶。
2. 如果桶为空则直接返回 null 。
3. 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
4. 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
5. 红黑树就按照树的查找方式返回值。
6. 不然就按照链表的方式遍历匹配返回值。
   从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logn)。

2.6 遍历方式

强烈建议使用EntrySet进行遍历。

涉及问题：

1. put过程是先计算hash然后通过hash与table.length取摸计算index值，然后将key放到table[index]位置，当table[index]已存在其它元素时，会在table[index]位置形成一个链表，将新添加的元素放在table[index]，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题，当元素数量达到临界值(capactiyfactor)时，则进行扩容，是table数组长度变为table.length2;
2. 如果通过hash运算计算出来的index值与数组中某个index值相同，说明此存储地址已经被其他元素所占有，这种现象称之为hash碰撞或hash冲突。
3. HashMap底层采用数组加链表加红黑树的方式，当存储地址index相同的时候，
4. 判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。
5. 如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果相同，这时就是产生了hash冲突。
6. Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。
7. 系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

3. 多线程

3.1 线程和进程介绍

进程是资源分配的最小单位，线程是程序执行的最小单位。

3.1.1 进程

进程是资源（CPU、内存等）分配的基本单位，它是程序执行时的一个实例。程序运行时系统就会创建一个进程，并为它分配资源，然后把该进程放入进程就绪队列，进程调度器选中它的时候就会为它分配CPU时间，程序开始真正运行。

3.1.2 线程

线程是程序执行时的最小单位，它是进程的一个执行流，是CPU调度和分派的基本单位，一个进程可以由很多个线程组成，线程间共享进程的所有资源，每个线程有自己的堆栈和局部变量。线程由CPU独立调度执行，在多CPU环境下就允许多个线程同时运行。同样多线程也可以实现并发操作，每个请求分配一个线程来处理。

3.2 实现多线程的三种方式

1. 继承Thread类
2. 实现Runnable接口
3. 使用ExecutorService、Callable、Future实现有返回结果的多线程

实现 Runnable 和 Callable 接口的类只能当做一个可以在线程中运行的任务，不是真正意义上的线程，因此最后还需要通过 Thread 来调用。可以说任务是通过线程驱动从而执行的。

实现接口 VS 继承 Thread:

1. Java 不支持多重继承，因此继承了 Thread 类就无法继承其它类，但是可以实现多个接口；
2. 类可能只要求可执行即可，继承整个 Thread 类开销会过大。

Thread和Runable的联系和区别

1. 联系
   • Thread类实现了Runable接口
   • 都需要重写里面Run方法
2. 区别
   • 实现Runnable的类更具有健壮性，避免了单继承的局限。
   • Runnable更容易实现资源共享，能多个线程同时处理一个资源

3.3 一个线程的生命周期

1. 新建状态:

   使用 new 关键字和 Thread 类或其子类建立一个线程对象后，该线程对象就处于新建状态。它保持这个状态直到程序 start() 这个线程。

2. 就绪状态:

   当线程对象调用了start()方法之后，该线程就进入就绪状态。就绪状态的线程处于就绪队列中，要等待JVM里线程调度器的调度。

3. 运行状态:

   如果就绪状态的线程获取 CPU 资源，就可以执行 run()，此时线程便处于运行状态。处于运行状态的线程最为复杂，它可以变为阻塞状态、就绪状态和死亡状态。

4. 阻塞状态:

   如果一个线程执行了sleep（睡眠）、suspend（挂起）等方法，失去所占用资源之后，该线程就从运行状态进入阻塞状态。在睡眠时间已到或获得设备资源后可以重新进入就绪状态。可以分为三种：

   • 等待阻塞：运行状态中的线程执行 wait() 方法，使线程进入到等待阻塞状态。
   • 同步阻塞：线程在获取 synchronized 同步锁失败(因为同步锁被其他线程占用)。
   • 其他阻塞：通过调用线程的 sleep() 或 join() 发出了 I/O 请求时，线程就会进入到阻塞状态。当sleep() 状态超时，join() 等待线程终止或超时，或者 I/O 处理完毕，线程重新转入就绪状态。

5. 死亡状态:

   一个运行状态的线程完成任务或者其他终止条件发生时，该线程就切换到终止状态。

产生线程阻塞的原因：

1. 调用 Thread.sleep() 方法进入休眠状态；
2. 通过 wait() 使线程挂起，直到线程得到 notify() 或 notifyAll() 消息（或者 java.util.concurrent 类库中等价的 signal() 或 signalAll() 消息；
3. 等待某个 I/O 的完成；
4. 试图在某个对象上调用其同步控制方法，但是对象锁不可用，因为另一个线程已经获得了这个锁。

3.4 线程同步

给定一个进程内的所有线程，都共享同一存储空间，这样有好处又有坏处。这些线程就可以共享数据，非常有用。不过，在两个线程同时修改某一资源时，这也会造成一些问题。Java 提供了同步机制，以控制对共享资源的互斥访问。

Synchronized关键字

1. synchronized是Java中的关键字，是一种同步锁。它修饰的对象有以下几种：
   • 修饰一个代码块，被修饰的代码块称为同步语句块，其作用的范围是大括号{}括起来的代码，作用的对象是调用这个代码块的对象；
   • 修饰一个方法，被修饰的方法称为同步方法，其作用的范围是整个方法，作用的对象是调用这个方法的对象；
   • 修饰一个静态的方法，其作用的范围是整个静态方法，作用的对象是这个类的所有对象；
   • 修饰一个类，其作用的范围是synchronized后面括号括起来的部分，作用主的对象是这个类的所有对象。
2. Synchronized的作用主要有三个：
   • 确保线程互斥的访问同步代码
   • 保证共享变量的修改能够及时可见 可见性
   • 有效解决重排序问题。有序性
3. Synchronized 原理
   Synchronized的语义底层是通过一个monitor的对象来完成，其实wait/notify等方法也依赖于monitor对象，这就是为什么只有在同步的块或者方法中才能调用wait/notify等方法，否则会抛出java.lang.IllegalMonitorStateException的异常的原因。

synchronized与Lock的区别

1. Lock的加锁和解锁都是由java代码实现的，而synchronize的加锁和解锁的过程是由JVM管理的。
2. synchronized能锁住类、方法和代码块，而Lock是块范围内的。
3. Lock能提高多个线程读操作的效率；
4. Lock：Lock实现和synchronized不一样，后者是一种悲观锁，它胆子很小，它很怕有人和它抢吃的，所以它每次吃东西前都把自己关起来。而Lock底层其实是CAS乐观锁的体现，它无所谓，别人抢了它吃的，它重新去拿吃的就好啦，所以它很乐观。底层主要靠volatile和CAS乐观锁操作实现的。

3.5 线程通信

wait()、notify()、notifyAll()它们都属于 Object 的一部分，而不属于 Thread。而 sleep() 是 Thread 的静态方法。只有在同步控制方法或同步控制块里才能调用 wait() 、notify() 和 notifyAll()。

1. wait()：会在等待时将线程挂起，而不是忙等待，并且只有在 notify() 或者 notifyAll() 到达时才唤醒。sleep() 和 yield() 并没有释放锁，但是 wait() 会释放锁。
2. 该方法用来通知那些可能等待该对象的对象锁的其他线程。如果有多个线程等待，则线程规划器任意挑选出其中一个 wait()状态的线程来发出通知，并使它等待获取该对象的对象锁。
3. 使所有原来在该对象上 wait 的线程统统退出 wait 的状态（即全部被唤醒，不再等待 notify 或 notifyAll，但由于此时还没有获取到该对象锁，因此还不能继续往下执行），变成等待获取该对象上的锁。

3.6 线程安全的实现方法

1. 互斥同步
   • 互斥同步（Mutual Exclusion＆Synchronization）是常见的一种并发正确性保障手段。同步是指在多个线程并发访问共享数据时，保证共享数据在同一个时刻只被一个（或者是一些，使用信号量的时候）线程使用。而互斥是实现同步的一种手段，临界区（Critical Section）、互斥量（Mutex）和信号量（Semaphore）都是主要的互斥实现方式。因此，在这 4 个字里面，互斥是因，同步是果；互斥是方法，同步是目的。在 Java 中，最基本的互斥同步手段就是 synchronized 关键字。
   • 除了 synchronized 之外，我们还可以使用 java.util.concurrent（下文称 J.U.C）包中的重入锁（ReentrantLock）来实现同步，在基本用法上，ReentrantLock 与 synchronized 很相似，他们都具备一样的线程重入特性，只是代码写法上有点区别，一个表现为 API 层面的互斥锁（lock() 和 unlock() 方法配合 try/finally 语句块来完成），另一个表现为原生语法层面的互斥锁。不过，相比 synchronized，ReentrantLock 增加了一些高级功能，主要有以下 3 项：等待可中断、可实现公平锁，以及锁可以绑定多个条件。
   • 等待可中断是指当持有锁的线程长期不释放锁的时候，正在等待的线程可以选择放弃等待，改为处理其他事情，可中断特性对处理执行时间非常长的同步块很有帮助。
   • 公平锁是指多个线程在等待同一个锁时，必须按照申请锁的时间顺序来依次获得锁；而非公平锁则不保证这一点，在锁被释放时，任何一个等待锁的线程都有机会获得锁。synchronized 中的锁是非公平的，ReentrantLock 默认情况下也是非公平的，但可以通过带布尔值的构造函数要求使用公平锁。
   • 锁绑定多个条件是指一个 ReentrantLock 对象可以同时绑定多个 Condition 对象，而在 synchronized 中，锁对象的 wait() 和 notify() 或 notifyAll() 方法可以实现一个隐含的条件，如果要和多于一个的条件关联的时候，就不得不额外地添加一个锁，而 ReentrantLock 则无须这样做，只需要多次调用 newCondition() 方法即可。
2. 非阻塞同步 乐观锁实现
   • 互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题，因此这种同步也称为阻塞同步（Blocking Synchronization）。从处理问题的方式上说，互斥同步属于一种悲观的并发策略，总是认为只要不去做正确的同步措施（例如加锁），那就肯定会出现问题，无论共享数据是否真的会出现竞争，它都要进行加锁（这里讨论的是概念模型，实际上虚拟机会优化掉很大一部分不必要的加锁）、用户态核心态转换、维护锁计数器和检查是否有被阻塞的线程需要唤醒等操作。随着硬件指令集的发展，我们有了另外一个选择：基于冲突检测的乐观并发策略，通俗地说，就是先进行操作，如果没有其他线程争用共享数据，那操作就成功了；如果共享数据有争用，产生了冲突，那就再采取其他的补偿措施（最常见的补偿措施就是不断地重试，直到成功为止），这种乐观的并发策略的许多实现都不需要把线程挂起，因此这种同步操作称为非阻塞同步（Non-Blocking Synchronization）。
3. 无同步方案
   • 要保证线程安全，并不是一定就要进行同步，两者没有因果关系。同步只是保证共享数据争用时的正确性的手段，如果一个方法本来就不涉及共享数据，那它自然就无须任何同步措施去保证正确性，因此会有一些代码天生就是线程安全的。
   • 可重入代码 （Reentrant Code）：这种代码也叫做纯代码（Pure Code），可以在代码执行的任何时刻中断它，转而去执行另外一段代码（包括递归调用它本身），而在控制权返回后，原来的程序不会出现任何错误。
   • 线程本地存储 （Thread Local Storage）：如果一段代码中所需要的数据必须与其他代码共享，那就看看这些共享数据的代码是否能保证在同一个线程中执行。如果能保证，我们就可以把共享数据的可见范围限制在同一个线程之内，这样，无须同步也能保证线程之间不出现数据争用的问题。比如Web 交互模型中的“一个请求对应一个服务器线程”（Thread-per-Request）的处理方式。
   • Java 语言中，如果一个变量要被多线程访问，可以使用 volatile 关键字声明它为“易变的”；如果一个变量要被某个线程独享，Java 中就没有类似 C++中 __declspec（thread）这样的关键字，不过还是可以通过 java.lang.ThreadLocal 类来实现线程本地存储的功能。

3.7 锁

3.7.1 锁的类型和优化

1. 在 java 中锁的实现主要有两类：内部锁 synchronized（对象内置的monitor锁）和显示锁java.util.concurrent.locks.Lock。
2. 在 java.util.concurrent.locks 包中有很多Lock的实现类，常用的有 ReentrantLock 和ReadWriteLock，其实现都依赖 java.util.concurrent.AbstractQueuedSynchronizer 类。

3.7.2 锁的一些概念

1. 可重入锁：

   指的是同一线程外层函数获得锁之后 ，内层递归函数仍然有获取该锁的代码，但不受影响，执行对象中所有同步方法不用再次获得锁。避免了频繁的持有释放操作，这样既提升了效率，又避免了死锁。

2. 自旋锁：

   所谓“自旋”，就是让线程去执行一个无意义的循环，循环结束后再去重新竞争锁，如果竞争不到继续循环，循环过程中线程会一直处于running状态，但是基于JVM的线程调度，会让出时间片，所以其他线程依旧有申请锁和释放锁的机会。自旋锁省去了阻塞锁的时间空间（队列的维护等）开销，但是长时间自旋就变成了“忙式等待”，忙式等待显然还不如阻塞锁。所以自旋的次数一般控制在一个范围内，例如10,100等，在超出这个范围后，自旋锁会升级为阻塞锁。

3. 公平锁：

   按等待获取锁的线程的等待时间进行获取，等待时间长的具有优先获取锁权利

4. 读写锁：

   对资源读取和写入的时候拆分为2部分处理，读的时候可以多线程一起读，写的时候必须同步地写。

5. 独占锁：

   是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。

6. 乐观锁：

   每次不加锁，假设没有冲突去完成某项操作，如果因为冲突失败就重试，直到成功为止。

3.7.3 synchronized的优化（jdk 1.6之后引入）

1. 偏向锁（无锁）：
   大多数情况下锁不仅不存在多线程竞争，而且总是由同一线程多次获得。偏向锁的目的是在某个线程获得锁之后（线程的id会记录在对象的Mark Word中），消除这个线程锁重入（CAS）的开销，看起来让这个线程得到了偏护。
2. 轻量级锁（CAS）：
   轻量级锁是由偏向锁升级来的，偏向锁运行在一个线程进入同步块的情况下，当第二个线程加入锁争用的时候，偏向锁就会升级为轻量级锁；轻量级锁的意图是在没有多线程竞争的情况下，通过CAS操作尝试将MarkWord更新为指向LockRecord的指针，减少了使用重量级锁的系统互斥量产生的性能消耗。
3. 重量级锁：
   虚拟机使用CAS操作尝试将MarkWord更新为指向LockRecord的指针，如果更新成功表示线程就拥有该对象的锁；如果失败，会检查MarkWord是否指向当前线程的栈帧，如果是，表示当前线程已经拥有这个锁；如果不是，说明这个锁被其他线程抢占，此时膨胀为重量级锁。

3.8 ThreadLocal

ThreadLocal 是解决线程安全问题一个很好的思路，它通过为每个线程提供一个独立的变量副本解决了变量并发访问的冲突问题。在很多情况下，ThreadLocal比直接使用synchronized同步机制解决线程安全问题更简单，更方便，且结果程序拥有更高的并发性。

1. ThreadLocal基础知识
   • 很多地方叫做线程本地变量，也有些地方叫做线程本地存储。ThreadLocal为变量在每个线程中都创建了一个副本，那么每个线程可以访问自己内部的副本变量。
   • ThreadLocal在每个线程中对该变量会创建一个副本，即每个线程内部都会有一个该变量，且在线程内部任何地方都可以使用，线程之间互不影响，这样一来就不存在线程安全问题，也不会严重影响程序执行性能。
   • Synchronized 用于线程间的数据共享，而 ThreadLocal 则用于线程间的数据隔离。
   • 初始容量16，负载因子2/3，解决冲突的方法是再hash法，也就是：在当前hash的基础上再自增一个常量进行哈希。
2. ThreadLocal原理
   • ThreadLocalMap中用于存储数据的entry定义，使用了弱引用，可能造成内存泄漏。
   • 当线程没有结束，但是ThreadLocal对象已经被回收，则可能导致线程中存在ThreadLocalMap的键值对，造成内存泄露。（ThreadLocal被回收，ThreadLocal关联的线程共享变量还存在）。解决办法：
     • 使用完线程共享变量后，显式调用ThreadLocalMap.remove方法清除线程共享变量
     • ThreadLocal定义为private static，这样ThreadLocal的弱引用问题则不存在0了。

ThreadLocal类提供的几个方法：

• public T get() { }
• public void set(T value) { }
• public void remove() { }
• protected T initialValue() { }

get()方法是用来获取ThreadLocal在当前线程中保存的变量副本，set()用来设置当前线程中变量的副本，remove()用来移除当前线程中变量的副本，initialValue()是一个protected方法，一般是用来在使用时进行重写的，它是一个延迟加载方法。

每个线程Thread内部有一个ThreadLocal.ThreadLocalMap类型的成员变量threadLocals，这个threadLocals就是用来存储实际的变量副本的，键值为当前ThreadLocal变量，value为变量副本（即T类型的变量）。

初始时，在Thread里面，threadLocals为空，当通过ThreadLocal变量调用get()方法或者set()方法，就会对Thread类中的threadLocals进行初始化，并且以当前ThreadLocal变量为键值，以ThreadLocal要保存的副本变量为value，存到threadLocals。
然后在当前线程里面，如果要使用副本变量，就可以通过get方法在threadLocals里面查找。
ThreadLocal配置多数据源