1. 问：List 和 Set 都有什么区别？

分析：这种问题面试官一般想考察的都是你对这两种数据结构的了解，已经使用时候的选择依据，所以可以从数据结构和一些使用案例入手分别做个介绍

答：List，列表，元素可重复。常用的实现ArrayList和LinkedList，前者是数组方式来实现，后者是通过链表来实现，在使用选择的时候，一般考虑的是基本数据结构的特性，比如，数组读取效率较高，链表插入时效率较高。

Set，集合，特点就是存储的元素不可重复。常用是实现，是HashSet和TreeSet，分开来谈：

HashSet，底层实现是HashMap，存储时，把值存在key，而value统一存储一个object对象。排重的时候，是先通过对象的hashcode来判断，如果不相等，直接存储。如果相等，会再对key做equals判断，如果依然相等，不存储，如果不相等，则存入，我们知道，HashMap是数组+链表的基本结构，同样的，在HashSet中，也是通过同样的策略，存储在相同的数组位置下的链表中。

TreeSet，存入自定义对象时，对象需要实现Comparable接口，重写排序规则。使用场景一般是需要保证存储数据的有序和唯一性。底层数据结构是自平衡的二叉排序树（红黑树）

延伸：

1. 在说到HashMap时，可能会直接引到HashMap相关话题，我发现这个问题面试官非常喜欢问，可能是因为HashMap可聊的较多，也能很好的考验下应聘者对底层实现细节、源码阅读、刨根问底的态度。
2. 涉及到二叉树了，小端就遇到过一次问红黑树特性的，因为之前准备过，胸有成竹的啪啪啪正要一一道来呢，结果刚说到第二个特性，面试官就问：红黑树和普通的平衡二叉树有什么区别？当时一脸懵逼样…回来后赶紧补足，核心区别就是：红黑树也是二叉查找树的一种，二叉树需要通过自旋、或其他方式（比如红黑树还能通过变色）来保证平衡（否则就成了链表结构了，没有时间复杂度上的优势了），红黑树限定的条件相对来说比较宽松，也就是说在平衡的过程中，消耗相对较小。
3. 由于HashSet无序，为了实现有序的目的，又不想用其他数据结构，可以用LinkedHashSet。简要说明，同HashSet和HashMap关系一样，也是使用了一个LinkedHashMap，LinkedHashMap和普通的HashMap的区别就是，在原有数据结构之上，采用双向链表的形式将所有entry（注意，是前面讲过的数组+链表中的各个链表里的元素，做了连接）连起来，顺序就是entry的插入顺序，这样可以保证元素的迭代顺序和插入顺序相同（有序性）

2. HashMap 是线程安全的吗，为什么不是线程安全的?

分析：这种问题，既然面试官问起，肯定是在这方面有的聊的。这个问题，在多数情况下，能清晰、全面的描述出问题来龙去脉即可，很少有面试官真的拿一段源码来考。当然，作为应聘者，如果能理解的很透彻，再用简单的图边写边讲，作为补充，还是非常出彩的。

答：嗯，不是线程安全的。主要从两个方面来说：

• 在插入新数据的时候，多线程hash后的结果相同，插入位置也就会定位到数组的相同下标下的同一个链表中。在插入时，假如第二个线程在第一个线程插入的瞬间也插入，就可能会导致，覆盖前面插入的值。
• 第二个非线程安全的影响是在扩容的时候，扩容会把所有值重新hash，插入到新的扩容后的“数组+链表”结构中。可能会导致环状链表情况出现，这样在读取节点的next节点时，永不为空，也就是著名的扩容时CPU使用率100%情况。

延伸：

要做到心中有底，还是需要知其然知其所以然才行，所以，撸下源码好好想想，才能做到临阵不乱。

1. 建议好好看看源码，源码量不大，结构也比较清晰。
2. 针对环状链表的情况，我是看了别人写的图文并茂版的文章弄明白的，这里放上链接，供参考：HashMap高并发问题

3. 问：那你是用什么数据结构来作为替代，满足线程安全的场景要求呢？

