不说了，我要去多多了
这是学习Java的小姐姐第61篇原创文章
前言
去年年底面试了多多买菜，有图为证，现整理面经，希望各位不要觉得太迟（这该死的拖延症?）。
周日晚上8点视频面试的拼多多，结果人家全员加班中，办公室中都是人，所以大家去多多前还是思考下把。?
问题1.arraylist线程是否安全，具体体现在哪行？
答：线程不安全，具体表现新增元素的赋值操作elementData[size++]=e。
我们先来看下什么是线程的安全性：
线程安全就是多线程访问时对数据进行了加锁机制(乐观锁或悲观锁)，只有一个线程能够正常访问，其他线程不能进行访问直到该线程读取完。不会出现数据不一致或者数据污染。
线程不安全就是多线程访问时不提供数据访问保护，有可能出现多个线程先后更改数据，所以得到的数据是脏数据。
如图，AbstractList下面有两个类，一个是线程不安全ArrayList，另外一个是线程安全vector。
从源码的角度来看，因为Vector的方法前加了synchronized 关键字，也就是同步的意思，所以其是线程安全的。
所以我们看到这两个的区别：
Vector：线程安全，但是性能低。
ArrayList:线程不安全，但是性能高，高效。
所以自古鱼和熊掌不可兼得。
我们来看下具体的代码，从下图我们可以得出其添加元素时候的两步走：
1. 在 Items[Size] 的位置存放此元素；
2. 增大 Size 的值。
我们来思考下：
在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1，一切都是正常的；
而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0，此时size并没有加一，但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。
线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0，此时size也没有加1。然后线程A和线程B都继续运行，都增加 Size 的值，此时size等于2。
那好，现在我们发现问题了，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。
看下面的代码，在多线程并发情况下，提示了报错信息，程序报了并发修改异常ConcurrentModificationException，我们也可以通过看下ArrayList底层中add(）方法，是没有加锁的操作，当多个线程共享一份资源时，可能发生线程问题；arrayList的add()方法是没有加锁的。
public static void main(String[] args) throws InterruptedException {
List<Integer> list = new ArrayList<>();
ExecutorService threadPool = Executors.newFixedThreadPool(30);
for (int i = 1; i <= 30; i++) {
int finalI = i;
threadPool.execute(() -> {
list.add(finalI);
System.out.println(list);
});
}
threadPool.shutdown();
}
如果我们想要不报错，可以将list转化为线程安全的集合，使用Collections工具类的synchronizedList方法，来将其转化线程安全的。
public static void main(String[] args) throws InterruptedException {
List<Integer> list = Collections.synchronizedList(new ArrayList<>());
//此处只是案例demo,真实使用线程池不建议用这种方式创建
ExecutorService threadPool = Executors.newFixedThreadPool(30);
for (int i = 1; i <= 30; i++) {
int finalI = i;
threadPool.execute(() -> {
list.add(finalI);
System.out.println(list);
});
}
threadPool.shutdown();
}
问题2.hashmap为什么用红黑树，不要AVL树，或B+树？
答：因为AVL树比红黑树保持更加严格的平衡，是以更多旋转操作导致更慢的插入和删除为代价的树，B+树所有的节点挤在一起，当数据量不多的时候会退化成链表。
AVL树
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
某在AVL树中查找通常更快，但这是以更多旋转操作导致更慢的插入和删除为代价的。因此，如果希望查找次数主导树的更新次数，请使用AVL树。
下面两张图都是平衡二叉搜索树。
那我们来看下不是平衡二叉搜索树长什么样子？从下图可以看到C节点的左子树有F，L，M，即为两层，但是C节点的右子树并没有，他们相差了2，所以并不是平衡二叉搜索树。
左子树的左子树插入结点 (左左)
右子树的右子树插入节点 (右右)
左子树的右子树插入节点 (左右)
右子树的左子树插入节点 (右左)
B+树
B+树的非叶子结点不存储数据，所以每个结点能存储的关键字更多。所以B+树更能应对大量数据的情况。jdk1.7中的HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。
如果用B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表
一个m阶的B树具有如下几个特征：
1.根结点至少有两个子女。
2.每个中间节点都至少包含ceil(m / 2)个孩子，最多有m个孩子。
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
问题3.ConcurrentHashMap为什么线程安全？哪些点保证了？
答：数组初始化的时候自旋来保证一定可以初始化成功，然后通过 CAS 设置 SIZECTL 变量的值，来保证同一时刻只能有一个线程对数组进行初始化，CAS 成功之后，还会再次判断当前数组是否已经初始化完成，如果已经初始化完成，就不会再次初始化；
新增槽点时通过自旋保证一定新增成功，然后通过CAS来新增，如果遇到槽点有值，通过锁住当前槽点或红黑树的根节点；
扩容时通过锁住原数组的槽点，设置转移节点，以及自旋等操作来保证线程安全。
ConcurrentHashMap 在 put 方法上的整体思路：
1. 如果数组为空，初始化，初始化完成之后，走 2； 2. 计算当前槽点有没有值，没有值的话，cas 创建，失败继续自旋（for 死循环），直到成功，槽点有值的话，走 3； 3. 如果槽点是转移节点(正在扩容)，就会一直自旋等待扩容完成之后再新增，不是转移节点走4； 4. 槽点有值的，先锁定当前槽点，保证其余线程不能操作，如果是链表，新增值到链表的尾部，如果是红黑树，使用红黑树新增的方法新增； 5. 新增完成之后 check 需不需要扩容，需要的话去扩容。
具体源码如下：
final V putVal (K key, V value,boolean onlyIfAbsent){
if (key == null || value == null) throw new NullPointerException();
//通过hashcode计算 hash
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
//table为空，进行初始化工作，调用initTable
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果当前索引位置没有值，直接创建
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//cas 在 i 位置创建新的元素，当 i 位置是空时，即能创建成功，结束 for 自循，否则继续自旋
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//如果当前槽点是转移节点，表示该槽点正在扩容，就会一直等待扩容完成
//转移节点的 hash 值是固定的，都是 MOVED
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//槽点上有值的
else {
V oldVal = null;
//锁定当前槽点，其余线程不能操作，保证了安全
synchronized (f) {
//这里再次判断 i 索引位置的数据没有被修改
//binCount 被赋值的话，说明走到了修改表的过程里面
if (tabAt(tab, i) == f) {
//链表
if (fh >= 0) {
binCount = 1;
for (Node<K, V> e = f; ; ++binCount) {
K ek;
//值有的话，直接返回
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K, V> pred = e;
//把新增的元素赋值到链表的最后，退出自旋
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
//红黑树，这里没有使用 TreeNode,使用的是 TreeBin，TreeNode 只是红黑树的一个节点
//TreeBin 持有红黑树的引用，并且会对其加锁，保证其操作的线程安全
else if (f instanceof TreeBin) {
Node<K, V> p;
binCount = 2;
//满足 if 的话，把老的值给 oldVal
//在 putTreeVal 方法里面，在给红黑树重新着色旋转的时候
//会锁住红黑树的根节点
if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
//binCount 不为空，并且 oldVal 有值的情况，说明已经新增成功了
if (binCount != 0) {
// 链表是否需要转化成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
//这一步几乎走不到。槽点已经上锁，只有在红黑树或者链表新增失败的时候
//才会走到这里，这两者新增都是自旋的，几乎不会失败
break;
}
}
}
//check 容器是否需要扩容，如果需要去扩容，调用 transfer 方法去扩容
//如果已经在扩容中了，check 有无完成
addCount(1L, binCount);
return null;
}
数组初始化时的线程安全
数组初始化时，首先通过自旋来保证一定可以初始化成功，然后通过 CAS 设置 SIZECTL 变量的值，来保证同一时刻只能有一个线程对数组进行初始化，CAS 成功之后，还会再次判断当前数组是否已经初始化完成，如果已经初始化完成，就不会再次初始化，通过自旋 + CAS + 双重 check等手段保证了数组初始化时的线程安全，源码如下：
//初始化 table，通过对 sizeCtl 的变量赋值来保证数组只能被初始化一次
private final Node<K, V>[] initTable () {
Node<K, V>[] tab;
int sc;
//通过自旋保证初始化成功
while ((tab = table) == null || tab.length == 0) {
// 小于 0 代表有线程正在初始化，释放当前 CPU 的调度权，重新发起锁的竞争
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// CAS 赋值保证当前只有一个线程在初始化，-1 代表当前只有一个线程能初始化
// 保证了数组的初始化的安全性
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 很有可能执行到这里的时候，table 已经不为空了，这里是双重 check
if ((tab = table) == null || tab.length == 0) {
// 进行初始化
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
}
新增槽点值时的线程安全
此时为了保证线程安全，做了四处优化：
- 通过自旋死循环保证一定可以新增成功。
- 当前槽点为空时，通过 CAS 新增。
- 当前槽点有值，锁住当前槽点。
- 红黑树旋转时，锁住红黑树的根节点，保证同一时刻，当前红黑树只能被一个线程旋转
扩容中时的线程安全
- 拷贝槽点时，会把原数组的槽点锁住；
- 拷贝成功之后，会把原数组的槽点设置成转移节点，这样如果有数据需要 put 到该节点时，发现该槽点是转移节点，会一直等待，直到扩容成功之后，才能继续 put，可以参考 put 方 法中的 helpTransfer 方法；
- 从尾到头进行拷贝，拷贝成功就把原数组的槽点设置成转移节点。
- 等扩容拷贝都完成之后，直接把新数组的值赋值给数组容器，之前等待 put 的数据才能继续 put。
// 扩容主要分 2 步，第一新建新的空数组，第二移动拷贝每个元素到新数组中去
// tab：原数组，nextTab：新数组
private final void transfer (Node < K, V >[]tab, Node < K, V >[]nextTab){
// 老数组的长度
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果新数组为空，初始化，大小为原数组的两倍，n << 1
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
// 新数组的长度
int nextn = nextTab.length;
// 代表转移节点，如果原数组上是转移节点，说明该节点正在被扩容
ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
// 无限自旋，i 的值会从原数组的最大值开始，慢慢递减到 0
for (int i = 0, bound = 0; ; ) {
Node<K, V> f;
int fh;
while (advance) {
int nextIndex, nextBound;
// 结束循环的标志
if (--i >= bound || finishing)
advance = false;
// 已经拷贝完成
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// 每次减少 i 的值
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// if 任意条件满足说明拷贝结束了
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 拷贝结束，直接赋值，因为每次拷贝完一个节点，都在原数组上放转移节点，所以拷贝完成的节点的数据一定不会再发生变化。
// 原数组发现是转移节点，是不会操作的，会一直等待转移节点消失之后在进行操作。
// 也就是说数组节点一旦被标记为转移节点，是不会再发生任何变动的，所以不会有任何线程安全的问题
// 所以此处直接赋值，没有任何问题。
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
} else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
// 进行节点的拷贝
if (tabAt(tab, i) == f) {
Node<K, V> ln, hn;
if (fh >= 0) {
int runBit = fh & n;
Node<K, V> lastRun = f;
for (Node<K, V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
} else {
hn = lastRun;
ln = null;
}
// 如果节点只有单个数据，直接拷贝，如果是链表，循环多次组成链表拷贝
for (Node<K, V> p = f; p != lastRun; p = p.next) {
int ph = p.hash;
K pk = p.key;
V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K, V>(ph, pk, pv, ln);
else
hn = new Node<K, V>(ph, pk, pv, hn);
}
// 在新数组位置上放置拷贝的值
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
// 在老数组位置上放上 ForwardingNode 节点
// put 时，发现是 ForwardingNode 节点，就不会再动这个节点的数据了
setTabAt(tab, i, fwd);
advance = true;
}
// 红黑树的拷贝
else if (f instanceof TreeBin) {
// 红黑树的拷贝工作，同 HashMap 的内容，代码忽略
// 在老数组位置上放上 ForwardingNode 节点
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
问题4.刚才说到分布式锁，谈谈设计思路和方案
答：主要根据具体的业务场景展开描述（这边各个项目不一样，就不展开说了），主要是引入redis实现的分布式锁，应该保证互斥性（在任何时候只有一个客户端持有锁，使用setnx），不能死锁（设置过期时间），保证上锁和解锁是同一个客户端（设置不同的value值），业务时间太长，导致锁过期（设置看门狗，自动续锁），锁的重入性（使用redis的hset）。
如果在一个分布式系统中，我们从数据库中读取一个数据，然后修改保存，这种情况很容易遇到并发问题。因为读取和更新保存不是一个原子操作，在并发时就会导致数据的不正确。如果是单机应用，直接使用本地锁就可以避免。如果是分布式应用，应用部署在多个JVM中，没有办法控制，所以引入分布式锁来解决。
互斥性
127.0.0.1:6379> setnx lock value1 #在键lock不存在的情况下，将键key的值设置为value1
(integer) 1
127.0.0.1:6379> setnx lock value2 #试图覆盖lock的值，返回0表示失败
(integer) 0
127.0.0.1:6379> get lock #获取lock的值，验证没有被覆盖
"value1"
127.0.0.1:6379> del lock #删除lock的值，删除成功
(integer) 1
127.0.0.1:6379> setnx lock value2 #再使用setnx命令设置，返回0表示成功
(integer) 1
127.0.0.1:6379> get lock #获取lock的值，验证设置成功
加锁：使用setnx key value命令，如果key不存在，设置value(加锁成功)。如果已经存在lock(也就是有客户端持有锁了)，则设置失败(加锁失败)。
解锁：使用del命令，通过删除键值释放锁。
不能死锁
设置过期时间，到点数据删除，避免导致如果一个客户端持有锁的期间突然崩溃了，就会导致无法解锁，则其他人将无法拿到该锁，锁会一直存在，最终导致出现死锁的现象。
锁过期
有效时间设置多长，假如我的业务操作比有效时间长，我的业务代码还没执行完就自动给我解锁了，不就完蛋了吗。
这个问题就有点棘手了，在网上也有很多讨论，第一种解决方法就是靠程序员自己去把握，预估一下业务代码需要执行的时间，然后设置有效期时间比执行时间长一些，保证不会因为自动解锁影响到客户端业务代码的执行。但是这并不是万全之策，比如网络抖动这种情况是无法预测的，也有可能导致业务代码执行的时间变长，所以并不安全。有一种方法比较靠谱一点，
就是给锁续期。在Redisson框架实现分布式锁的思路，就使用watchDog机制实现锁的续期。当加锁成功后，同时开启守护线程，默认有效期是30秒，每隔10秒就会给锁续期到30秒，只要持有锁的客户端没有宕机，就能保证一直持有锁，直到业务代码执行完毕由客户端自己解锁，如果宕机了自然就在有效期失效后自动解锁。
保证上锁和解锁都是同一个客户端
key的值可以根据业务设置，比如是用户中心使用的，可以命令为USER_REDIS_LOCK，value可以使用uuid保证唯一，用于标识加锁的客户端，保证加锁和解锁都是同一个客户端。
每次解锁可以先判断锁的value是不是当前用户，如果是，说明可以解锁，如果不是，则不能解锁，会导致误解了其他人的锁。
锁的重入性
可重入锁意思是在外层使用锁之后，内层仍然可以使用，那么可重入锁的实现思路又是怎么样的呢？在Redisson实现可重入锁的思路，使用Redis的哈希表存储可重入次数，当加锁成功后，使用hset命令，value(重入次数)则是1。
解锁时，先判断可重复次数是否大于0，大于0则减一，否则删除键值，释放锁资源。
问题5.算法题
看到这算法题，我笑了，这不是力扣的第一题吗，哈哈哈，幸好刷过。简单方法大家都会写，暴力操作，但是性能有影响，但是评论区有为大神写的很巧妙，我就直接搬过来了。
题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解法：
这个解法并不是从题目计算答案，而是从答案出发，看需要什么数字。
public int[] twoSum(int[] nums, int target) {
int[] indexs = new int[2];
// 建立k-v ，一一对应的哈希表
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.length; i++){
if(hash.containsKey(nums[i])){
indexs[0] = i;
indexs[1] = hash.get(nums[i]);
return indexs;
}
// 将数据存入 key为补数 ，value为下标
hash.put(target-nums[i],i);
}
// // 双重循环 循环极限为(n^2-n)/2
// for(int i = 0; i < nums.length; i++){
// for(int j = nums.length - 1; j > i; j --){
// if(nums[i]+nums[j] == target){
// indexs[0] = i;
// indexs[1] = j;
// return indexs;
// }
// }
// }
return indexs;
}
腾讯云开发者
