JAVA

锁

对象头MarkWord

线程在获取锁的时候，实际上就是获得一个监视器对象(monitor) ,monitor 可以认为是一个同步对象，所有的Java 对象是天生携带 monitor。

锁存在四种状态分别是：无锁、偏向锁、轻量级锁、重量级锁

悲观锁

Java中Synchronized和ReentrantLock等独占锁就是悲观锁思想实现的。

synchronized

synchronized是JVM内置锁，通过内部对象Monitor(监视器锁)来实现，基于进入与退出monitor对象来实现方法与代码块的同步，监视器锁的实现，最终依赖操作系统的Mutex lock(互斥锁)来实现。

四个特性

1. 原子性：保证被synchronized修饰的一个或者多个操作，在执行的过程中不会被任何的因素打断，即所谓的原子操作，直到锁被释放。
2. 可见性：保证持有锁的当前线程在释放锁之前，对共享变量的修改会刷新到主存中，并对其它线程可见。
3. 有序性：保证多线程时刻中只有一个线程执行，线程执行的顺序都是有序的。
4. 可重入性：保证在多线程中，有其他的线程试图竞争持有锁的临界资源时，其它的线程会处于等待状态，而当前持有锁的线程可以重复的申请自己持有锁的临界资源。

三种应用方式

• 修饰实例方法，作用于当前实例对象加锁，进入同步代码前要获得当前实例对象的锁
• 修饰静态方法，作用于当前类class对象加锁，进入同步代码前要获得当前类class对象的锁
  • 修饰代码块，指定加锁对象，对给定对象加锁，进入同步代码块前要获得给定对象的锁

synchronized的优化

在JVM的书籍中介绍到，synchronized在jdk6之前一直使用的是重量级锁，在jdk6之后便对其进行了优化，新增了偏向锁、轻量级锁（自旋锁），并通过锁消除、锁粗化、自旋锁、自适应自旋等方法使用于各种场景，大大提升了synchronized的性能。

偏向锁

当一个线程访问加了同步锁的代码块时，会在对象头中存储当前线程的 ID ，后续这个线程进入和退出这段加了同步锁的代码 块时，不需要再次加锁和释放锁。而是直接比较对象头里面是否存储了指向当前线程的偏向锁。如果相等表示偏向锁是偏向于当前线程的，就不需要再尝试获得锁了

偏向锁的撤销：偏向锁的撤销并不是把对象恢复到无锁可偏向状态，因为偏向锁并不存在锁释放的概念 而是在获取偏向锁的过程中，发现 cas 失败也就是存在线程竞争时，直接把被偏向的锁对象升级到被加了轻量级锁的状态 。

轻量级锁

轻量级锁在加锁过程中，用到了自旋锁。所谓自旋，就是指当有另外一个线程来竞争锁时，这个线程会在原地循环等待，而不是把该线程给阻塞，直到那个获得锁的线程释放锁之后，这个线程就可以马上获得锁的。注意，锁在原地循环的时候，是会消耗cpu 的，就相当于在执行一个啥也没有的 for 循环。

默认情况下自旋的次数是 10 次

自适应自旋锁

自适应意味着自旋的次数不是固定不变的，而是根据前一次在同一个锁上自旋的时间以及锁的拥有者的状态来决定。
如果在同一个锁对象上，自旋等待刚刚成功获得过锁，并且持有锁的线程正在运行中，那么虚拟机就会认为这次自旋也是很有可能再次成功，进而它将允许自旋等待持续相对更长的时间。如果对于某个锁，自旋很少成功获得过，那在以后尝试获取这个锁时将可能省略掉自旋过程，直接阻塞线程，避免浪费处理器资源

轻量级锁的解锁

轻量级锁的锁释放逻辑其实就是获得锁的逆向逻辑，通过CAS 操作把线程栈帧中的 Lock Record 替换回到锁对象的MarkWord 中，如果成功表示没有竞争。 如果失败，表示当前锁存在竞争，那么轻量级锁就会膨胀成为重量级锁。当轻量级锁膨胀到重量级锁之后，意味着线程只能被挂起阻塞来等待被唤醒了。

重量级锁的monitor