分析：这里一般面试官想考察的是对ConcurrentHashMap的了解，但是也有个别情况，会涉及到HashTable，小端就吃过这方面的亏，明明可以一笔带过的小知识点，却由于准备不充分，而没能答完整。

答：在Java里，提供了以下数据结构，可以解决线程安全问题：

• HashTable，实现原理是通过Synchronize同步锁来把读写方法都加锁的方式。虽然线程安全了，但是效率低下，只要有读写，就不能做其他操作。
• SynchronizedMap（涉及较少，了解即可），有条件的同步，是Collections类提供的一个方法返回的HashMap的多线程版本。实现是把基本的方法都加了同步锁。
• ConcurrentHashMap（重头戏）：根据jdk版本不同，实现也有差别。

java8以前，是用segment（锁住map一段实现，默认是16段也就是可以并发数支持到16，也可自定义。读不受影响），数据结构为数组(segment)+数组(entry)+链表，适用于读多写少的场景。提供原子操作putIfAbsent()（没有则添加）。segment继承自ReentrantLock，来作为锁。

java8，元素结构为Node（实现Entry接口），数据结构为数组+链表；直接对Node进行加锁，粒度更小。当链表长度大于8，转换为红黑树,当然在转换前，先看下数组长度，如果小于64，那先通过扩容来实现；插入元素时，如果该位置为null，用CAS插入；如果不为null，则加Synchronize锁插入到链表；

扩展：

• 我们看到，数组的默认长度都是16，那么这个数字有什么深意吗？有！做运算时效率高！属于取巧的设计。一个是扩容的时候，直接向左位操作，移一位，扩张为二倍；二是hash取模的时候，hash值是32位，右移28位，剩高四位，然后与这个length-1也就是15（1111）按位与操作，使数据均匀分布。
• ConcurrentHashMap在获取size时候是怎么计算的呢？

1.7size(),先获取segment的大小，然后判断是否修改过，如果是，在加锁重新获取segment大小，然后把所有segment大小加在一起；
1.8size()的实现是用一个volatile 变量来做CAS修改，如果高并发，还会把部分值存到一个volatile数组。取值时，把这两部分的值加在一起。mappingcount()方法和size()方法实现方式一样

• hashmap可以使用null作为key和value，存储于table数组第一个节点；hashtable不允许key和value为null.（这个在一个小公司被面试官问倒了，汗颜）
• 了解一些其他的数据结构：

• ConcurrentSkipListMap 数据有序
• ConcurrentSkipListSet 能去重

• hashset是用hashmap实现，内部存的是key，所有的value都是同一个object

1. 问：请谈谈你对ThreadLocal的理解。

分析：在多线程环境下，我们经常遇到这样的场景：维护一个全局变量。如果要保证变量值的正确性（或者说变量值修改的原子性），需用什么方式来实现呢？是的，对修改代码加锁可以实现，保证了在同一时刻只有一个线程来修改该变量值。办法当然不止一种，并发包AtomicXXX一样能达到这个效果，原理，差不多，无非是通过锁来实现并发。那么还有没有其他思路呢？有，ThreadLocal，实现思路可谓是另辟蹊径。

答：每个线程，都会有一个Map（ThreadLocalMap），用来存储以我们定义的ThreadLocal对象为key，以我们自定义的值为value的 名值对。而这个Map，是来自于我们写的多线程程序继承的父线程Thread。以此机制，保证了多线程间该变量值的隔离。

看下源码，以get()方法为切入口：

public T get() {
	Thread t = Thread.currentThread();
	ThreadLocalMap map = getMap(t);
	if (map != null) {
		ThreadLocalMap.Entry e = map.getEntry(this);
		if (e != null) {
			@SuppressWarnings("unchecked")
			                  T result = (T)e.value;
			return result;
		}
	}
	return setInitialValue();
}

重点是第三行，当前线程作为参数传入，我们来看下getMap(t)做了什么？

ThreadLocalMap getMap(Thread t) {
	return t.threadLocals;
}

是的，拿到当前线程对象的threadLocals对象，我们可以通过方法返回值推断，是一个ThreadLocalMap类型的对象。那么这个对象在哪定义的呢？继续看源码：

