[数据结构与算法]阿里巴巴java面试经验

前阵子面试了阿里巴巴java开发工程师的岗位，因为准备不充分一面就挂了，面试过后回顾了整个面试过程，记录了面试题目，基本包含了java开发相关的基础知识，在这里做一次分享。

面试题目：

1、hashmap get和put方法实现及扩容的过程

? get方法：

首先判断输入的key是否为空,如果为空,从hashmap数组下标为0的位置获取值返回

如果不为空,根据key的值,从hashmap数组中获取对应的entry对象,判断这个对象是否为空,为空返回null,不为空返回对应的value值, 获取value的方法中key为空和不为空时的方法里都先判断数组中的元素是否为0 ,如果不为0,才继续查找

put方法：

调用put方法的时候首先判断hashmap数组是否为空数组,如果为空,进行初始化,判断key的值是否是null,如果是null,把对应的value值存进数组中下标为0的位置,计算key的hash值,并计算出下标,遍历下标对应的链表,匹配hash值和key的值,如果存在,则覆盖,返回旧值，如果不存在,新添加一个,返回null，如果扩容,是先扩容之后再把数据添加进新扩容的数组中

扩容的过程：

如果数组中元素的容量超过阈值,会触发扩容,扩容是先把源数组放进一个临时数组中,获取老数组的长度,通过老数组长度乘2获取新数组长度,并创建新数组,把临时数组中的数据通过重新计算下表,存进扩容后的数组中.

2、concurrentHashMap

1.7 原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

3、锁synchronized和lock的区别

synchronized是Java提供的一种原子性性内置锁，Java每个对象都可以把它当做是监视器锁，线程代码执行在进入synchronized代码块时候会自动获取内部锁，这个时候其他线程访问时候会被阻塞到队列，直到进入synchronized中的代码执行完毕或者抛出异常或者调用了wait方法，都会释放锁资源。在进入synchronized会从主内存把变量读取到自己工作内存，在退出的时候会把工作内存的值写入到主内存，保证了原子性。

区别：

1. 来源：
   lock是一个接口，而synchronized是java的一个关键字，synchronized是内置的语言实现；
2. 异常是否释放锁：
   synchronized在发生异常时候会自动释放占有的锁，因此不会出现死锁；而lock发生异常时候，不会主动释放占有的锁，必须手动unlock来释放锁，可能引起死锁的发生。（所以最好将同步代码块用try catch包起来，finally中写入unlock，避免死锁的发生。）
3. 是否响应中断
   lock等待锁过程中可以用interrupt来中断等待，而synchronized只能等待锁的释放，不能响应中断；
4. 是否知道获取锁
   Lock可以通过trylock来知道有没有获取锁，而synchronized不能；
5. Lock可以提高多个线程进行读操作的效率。（可以通过readwritelock实现读写分离）
6. 在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源非常激烈时（即有大量线程同时竞争），此时Lock的性能要远远优于synchronized。所以说，在具体使用时要根据适当情况选择。
7. synchronized使用Object对象本身的wait 、notify、notifyAll调度机制，而Lock可以使用Condition进行线程之间的调度。

4、锁升级

大多数时候是不存在锁竞争的，常常是一个线程多次获得同一个锁，因此如果每次都要竞争锁会增大很多没有必要付出的代价，为了降低获取锁的代价，才引入的偏向锁；

线程2尝试去获取另一个线程的偏向锁的时候，这个时候偏向锁升级为轻量级锁，线程2自选等待锁的释放；

轻量级锁的情况下，自选次数达到限制比如10或者100，这时候又有线程来竞争这个锁，这个时候轻量级锁就会膨胀为重量级锁。

5、AOS的实现

AQS定义了一套多线程访问共享资源的同步器框架，许多同步类实现都依赖于它。

简单说，AQS记录了锁的持有线程，将等待锁的线程放入一个队列中，当锁被释放的时候，从队列中拿出最早的线程获取锁，等待执行的线程全部处于阻塞状态。

6、线程池的实现原理

当往线程池新增加一个线程时，首先判断核心线程数是否已满，如果不满则新创建一个线程执行，如果已满则判断队列是否已满，如果不满则添加进队列，如果已满则判断线程数量是否超过最大线程数，如果未超过则新创建线程执行，如果超过则根据配置的饱和策略处理。

7、mysql 索引实现 为什么用b+树

b+树单个节点可以存储多个数据，数据全部存储在叶子节点，节点之间有指针互相指向，便于范围查询。