每一个JAVA 对象都会与一个监视器 monitor 关联，我们可以把它理解成为一把锁，当一个线程想要执行一段被synchronized 修饰的同步方法或者代码块时，该线程得先获取到 synchronized 修饰的对象对应的 monitor 。monitorenter表示去获得一个对象监视器。 monitorexit 表示释放 monitor 监视器的所有权，使得其他被阻塞的线程可以尝试去获得这个监视器。monitor依赖操作系统的 MutexLock( 互斥锁) 来实现的，线程被阻塞后便进入内核（ Linux ）调度状态，这个会导致系统在用户态与内核态之间来回切换，严重影响锁的性能

注意：wait/notify/notifyall 三个方法都必须在 synchronized 同步关键字所限定的作用域中调用，否则会报错java.lang.IllegalMonitorStateException ，意思是因为没有同步，所以线程对对象锁的状态是不确定的，不能调用这些方法。另外，通过同步机制来确保线程从wait 方法返回时能够感知到感知到 notify 线程对变量做出的修改。

ReentrantLock

重入锁指的是线程在获得锁之后，再次获取该锁不需要阻塞，而是直接关联一次计数器增加重入次数，重入锁的设计目的是避免线程的死锁。

ReentrantLock主要利用CAS+AQS队列来实现。它支持公平锁和非公平锁，两者的实现类似

ReentrantLock的基本实现可以概括为：先通过CAS尝试获取锁。如果此时已经有线程占据了锁，那就加入AQS队列并且被挂起。当锁被释放之后，排在CLH队列队首的线程会被唤醒，然后CAS再次尝试获取锁。在这个时候，如果：

非公平锁：如果同时还有另一个线程进来尝试获取，那么有可能会让这个线程抢先获取；

公平锁：如果同时还有另一个线程进来尝试获取，当它发现自己不是在队首的话，就会排到队尾，由队首的线程获取到锁。

以非公平锁为例，来看看lock 中的实现

1. 非公平锁和公平锁最大的区别在于，在非公平锁中我抢占锁的逻辑是，不管有没有线程排队，我先上来 cas 去抢占一下
2. CAS 成功，就表示成功获得了 锁
3. CAS 失败，调用 acquire(1) 走锁竞争逻辑

AQS

AbstractQueuedSynchronizer 抽象同步队列

是一个用于构建锁和同步容器的框架。事实上concurrent包内许多类都是基于AQS构建，例如ReentrantLock，Semaphore，CountDownLatch，ReentrantReadWriteLock，FutureTask等。AQS解决了在实现同步容器时设计的大量细节问题。

AQS使用一个FIFO的队列表示排队等待锁的线程，队列头节点称作“哨兵节点”或者“哑节点”，它不与任何线程关联。其他的节点与等待线程关联，每个节点维护一个等待状态waitStatus

AQS 的功能分为两种：独占和共享
独占锁：每次只能有一个线程持有锁，比如前面给大家演示的ReentrantLock 就是以独占方式实现的互斥锁
共享锁：允许多个线程同时获取锁，并发访问共享资源，比如ReentrantReadWriteLock

AQS的内部实现

AQS队列内部维护的是一个 FIFO 的双向链表，这种结构的特点是每个数据结构都有两个指针，分别指向直接后继节点和直接前驱节点。所以双向链表可以从任意一个节点开始很方便的访问前驱和后继。每个 Node 其实是由线程封装，当线程争抢锁失败后会封装成 Node 加入到 ASQ 队列中去，当获取锁的线程释放锁以后，会从队列中唤醒一个阻塞的节点线程 。

lock()与unlock()实现原理

可重入锁。可重入锁是指同一个线程可以多次获取同一把锁。ReentrantLock和synchronized都是可重入锁。

可中断锁。可中断锁是指线程尝试获取锁的过程中，是否可以响应中断。synchronized是不可中断锁，而ReentrantLock则提供了中断功能。

公平锁与非公平锁。公平锁是指多个线程同时尝试获取同一把锁时，获取锁的顺序按照线程达到的顺序，而非公平锁则允许线程“插队”。synchronized是非公平锁，而ReentrantLock的默认实现是非公平锁，但是也可以设置为公平锁。

乐观锁