public class Thread implements Runnable {
	......
	     ThreadLocal.ThreadLocalMap threadLocals = null;
	......
}

很明显，是在Thread类里定义。

扩展：内存泄漏问题。

ThreadLocal对象是弱引用。在GC时，会直接回收。这种情况下，Map中的key为null，value值还在，无法得到及时的释放。目前的策略是在调用get、set、remove等方法时，会启动回收这些值。但是如果一直没调用呢？嗯，很容易就导致内存泄漏了。当然，并不能因为此就认为是弱引用导致的内存泄露，而应该是，设计的这个变量存储机制，导致了泄露。所以在使用的时候，要及时释放（通过以上描述，你肯定已经想到怎么合理释放了吧？）

1. 问：请你说下对Valotile的了解，以及使用场景。

分析：多线程编程，我们要解决的问题集中在三个方面：

• 原子性：最简单的例子就是，i++,在多线程环境下，最终的结果是不确定的，为什么？就是因为这么一个++操作，被编译为指令 后，是多个指令来完成的。那么遇到并发的情况，就会导致彼此“覆盖”的情况。
• 可见性：通俗解释就是，在A线程对一个变量做了修改，在B线程中，能正确的读取到修改后的结果。究其原理，是cpu不是直 接 和系统内存通信，而是把变量读取到L1，L2等内部的缓存中，也叫作私有的数据工作栈。修改也是在内部缓存中，但是何时同步到系统内存是不能确定的，有了这个时间差，在并发的时候，就可能会导致，读到的值，不是最新值。
• 有序性：这里只说指令重排序，虚拟机在把代码编译为指令后执行，出于优化的目的，在保证结果不变的情况下，可能会调整指 令的执行顺序。

答：valotile，能满足上述的可见性和有序性。但是无法保证原子性。

• 可见性，是在修改后，强制把对变量的修改同步到系统内存。而其他cpu在读取自己的内部缓存中的值的时候，发现是valotile修饰 的，会把内部缓存中的值，置为无效，然后从系统内存读取。
• 有序性，是通过内存屏障来实现的。所谓的内存屏障，可以理解为，在某些指令中，插入屏障指令，用以确保，在向屏障指令后面 继续执行的时候，其前面的所有指令已经执行完毕。

扩展：在写单例模式时，我们通常会采用双层判断的方式，在最内层：

instance = new Singleton()

其实这也有一个隐含的问题：这句赋值语句，其实是分三步来操作的：

• 为instance分配内存
• 调用Singleto构造函数来初始化变量
• instance指向上一步初始化的对象

在jvm做了指令重排序优化后，上述步骤b和c不能保证，可能出现，c先执行，但是对象却没初始化，这时候其他线程判断的时候，发现是非null，但是使用的时候，却没有具体实例，导致报错。所以，我们可以用valotile来修饰instance，避免该问题。

1. 问：你平时涉及到多线程编程多不多？谈谈你对Synchronized锁的理解

分析：多从实现原理，工作机制来描述

答：在多线程编程中，为了达到线程安全的目的，我们往往通过加锁的方式来实现。而Synchronized正是java提供给我们的非常重要的锁之一。它属于jvm级别加锁，底层实现是：在编译过程中，在指令级别加入一些标识来实现的。例如，同步代码块，会在同步代码块首尾加入monitorenter和monitorexit字节码指令，这两个指令都需要一个reference类型的参数，指明要加锁和解锁的对象，同步方法则是通过在修饰符上加acc_synchronized标识实现。在执行到这些指令（标识）时，本质都是获取、占有、释放monitor锁对象实现互斥，也就是说，同一时刻，只能有一个线程能成功的获取到这个锁对象。我们看一段加了synchronized关键字的代码编译后的字节码。编译前：

public class test {
  public test() {
  }
  public static void main(String[] args) {
    synchronized(new Object()){
        int i = 0;
    }
  }
}

编译后：

