7月15号上午11点30分要面试京东提前批，拿来牛客网牛友分享的面经，预热一下。学习过程中如有错误，欢迎私聊我纠正。
第一轮面试题
自我介绍
介绍一下快排
快排最好的时间复杂度为O(nlog2n) 最坏时间复杂度为O（n2）
第一轮：选出一个关键字（一般为第一个），最终结果为这个关键字处于中间位置，其左边元素小于关键字，右边元素大于关键字。
第二轮：以上一轮关键字为分割点，分别按照上述步骤进行左右两端的排序
…
最后一轮：输出
如何判断链表中有环
没有头结点的单链表，设置两个指针fast和slow，fast，slow从头结点开始往后走，每次走一步，同时fast从头结点开始往后走，每次走两步，这两个指针一直往后面走直到fast为空，则单链表无环，或者slow与fast相等，则单链表有环。
介绍HashMap
设置当前为capacity大小的entry数组，数组中的每一个元素代表一个桶。JDK8，新增默认为8的阈值，当一个桶里的entry超过阈值，就不一以单向链表存储而是以红黑树进行存放，加快key的查找速度。当默认entry的数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的entry。HashMap在jdk1.7中采用头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
什么时候转为红黑树
当前桶中entry的链表长度超过8时 就会自动转为红黑树；
介绍ConcurrentHashMap
JDK1.7 是由Segment数组、HashEntry组成，数组加链表。
Segment 数组，存放数据时首先需要定位到具体的 Segment 中，Segment 是 ConcurrentHashMap 的一个内部类。 原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
JDK1.8 是由Segment数组、Node节点，数组加链表+红黑树。
JDK1.8 抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
乐观锁悲观锁
乐观锁：CAS操作的就是乐观锁，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。这个过程也称为自旋
缺点：（1）CPU开销较大。在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很大的压力。
（2）不能保证代码块的原子性
CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用Synchronized了。
悲观锁：synchronized是悲观锁，这种线程一旦得到锁，其他需要锁的线程就挂起的情况就是悲观锁。
Synchronized虽然确保了线程的安全，但是在性能上却不是最优的，Synchronized关键字会让没有得到锁资源的线程进入BLOCKED状态，而后在争夺到锁资源后恢复为RUNNABLE状态，这个过程中涉及到操作系统用户模式和内核模式的转换，代价比较高。
悲观锁、乐观锁的应用场景
悲观锁：每次拿数据的时候都觉得数据会被人更改，所以拿数据的时候就把这条记录锁掉，这样别人就没法改这条数据，一直到你的锁释放。
乐观锁：用于写比较少的情况下，即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。
线程同步
在对共享数据加锁后，每个线程在访问共享数据时必须先申请相应的锁。一旦获得锁后，就可以访问共享数据，并且一个锁同一时刻只能被一个线程持有，这意味着获得锁后不会有其他线程再访问共享数据。访问共享数据结束后线程必须释放锁。锁的持有线程在其获得锁之后和释放锁之前这段时间内所执行的代码被称为临界区。因此，共享数据只允许在临界区内进行访问，临界区一次只能被一个线程执行。
如何实现一个生产者消费者模型，使用什么数据结构？
采用阻塞队列实现生产者消费者模式。
当队列元素已满的时候，阻塞插入操作；
当队列元素为空的时候，阻塞获取操作。
ArrayBlockingQueue 与 LinkedBlockingQueue都是支持FIFO(先进先出)，但是LinkedBlockingQueue是无界的，而ArrayBlockingQueue 是有界的。