乐观锁适用于多读的应用类型，这样可以提高吞吐量

版本号机制

一般是在数据表中加上一个版本号version字段，表示数据被修改的次数，当数据被修改时，version值会加一。当线程A要更新数据值时，在读取数据的同时也会读取version值，在提交更新时，若刚才读到的version值与当前数据库中的version值相等时才更新，否则重试更新操作，直到更新成功。

CAS算法

AtomicInteger工具类实现

即compare and swap（比较和互换），是一种有名的无锁算法。无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步。CAS算法涉及到3个操作数。
1、需要读写的内存值V
2、进行比较的值A
3、拟写入的新值B
当且仅当V的值等于A时，CAS通过原子方式用新值B来更新V的值，否则不会执行任何操作（比较和替换是一个原子操作）。一般情况下是一个自旋操作，即不断的重试。

自旋性能与ABA问题

CAS操作中我们可以看到AtomicInteger类中getAndAddInt方法的自旋操作，如果长时间自旋，那么肯定会对系统造成压力。而且如果value值从A->B->A,那么CAS就会认为这个值没有被操作过，这个称为CAS操作的”ABA”问题。
ABA问题：基于“值”的CAS乐观锁，可能导致ABA问题，应该由“值”比对，优化为“版本号”比对。

循环时间长开销大

自旋CAS（也就是不成功就一直循环执行直到成功）如果长时间不成功，会给CPU带来非常大的执行开销。

只能保证一个共享变量的原子操作

CAS 只对单个共享变量有效，当操作涉及跨多个共享变量时 CAS 无效。但是从 JDK 1.5开始，提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行 CAS 操作.所以我们可以使用锁或者利用AtomicReference类把多个共享变量合并成一个共享变量来操作。

volatile

volatile关键字是Java提供的一种轻量级同步机制。它能够保证可见性和有序性，但是不能保证原子性。

volatile变量的可见性

• 当对volatile变量执行写操作后，JMM会把工作内存中的最新变量值强制刷新到主内存
• 写操作会导致其他线程中的缓存无效

这样，其他线程使用缓存时，发现本地工作内存中此变量无效，便从主内存中获取，这样获取到的变量便是最新的值，实现了线程的可见性。

volatile变量的禁止指令重排序

volatile是通过编译器在生成字节码时，在指令序列中添加“内存屏障”来禁止指令重排序的。

内存屏障的作用可以通过防止CPU对内存的乱序访问来保证共享数据在多线程并行执行下的可见性。

JVM的实现会在volatile读写前后均加上内存屏障，在一定程度上保证有序性。

死锁的四个必要条件

1.互斥条件

2.请求与保持条件

3.不可剥夺条件

4.循环等待条件

避免死锁的方法：系统对进程发出每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,如果分配后系统可能发生死锁,则不予分配,否则予以分配，这是一种保证系统不进入死锁状态的动态策略。

线程

有三种创建线程的方式，分别是继承Thread 类、实现Runable 接口和使用线程池

线程池ThreadPoolExecutor

工作原理：线程池可以减少创建和销毁线程的次数，从而减少系统资源的消耗，

当一个任务提交到线程池时:

a. 首先判断核心线程池中的线程是否已经满了，如果没满，则创建一个核心线程执行任务，否则进入下一步

b. 判断工作队列是否已满，没有满则加入工作队列，否则执行下一步

c. 判断线程数是否达到了最大值，如果不是，则创建非核心线程执行任务，否则执行饱和策略，默认抛出异常

线程池的种类

1.FixedThreadPool:可重用固定线程数的线程池，只有核心线程，没有非核心线程，核心线程不会被回收，有任务时，有空闲的核心线程就用核心线程执行，没有则加入队列排队

2.SingleThreadExecutor:单线程线程池，只有一个核心线程，没有非核心线程，当任务到达时，如果没有运行线程，则创建一个线程执行，如果正在运行则加入队列等待，可以保证所有任务在一个线程中按照顺序执行，和FixedThreadPool的区别只有数量

3.CachedThreadPool:按需创建的线程池，没有核心线程，非核心线程有Integer.MAX_VALUE个，每次提交任务如果有空闲线程则由空闲线程执行，没有空闲线程则创建新的线程执行，适用于大量的需要立即处理的并且耗时较短的任务