public class test extends java.lang.Object{
public test();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."":()V
   4:   nop
   5:   return

public static void main(java.lang.String[]);
  Code:
   0:   new     #2; //class Object
   3:   dup
   4:   invokespecial   #1; //Method java/lang/Object."":()V
   7:   dup
   8:   astore_1
   9:   monitorenter // Enter the monitor associated with object 
   10:  iconst_0
   11:  istore_2
   12:  nop
   13:  aload_1
   14:  monitorexit // Exit the monitor associated with object 
   15:  goto    23
   18:  astore_3
   19:  aload_1
   20:  monitorexit // Be sure to exit monitor... 
   21:  aload_3
   22:  athrow
   23:  nop
   24:  return
  Exception table:
   from   to  target type
   15    18   any
   21    18   any

}

重点关注14行，和20行。

在使用Synchronized时，用到的方法是wait和notify（或notifyAll），他们的原理是，调用wait方法后，线程让出cpu资源，释放锁，进入waiting状态，进入等待队列【第一个队列】。当有其他线程调用了notify或者notifyAll唤醒时，会将等待队列里的线程对象，移入阻塞队列【第二个队列】，状态是blocked，等待锁被释放后（这个释放时机，由虚拟机来决定，人为无法干预），开始竞争锁。

Synchronized无法中断正在阻塞队列或者等待队列的线程。

扩展：Synchronized提供了以下几种类型的锁：偏向锁、轻量级锁、重量级锁。在大部分情况下，并不存在多线程竞争，更常见的是一个线程多次获取同一个锁。那么很多的消耗，其实是在锁的获取与释放上。Synchronized一直在被优化，可以说Synchronized虽然推出的较早，但是效率并不比后来推出的Lock差。

偏向锁：在jdk1.6中引入，目的是消除在无竞争情况下的同步原语（翻译成人话就是，即使加了synchronized关键字，但是在没有竞争的时候，没必要去做获取-持有-释放锁对象的操作，提高程序运行性能）。怎么做呢？当锁对象第一次被线程A获取时，虚拟机会把对象头中的标志位设置为01，也就是代表偏向模式。同时把代表这个线程A的ID，通过CAS方式，更新到锁对象头的MarkWord中。相同的线程下次再次申请锁的时候，只需要简单的比较线程ID即可。以上操作成功，则成功进入到同步代码块。如果此时有其他线程B来竞争该锁，分两种情况做不同的处理：

• 如果线程A已执行完（并不会主动的修改锁对象的状态），会直接撤销锁对象的状态为未锁定，标志位为00；
• 如果线程A还在持有该锁，则锁升级为轻量级锁。

轻量级锁：也是JDK1.6中引入的，轻量级，是相对于使用互斥量的重量级锁来说的。线程发生竞争锁的时候，不会直接进入阻塞状态，而是先尝试做CAS修改操作，进入自旋，这个过程避免了线程状态切换的开销，不过要消耗cpu资源。详细过程是：

1. 线程尝试进入同步代码块，如果锁对象未被锁定，在当前线程对应的栈帧中，建立锁记录的空间，用于存储锁对象Mark Word的拷贝。
2. 然后JVM用CAS方式尝试将锁对象的MarkWord内容替换为指向前述“锁记录”的指针。如果成功，当前线程则持有了锁，处于轻量级锁定状态；如果失败，会首先检查当前MarkWord是否已经指向当前线程栈帧的“锁记录”，如果是，就说明当前线程已经拥有了这个锁，直接重入即可。否则就表明是其他线程持有锁，那么进入自旋（其实就是重试CAS修改操作）。
3. 释放锁时，是使用CAS来讲MarkWord和“锁记录”里的内容互换。如果成功，成功释放；如果事变，表明当前锁存在竞争（被其他线程修改了MarkWord里的数据），此时，锁会升级为重量级锁。

重量级锁：也就是我们使用的互斥量方式实现的锁，当存在多线程竞争时，只要没拿到锁，就会进入阻塞状态，主要消耗是在阻塞-唤起-阻塞-唤起的线程状态切换上。

上面介绍的三种类型的锁，是JVM来负责管理使用哪种类型锁，以及锁的升级（注意，没有降级）。