4.ScheduledThreadPoolExecutor:继承自ThreadPoolExecutor,用于延时执行任务或定期执行任务，核心线程数固定，线程总数为Integer.MAX_VALUE

ThreadLocal

提供了一个线程范围的局部变量，是线程级别隔离的副本

ThreadLocalMap 通过哈希递增，黄金分割线，斐波那契散列

 private static final int HASH_INCREMENT = 0x61c88647;
static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;
    Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
    }
}

JVM

方法区：主要是存储类信息，常量池（static常量和static变量），编译后的代码（字节码）等数据
堆：初始化的对象，成员变量 （那种非static的变量），所有的对象实例和数组都要在堆上分配
虚拟机栈：栈的结构是栈帧组成的，调用一个方法就压入一帧，帧上面存储局部变量表，操作数栈，方法出口等信息，局部变量表存放的是8大基础类型加上一个应用类型，所以还是一个指向地址的指针
本地方法栈：主要为Native方法服务
程序计数器：记录当前线程执行的行号

堆里面的分区

堆里面分为新生代和老生代（java8取消了永久代，采用了Metaspace）

新生代包含Eden+Survivor区，survivor区里面分为from和to区，内存回收时，如果用的是复制算法，从from复制到to，当经过一次或者多次GC之后，存活下来的对象会被移动到老年区，当JVM内存不够用的时候，会触发Full GC，清理JVM老年区
当新生区满了之后会触发YGC，先把存活的对象放到其中一个Survice 区，然后进行垃圾清理。因为如果仅仅清理需要删除的对象，这样会导致内存碎 片，因此一般会把Eden 进行完全的清理，然后整理内存。那么下次GC 的时候， 就会使用下一个Survive，这样循环使用。如果有特别大的对象，新生代放不下， 就会使用老年代的担保，直接放到老年代里面。因为JVM 认为，一般大对象的存活时间一般比较久远。

堆的大小与比例

可以通过参数 –Xms、-Xmx 来指定

新生代 ( Young ) 与老年代 ( Old ) 的比例的值为 1:2 ( 可以通过参数 –XX:NewRatio 来指定 )

Eden : from : to = 8 : 1 : 1 ( 可以通过参数 –XX:SurvivorRatio 来设定 )

内存回收GC

GC算法

1.引用计数法

2.可达性算法(引用链法)

在java中，可作为GC Roots的对象 ：

（1）方法区中类静态属性引用的对象。
（2）方法区中的常量引用的对象。
（3）虚拟机栈（栈帧中的本地变量表）中引用的对象。
（4）本地方法栈中JNI（Native方法）引用的对象。

GC的三种收集方法

标记-清除、标记-整理、复制算法

现在的虚拟机垃圾收集大多采用这种方式，它根据对象的生存周期，将堆分为新生代和老年代。在新生代中，由于对象生存期短，每次回收都会有大量对象死去，那么这时就采用复制算法。老年代里的对象存活率较高，没有额外的空间进行分配担保，所以可以使用 标记-整理 或者 标记-清除。

java内存分配与回收策率以及Minor GC和Major GC

1.对象优先在堆的Eden区分配。

2.大对象直接进入老年代.

3.长期存活的对象将直接进入老年代. 当Eden区没有足够的空间进行分配时，虚拟机会执行一次Minor GC.Minor Gc通常发生在新生代的Eden区，在这个区的对象生存期短，往往发生Gc的频率较高，回收速度比较快;Full Gc/Major GC 发生在老年代，一般情况下，触发老年代GC的时候不会触发Minor GC,但是通过配置，可以在Full GC之前进行一次Minor GC这样可以加快老年代的回收速度。

新生代收集器：Serial、ParNew、Parallel Scavenge

老年代收集器：CMS、Serial Old、Parallel Old

整堆收集器： G1

CMS收集器

一种以获取最短回收停顿时间为目标的收集器。

特点：基于标记-清除算法实现。并发收集、低停顿。

应用场景：适用于注重服务的响应速度，希望系统停顿时间最短，给用户带来更好的体验等场景下。如web程序、b/s服务。

CMS收集器的运行过程分为下列4步：

初始标记：标记GC Roots能直接到的对象。速度很快但是仍存在Stop The World问题。

并发标记：进行GC Roots Tracing 的过程，找出存活对象且用户线程可并发执行。

重新标记：为了修正并发标记期间因用户程序继续运行而导致标记产生变动的那一部分对象的标记记录。仍然存在Stop The World问题。

并发清除：对标记的对象进行清除回收。

CMS收集器的内存回收过程是与用户线程一起并发执行的。

CMS收集器的工作过程图：

类的加载

类加载过程主要包含加载、验证、准备、解析、初始化、使用、卸载七个方面，下面一一阐述。

1.加载：获取定义此类的二进制字节流，生成这个类的java.lang.Class对象

2.验证：保证Class文件的字节流包含的信息符合JVM规范，不会给JVM造成危害

3.准备：准备阶段为变量分配内存并设置类变量的初始化

4.解析：解析过程是将常量池内的符号引用替换成直接引用

5.初始化：不同于准备阶段，本次初始化，是根据程序员通过程序制定的计划去初始化类的变量和其他资源。这些资源有static{}块，构造函数，父类的初始化等

6.使用：使用过程就是根据程序定义的行为执行

7.卸载：卸载由GC完成。

双亲委托模式的好处

1.避免重复加载，如果已经加载过一次Class，则不需要再次加载，而是直接读取已经加载的Class

2.更加安全，确保，java核心api中定义类型不会被随意替换，比如，采用双亲委托模式可以使得系统在Java虚拟机启动时旧加载了String类，也就无法用自定义的String类来替换系统的String类，这样便可以防止核心API库被随意篡改。

序列化

serialVersionUID

多类中，这个编号是唯一的。所以，由于没有显指定 serialVersionUID ，编译器又为我们生成了一个UID ，当然和前面保存在文件中的那个不会一样 了，于是就出现了 2 个序列化版本号不一致的错误。因此，只要我们自己指定了 se rialVersionUID ，就可以在序列化后，去添加一个字段，或者方法，而不会影响到后期的还原，还原后的对象照样可以使用，而且还多了方法或者属性可以用。

transient

transient关键字的作用是控制变量的序列化，在变量声明前加上该关键字，可以阻止该变量被序列化到文件中，在被反序列化后， transient 变量的值被设为初始值，如 int 型的是0 ，对象型的是 null 。

数据结构

Map

HashMap

HashMap<String, String> hashMap = new HashMap<>();
V put(K key, V value); // put后再初始化哈希表，默认16个
V get(Object key);
V remove(Object key);
V replace(K key, V value);
boolean containsKey(Object key);
// 遍历
for (String key : map.keySet()) {
	map.get(key);
}
for (Entry<String, String> entry : map.entrySet()) {
	entry.getKey();
	entry.getValue();
}
Iterator iter = map.entrySet().iterator(); // 效率高
while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
}
Iterator iter = map.keySet().iterator(); // 效率低
　　while (iter.hasNext()) {
　　Object key = iter.next();
　　Object val = map.get(key);
}

HashMap的底层实现是数组 + 链表 + 红黑树（JDK1.8增加了红黑树部分, 链表长度大于8转为红黑树)

int size; 用于记录HashMap实际存储元素的个数；(默认16)
float loadFactor; 负载因子（默认是0.75）当负载因子越大，则HashMap的装载程度就越高。也就是能容纳更多的元素，元素多了，发生hash碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。
int threshold; 下一次扩容时的阈值，达到阈值便会触发扩容机制resize（阈值 threshold = 容器容量 capacity * 负载因子 load factor）。
Node<K,V>[] table; 底层数组，充当哈希表的作用，用于存储对应hash位置的元素Node<K,V>，此数组长度总是2的N次幂。

Java7做了4次16位右位移异或混合，Java 8中这步已经简化了，只做一次16位右位移异或混合，而不是四次。自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。降低hash碰撞，

HashMap的容量为什么一定要是2的 n次方？