1. 问：你平时涉及到多线程编程多不多？谈谈你对Lock锁的理解

分析：最好对比着synchronized来讲

答：

在多线程编程中，为了达到线程安全的目的，我们往往通过加锁的方式来实现。Lock锁是java代码级别来实现的，相对于synchronizedd在功能性上，有所加强，主要是，公平锁，轮询锁，定时锁，可中断锁等，还增加了多路通知机制（Condition），可以用一个锁来管理多个同步块。另外在使用的时候，必须手动的释放锁。

详细分析：

• Lock锁的实现，主要是借助于队列同步器（我们常常见到的AQS）来实现。它包括一个int变量来表示状态；一个FIFO队列，来存储获取资源的排队线程。
• 当一个线程申请资源时，就是是获取当前的同步状态，并判断是否可符合预期，如果是，则通过CAS操作，来修改上述Int变量标识的同步状态。如果否，则线程进入队列排队（这是在一般情况，在使用tyrLock时，是直接返回获取锁失败）。

锁有独占锁和共享锁。独占锁就是在同一时刻，只允许同一个线程持有该锁；共享锁实现的时候和独占锁稍有不同，不是简单的修改同步状态（比如1和0），而是获取这个值，当值大于0时，即标识获取共享锁成功（隐含意思是每个线程获取锁成功后，这个值减1）。这里附上独占锁的实现源码（源码片段来自《java并发编程的艺术》，并加上自己的注释）：

public class Mutex implements Lock {  
  
    // 静态内部类，自定义同步器  
    private static class Sync extends AbstractQueuedSynchronizer{  
        // 该方法用于判断当前锁是否在独占模式下被占用状态  
        protected boolean isHeldExclusively(){  
            return getState() == 1;  
        }  
  
        // 获取锁!!! 
        public boolean tryAcquire(int acquires){ 
　　 　　     //典型的CAS原子操作，如果初始状态为0，可以获得锁
            if (compareAndSetState(0, 1)){  
                setExclusiveOwnerThread(Thread.currentThread());  
                return true;  
            }  
            return false;  
        }  
  
        //释放锁，将当前状态设置为0  
        protected boolean tryRelease(int releases){  
            if (getState() == 0){  
                throw new IllegalMonitorStateException();  
            }  
            setExclusiveOwnerThread(null);  
            setState(0);  
            return true;  
        }  
  
        // 返回一个Condition，每个condition都包含了一个condition队列 ，这个后续再说 
        Condition newCondition(){  
            return new ConditionObject();  
        }  
    }

• Lock锁中，支持可中断的锁，实现原理是，队列中的等待线程，可以响应其他线程发起的中断信号，抛出InterruptdException异常。
• 关于同步队列，需要了解，获取同步状态失败的线程，被包装为Node节点后，加入队列尾，这个操作是CAS操作，以保证线程安全，失败就死循环重试；而队列首节点，则是当前持有锁的线程。该节点一旦释放锁，会唤醒后继节点。
• 关于唤醒，是这样的，每个在同步队列中的阻塞线程，都处于自旋的状态，不断的尝试获取锁。这样，当首节点释放锁唤醒后继线程后，被唤醒的线程，还需要判断是否前继线程是首线程，是则获取同步状态（锁）成功。

扩展：Condition，多路通知机制

• 在Synchronized锁中，提供了wait、notify、notifyAll等方法，实现了等待/通知模式。那么在lock中，由Condition配合，也实现了类似的模式。
• 其实现实质是，一个Condition包含一个等待队列，定义多个Condition，那就有多个等待队列，和上文提到的同步队列配合使用。同步队列-等待队列模型请参

• 在上述模型中，调用await方法，相当于把同步队列首节点（持有锁的线程），移动到等待队列。调用signal方法唤醒阻塞的线程，则是将对应Condition等待队列里的首节点（等待时间最长），移入同步队列。
• 还有一点需要补充，就是线程的唤醒，调用signal可以正常唤醒；在其他线程中终止线程，也一样会唤醒，只不过唤醒后，只是抛出InterruptException异常。