因为调用put(K key, V value)操作添加key-value键值对时，具体确定此元素的位置是通过 hash值 % 模上 哈希表Node<K,V>[] table的长度 hash % length 计算的。但是”模”运算的消耗相对较大，通过位运算h & (length-1)也可以得到取模后的存放位置，而位运算的运行效率高，但只有length的长度是2的n次方时，h & (length-1) 才等价于 h % length。而且当数组长度为2的n次幂的时候，不同的key算出的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

多线程下操作HashMap，由于存在扩容机制，当HashMap调用resize()进行自动扩容时，可能会导致死循环的发生。JDK1.7 头插入法 改为 JDK 1.8的尾插入法。

用HashMap时，最好选择不可变对象作为key。例如String，Integer等不可变类型作为key是非常明智的。
如果key对象是可变的，那么key的哈希值就可能改变。在HashMap中可变对象作为Key会造成数据丢失。因为我们再进行hash & (length - 1)取模运算计算位置查找对应元素时，位置可能已经发生改变，导致数据丢失。

HsahTable

容器整体结构

HashMap的key和value都允许为null，HashMap遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理。
Hashtable的key和value都不允许为null。Hashtable遇到null，直接返回NullPointerException。

容量设定与扩容机制

HashMap默认初始化容量为 16，并且容器容量一定是2的n次方，扩容时，是以原容量2倍的方式进行扩容。
Hashtable默认初始化容量为 11，扩容时，是以原容量2倍再加1的方式进行扩容。即int newCapacity = (oldCapacity << 1) + 1;。

散列分布方式（计算存储位置）

HashMap是先将key键的hashCode经过扰动函数扰动后得到hash值，然后再利用 hash & (length - 1)的方式代替取模，得到元素的存储位置。
Hashtable则是除留余数法进行计算存储位置的（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算），int index = (hash & 0x7FFFFFFF) % tab.length;。

线程安全（最重要）

HashMap 不是线程安全，如果想线程安全，可以通过调用synchronizedMap(Map<K,V> m)使其线程安全。但是使用时的运行效率会下降，所以建议使用ConcurrentHashMap容器以此达到线程安全。
Hashtable则是线程安全的，对整个哈希表加锁。每个操作方法前都有synchronized修饰使其同步，但运行效率也不高，所以还是建议使用ConcurrentHashMap容器以此达到线程安全。

因此，Hashtable是一个遗留容器，如果我们不需要线程同步，则建议使用HashMap，如果需要线程同步，则建议使用ConcurrentHashMap。

HashSet

boolean add(E e);
boolean contains(Object o)
boolean remove(Object o);
void clear();

（1）HashSet内部使用HashMap的key存储元素，以此来保证元素不重复；

（2）HashSet是无序的，因为HashMap的key是无序的；

（3）HashSet中允许有一个null元素，因为HashMap允许key为null；

（4）HashSet是非线程安全的；

（5）HashSet是没有get()方法的；

TreeMap

基于红黑树数据结构的实现。查看“键”或“键值对”时，它们会被排序(次序由Comparabel 或Comparator 决定)。TreeMap 的特点在于，你得到的结果是经过排序的。TreeMap 是唯一的带有subMap()方法的Map，它可以返回一个子树。适用于按自然顺序或自定义顺序遍历键(key)。

ArrayMap

ArrayMap 采用二分法查找；

添加数据时扩容时的处理不一样，进行了new 操作，重新创建对象，开销很大。ArrayMap 用的是copy 数据，所以效率相对要高。

ArrayMap 提供了数组收缩的功能，在clear 或remove 后，会重新收缩数组，是否空间

LinkedHashMap

LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的。同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序。

迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap 慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

WeakHashMap

WeakHashMap 继承于AbstractMap，实现了Map接口。和HashMap一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。不过WeakHashMap的键是“弱键”。在 WeakHashMap 中，当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。
原理： 通过WeakReference和ReferenceQueue实现的。

CoucurrentHashMap

1.7之前采用分段锁技术，只锁相关的bucket，不相关部分可以并发，提高了效率，但是是把map中的值重写到HashEntry[]中，不再是一个map， 另外也不会保持原先map中的顺序。 1.8之后，取消了分段锁的概念，采用CAS实现。在理想状态下，ConcurrentHashMap 可以支持 16 个线程执行并发写操作（如果并发级别设为16），及任意数量线程的读操作。

CoucurrentHashMap对列表中的头结点对象加锁，HsahTable对每个操作方法加锁，整个表加锁

SynchronizedHashMap

SynchronizedHashMap是采用全部加锁，相当于包装了一层，内部加完锁再调用hashmap，返回的也是一个SynchronizedMap 会保证原来map中的顺序

Array

SparseArray

SparseArray（稀疏数组）内部主要使用两个一维数组来保存数据，一个用来存key，一个用来存value，不需要额外的额外的数据结构，key为int的时候才能使用，注意是int而不是Integer，这也是sparseArray效率提升的一个点，去掉了装箱的操作。核心思想是通过二分查找来找到key对应的位置，然后取出值，或者插入值！

put：在插入的时候GrowingArrayUtils.insert()方法，可能因为空间不足需要扩容数组，再复制原数组到新的数组，在内部会调用growSize获取新的容量，一般情况下，新容量为当前容量的两倍

remove：移除键值对的时候，就会设置mGarbage = true，gc()其实不是真正意义上的java的gc，指的是从头遍历一遍，让后面的节点往前移动，顶替掉原有的DELETED的节点。

SparseBooleanArray，SparseIntArray，SparseLongArray

// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
    int lo = 0;
    int hi = size - 1;
    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1;
        final int midVal = array[mid];
        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    return ~lo;  // value not present
}

1. 返回结果是正数，表示查找得到，为对应的位置
2. 返回结果是负数，表示查找不到，但是对结果取反，得到元素待插入的位置，对put()操作可以避免再次查找

ArrayList

基于数组实现的，ArrayList 线程不安全。

boolean add(E e);
void add(int index, E element)
E get(int index);
E set(int index, E element);
E remove(int index);
boolean remove(Object o);
boolean contains(Object o);
addAll(int index, Collection<? extends E> c);
Object[] toArray();
void sort(Comparator<? super E> c); // 排序

LinkedList

实现了List接口的双向链表。实现了所有可选列表操作，并且可以存储所有类型的元素，包括null。

void addFirst(E element);
void addLast(E element);
E getFirst();
E getLast();
E removeFirst();
E removeLast();
boolean add(E e); //把元素e添加到链表末尾 
void add(int index, E element); //在指定索引处添加元素

除了add(int index, E element)外，时间复杂度均为O(1)，而add(int index, E element)的时间复杂度为O(N)。

List,Set,Map 的区别

Set 是最简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。

Set 接口主要实现了两个实现类：

HashSet： HashSet 类按照哈希算法来存取集合中的对象，存取速度比较快

TreeSet ：TreeSet 类实现了SortedSet 接口，能够对集合中的对象进行排序。

List 的特征是其元素以线性方式存储，集合中可以存放重复对象。

ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。

LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。

Stack & Queue

Stack

Stack<E> stack = new Stack();
E push(E item); // 把对象压入堆栈顶部
synchronized E pop(); // 移除堆栈顶部的对象，并返回该对象
synchronized E peek(); // 查看堆栈顶部的对象，但不从堆栈中移除它
boolean empty(); // 堆栈是否为空
synchronized int search(Object o); // 从后找元素,返回对象在堆栈中的位置，以 1 为基数。

Queue

boolean add(E e); // 将指定的元素插入此队列(可能无法插入元素，抛出IllegalStateException异常)
boolean offer(E e); // 将指定的元素插入此队列，插入成功返回 true；否则返回 false。
E remove(); // 获取并移除此队列的头，如果此队列为空，则抛出NoSuchElementException异常
E poll(); // 获取并移除此队列的头，如果此队列为空，则返回 null
E element(); // 获取队列的头但不移除此队列的头。如果此队列为空，则抛出NoSuchElementException异常
E peek(); // 获取队列的头但不移除此队列的头。如果此队列为空，则返回 null

interface Deque<E> extends Queue<E>
interface BlockingQueue<E> extends Queue<E> 
interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E>
class LinkedList<E> implements List<E>, Deque<E>
class ArrayDeque<E> implements Deque<E>
class ConcurrentLinkedDeque<E> implements Deque<E>
class LinkedBlockingQueue<E>implements BlockingQueue<E>
class ArrayBlockingQueue<E> implements BlockingQueue<E>
class SynchronousQueue<E> implements BlockingQueue<E>

Deque

Deque<String> deque = new ArrayDeque<>();
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
void push(E e);
E pop();

ConcurrentLinkedDeque

红黑树

1.root 节点和叶子节点是黑色
2.红色节点后必须为黑色节点
3.从root 到叶子每条路径的黑节点数量相同

设计模式

设计模式的六大原则

1、开闭原则（Open Close Principle）

开闭原则就是说对扩展开放，对修改关闭。在程序需要进行拓展的时候，不能去修改原有的代码，实现一个热插拔的效果。所以一句话概括就是：为了使程序的扩展性好，易于维护和升级。想要达到这样的效果，我们需要使用接口和抽象类。

2、里氏代换原则（Liskov Substitution Principle）

里氏代换原则(Liskov Substitution Principle LSP)面向对象设计的基本原则之一。 里氏代换原则中说，任何基类可以出现的地方，子类一定可以出现。 LSP是继承复用的基石，只有当衍生类可以替换掉基类，软件单位的功能不受到影响时，基类才能真正被复用，而衍生类也能够在基类的基础上增加新的行为。里氏代换原则是对“开-闭”原则的补充。实现“开-闭”原则的关键步骤就是抽象化。而基类与子类的继承关系就是抽象化的具体实现，所以里氏代换原则是对实现抽象化的具体步骤的规范。

3、依赖倒转原则（Dependence Inversion Principle）

这个是开闭原则的基础，具体内容：针对接口编程，依赖于抽象而不依赖于具体。

4、接口隔离原则（Interface Segregation Principle）

这个原则的意思是：使用多个隔离的接口，比使用单个接口要好。还是一个降低类之间的耦合度的意思，从这儿我们看出，其实设计模式就是一个软件的设计思想，从大型软件架构出发，为了升级和维护方便。所以上文中多次出现：降低依赖，降低耦合。

5、迪米特法则（最少知道原则）（Demeter Principle)

为什么叫最少知道原则，就是说：一个实体应当尽量少的与其他实体之间发生相互作用，使得系统功能模块相对独立。

6、合成复用原则（Composite Reuse Principle）

原则是尽量使用合成/聚合的方式，而不是使用继承。

设计模式的三大类

创建型模式(5种)：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。

结构型模式(7种)：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。

行为型模式(11种)：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。

手写单例模式

public class Singleton {
	private volatile static Singleton sInstance; 
	private Singleton() {}
	public static Singleton getInstance() {
		if (sInstance == null) {
			synchronized (Singleton.class) {
				if (sInstance == null) {
						sInstance = new Singleton();
				}
			}
		}
		return sInstance;
	}
}

注意volatile关键字的使用，保证了各线程对sInstance静态实例域修改的可见性。

泛型

泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。

可以看到，使用 Object 来实现通用、不同类型的处理，有这么两个缺点：

1. 每次使用时都需要强制转换成想要的类型
2. 在编译时编译器并不知道类型转换是否正常，运行时才知道，不安全

实际上引入泛型的主要目标有以下几点：

• 类型安全

• • 泛型的主要目标是提高 Java 程序的类型安全
  • 编译时期就可以检查出因 Java 类型不正确导致的 ClassCastException 异常
  • 符合越早出错代价越小原则

• 消除强制类型转换

• • 泛型的一个附带好处是，使用时直接得到目标类型，消除许多强制类型转换
  • 所得即所需，这使得代码更加可读，并且减少了出错机会

• 潜在的性能收益

• • 由于泛型的实现方式，支持泛型（几乎）不需要 JVM 或类文件更改
  • 所有工作都在编译器中完成
  • 编译器生成的代码跟不使用泛型（和强制类型转换）时所写的代码几乎一致，只是更能确保类型安全而已

泛型通配符和上下界的限定

? 通配符类型
<? extends T> 表示类型的上界，表示参数化类型的可能是T 或是 T的子类
<? super T> 表示类型下界（Java Core中叫超类型限定），表示参数化类型是此类型的超类型（父类型），直至Object