互联网科技Java成长之路Java架构技术进阶

2020金三银四冲击BAT必备面试题（上篇）：集合类+阻塞队列+

2019-12-19  本文已影响0人  程序员北游

一、集合类

1. ArrayList的扩容机制

  1. 每次扩容是原来容量的1.5倍，通过移位的方法实现。
  2. 使用copyOf的方式进行扩容。

扩容算法是首先获取到扩容前容器的大小。然后通过oldCapacity + (oldCapacity >> 1) 来计算扩容后的容器大小newCapacity。这里用到了>> 右移运算，即容量增大原来的1.5倍。还要注意的是，这里扩充容量时，用的时Arrays.copyOf方法,其内部也是使用的System.arraycopy方法。

区别：

2. 数组和ArrayList的区别

3. ArrayList和LinkedList的区别

4. 如何创建同步的List

可以通过Collections.sychronizeList将list转换成同步list,或者直接使用CopyOnWriteArrayList。

5. CopyOnWriteArrayList

6. Vector

ArrayList线程安全的一个版本，底层通过synchronize加锁实现线程安全。

7. HashMap扩容机制

HashMap使用resize()方法来进行扩容，计算table数组的新容量和Node在新数组中的新位置，将旧数组中的值复制到新数组中，从而实现自动扩容。

8. HashMap为什么不是线程安全的

9. 为什么HashMap的hashCode要高16位异或hashCode

因为元素所处位置只与低n位相关，高16位与hashcode进行异或是为了减少碰撞。

异或是两者相同返回0 不相同返回1。

10. 为什么HashMap的容量要是2的N次幂

2^n下有特性：x%2^n=x&(2^n-1)只有2的幂次方才有此特性。

11. ConcurrentHashMap的实现

12. ConcurrentHashMap1.7与1.8异同

13. 为什么ConcurrentHashMap读操作不加锁

14. LinkedHashMap的实现

基于hashMap和双向链表实现的，线程不安全。

15. HashSet的实现

16. TreeMap的实现

底层使用红黑树实现。根据键值进行排序，key必须实现Compareable接口或者构造TreeMap时传入Comparetor。

17. TreeSet的实现

底层使用TreeMap实现，即使用红黑树进行实现。
Set判断两个元素是否相等，先判断hashCode再使用equals

18. 解决Hash冲突的方法

19. List、Map、Set存储的null值

20. 平衡二叉树AVL与红黑树的区别

红黑树定义：

二. 阻塞队列

1. 五种阻塞队列介绍

2. poll和peek的区别

都用于取队列的头结点，poll会删除头结点，peek不会删除头结点。

3. LinkedBlockingQueue

3.1、功能

3.1.1、增加

增加有三种方式，前提：队列满

3.1.2、删除
删除有三种方式，前提：队列为空

3.2、简单分析

3.2.1、节点与属性

//链表节点内部类
static class Node<E> {
    //节点元素
    E item;
    Node<E> next;
    Node(E x) {
         item = x;
    }
}
//容量界限，如果未设定，则为Integer最大值
 private final int capacity;
//当前元素个数
private final AtomicInteger count = new AtomicInteger();
//链表的头：head.item == null
transient Node<E> head;
//链表的尾：last.next == null
private transient Node<E> last;
//take,poll等获取锁
private final ReentrantLock takeLock = new ReentrantLock();
//等待任务的等待队列
private final Condition notEmpty = takeLock.newCondition();
//put，offer等插入锁
private final ReentrantLock putLock = new ReentrantLock();
//等待插入的等待队列
private final Condition notFull = putLock.newCondition();

3.2.2、插入线程与获取线程的相互通知

signalNotEmpty()方法，在插入线程发现队列为空时调用，告知获取线程需要等待。
signalNotFull()方法,在获取线程发现队列已满时调用，告知插入线程需要等待。

//表示等待take。put/offer调用，否则通常不会锁定takeLock。
private void signalNotEmpty() {
    //获取takeLock
    final ReentrantLock takeLock = this.takeLock;
    //锁定takeLock
    takeLock.lock();
    try {
        //唤醒take线程等待队列
        notEmpty.signal();
    } finally {
       //释放锁
       takeLock.unlock();
    }
}
//表示等待put,take/poll 调用
private void signalNotFull() {
    //获取putLock
    final ReentrantLock putLock = this.putLock;
    //锁定putLock
    putLock.lock();
    try {
        //唤醒插入线程等待队列
        notFull.signal();
    } finally {
        //释放锁
        putLock.unlock();
    }
}

3.2.3、入队与出队操作

enqueue()方法只能在持有 putLock 锁下执行，dequeue()在持有 takeLock 锁下执行。

//在队列尾部插入
private void enqueue(Node<E> node) {
    // assert putLock.isHeldByCurrentThread();
    // assert last.next == null;
    //last.next指向当前node
    //尾指针后移
    last = last.next = node;
}
//移除队列头
private E dequeue() {
    // assert takeLock.isHeldByCurrentThread();
    // assert head.item == null;
    //保存头指针
    Node<E> h = head;
   //获取当前链表第一个元素
   Node<E> first = h.next;
   //头指针的next指向自己
   h.next = h; // help GC
   //头指针指向第一个元素
   head = first;
   //获取第一个元素的值
   E x = first.item;
   //将第一个元素的值置空
   first.item = null;
   //返回第一个元素的值
   return x;
}

3.2.4、对两把锁的加锁与释放

在需要对两把锁同时加锁时，把加锁的顺序与释放的顺序封装成方法，确保所有地方都是一致的。而且获取锁时都是不响应中断的，一直获取直到加锁成功，这就避免了第一把锁加锁成功，而第二把锁加锁失败导致锁不释放的风险。

//锁定putLock和takeLock
void fullyLock() {
    putLock.lock();
    takeLock.lock();
}
//与fullyLock的加锁顺序相反，先解锁takeLock，再解锁putLock
void fullyUnlock() {
    takeLock.unlock();
    putLock.unlock();
}

3.3、源码解读
简单介绍一下LinkedBlockingQueue中API的源码，如构造方法，新增，获取，删除，drainTo。

3.3.1、构造函数
LinkedBlockingQueue有三个构造方法，其中无参构造尽量少用，因为容量为Integer的最大值，操作不当会出现内存溢出。

public LinkedBlockingQueue() {
    this(Integer.MAX_VALUE);
}
public LinkedBlockingQueue(int capacity) {
    //参数校验
    if (capacity <= 0) throw new IllegalArgumentException();
    //设置容量
    this.capacity = capacity;
    //首尾节点指向一个空节点
    last = head = new Node<E>(null);
}
public LinkedBlockingQueue(Collection<? extends E> c) {
    this(Integer.MAX_VALUE);
    //获取putLock
    final ReentrantLock putLock = this.putLock;
    //锁定
    putLock.lock(); // Never contended, but necessary for visibility
    try {
        int n = 0;
        for (E e : c) {
            if (e == null)
                throw new NullPointerException();
            if (n == capacity)
                throw new IllegalStateException("Queue full");
            enqueue(new Node<E>(e));
            ++n;
        }
        count.set(n);
    } finally {
        putLock.unlock();
    }
}

3.3.2、offer(E e)

将给定的元素设置到队列中，如果设置成功返回true, 否则返回false。 e的值不能为空，否则抛出空指针异常。

//如果可以在不超过队列容量的情况下立即插入指定的元素到队列的尾部，成功后返回true，如果队列已满，返回false。当使用容量受限的队列时，此方法通常比方法BlockingQueue#add更可取，后者只能通过抛出异常才能插入元素。
public boolean offer(E e) {
    //非空判断
    if (e == null) throw new NullPointerException();
    //计数器
    final AtomicInteger count = this.count;
    //如果队列已满，直接返回插入失败
    if (count.get() == capacity)
        return false;
    int c = -1;
    //新建节点
    Node<E> node = new Node<E>(e);
    //获取插入锁
    final ReentrantLock putLock = this.putLock;
    //锁定
    putLock.lock();
    try {
        //如果队列未满
        if (count.get() < capacity) {
        //插入队列
        enqueue(node);
        //计数
        c = count.getAndIncrement();
        //还有空余空间
        if (c + 1 < capacity)
             //唤醒插入线程
             notFull.signal();
        }
    } finally {
        //解锁
        putLock.unlock();
    }
    //如果队列为空
    if (c == 0)
        //通知获取线程阻塞
        signalNotEmpty();
    //返回成功或者插入失败
    return c >= 0;
}

3.3.3、put(E e)

将元素设置到队列中，如果队列中没有多余的空间，该方法会一直阻塞，直到队列中有多余的空间。

public void put(E e) throws InterruptedException {
    //不可以插入空元素
    if (e == null) throw new NullPointerException();

    //所有put/take/etc中的约定都是预先设置本地var
    //除非设置，否则保持计数为负数表示失败。
    int c = -1;
    //新建节点
    Node<E> node = new Node<E>(e);
    //获取putLock
    final ReentrantLock putLock = this.putLock;
    //获取计数器
    final AtomicInteger count = this.count;
    //可中断加锁，即在锁获取过程中不处理中断状态，而是直接抛出中断异常，由上层调用者处理中断。
    putLock.lockInterruptibly();
    try {
        /*
        * 注意count在wait守卫线程中使用，即使它没有被锁保护。
        * 这是因为count只能在此时减少(所有其他put都被锁定关闭)，
        * 如果它从容量更改，我们(或其他一些等待put)将收到信号。
        * 类似地，count在其他等待守卫线程中的所有其他用途也是如此。
        */
        //只要当前队列已满
        while (count.get() == capacity) {
            //通知插入线程等待
            notFull.await();
        }
        //插入队列
        enqueue(node);
        //数量加1
        c = count.getAndIncrement();
        //如果队列增加1个元素还未满
        if (c + 1 < capacity)
            //唤醒插入进程
            notFull.signal();
    } finally {
        //解锁
        putLock.unlock();
    }
    //如果队列中没有元素了
    if (c == 0)
        //通知获取线程等待
        signalNotEmpty();
}

3.3.4、peek()

非阻塞的获取队列中的第一个元素，不出队列。

public E peek() {
    //队列为空，直接返回
    if (count.get() == 0)
        return null;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
        //获取第一个元素，非哨兵
        Node<E> first = head.next;
        //元素为空，返回null
        if (first == null)
            return null;
        else
            //返回第一个元素值
            return first.item;
    } finally {
        takeLock.unlock();
    }
}

3.3.5、poll()
非阻塞的获取队列中的值，未获取到返回null。

public E poll() {
    final AtomicInteger count = this.count;
    //队列为空，直接返回
    if (count.get() == 0)
        return null;
    E x = null;
    int c = -1;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
        //队列非空，获取队列中元素
        if (count.get() > 0) {
            x = dequeue();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        }
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)
        signalNotFull();
    return x;
}

3.3.6、remove(Object o)
从队列中移除指定的值。将两把锁都锁定。

public boolean remove(Object o) {
    //不支持null
    if (o == null) return false;
    //锁定两个锁
    fullyLock();
    try {
        //迭代队列
        for (Node<E> trail = head, p = trail.next;
            p != null;
            trail = p, p = p.next) {
            //通过equals方法匹配待删除元素
            if (o.equals(p.item)) {
                //移除p节点
                unlink(p, trail);
                //成功
                return true;
            }
        }
        //失败
        return false;
    } finally {
        //解锁
        fullyUnlock();
    }
}
// 将内部节点p与前一个跟踪断开连接
void unlink(Node<E> p, Node<E> trail) {
    // assert isFullyLocked();
    // p.next is not changed, to allow iterators that are
    // traversing p to maintain their weak-consistency guarantee.
    //p节点内容置空
    p.item = null;
    //trail节点的next指向p的next
    trail.next = p.next;
    //如果p是队尾
    if (last == p)
        //trail变为队尾
        last = trail;
    //如果队列已满
    if (count.getAndDecrement() == capacity)
        //通知插入线程阻塞
        notFull.signal();
}

3.3.7、clear()

清空队列。

//原子性地从队列中删除所有元素。此调用返回后，队列将为空。
public void clear() {
    //锁定
    fullyLock();
    try {
        //清空数据，帮助垃圾回收
        for (Node<E> p, h = head; (p = h.next) != null; h = p) {
             h.next = h;
             p.item = null;
        }
        head = last;
        // assert head.item == null && head.next == null;
        //如果容量为0
        if (count.getAndSet(0) == capacity)
            //唤醒插入线程
            notFull.signal();
    } finally {
        //解锁
        fullyUnlock();
    }
}

3.3.8、drainTo(Collection c)
将队列中值，全部移除，并发设置到给定的集合中。

public int drainTo(Collection<? super E> c, int maxElements) {
    //各种判断
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    if (maxElements <= 0)
        return 0;
    boolean signalNotFull = false;
    //锁
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lock();
    try {
        //获取要转移的数量
        int n = Math.min(maxElements, count.get());
        // count.get provides visibility to first n Nodes
         Node<E> h = head;
        int i = 0;
        try {
            //组装集合
            while (i < n) {
                Node<E> p = h.next;
                c.add(p.item);
                p.item = null;
                h.next = h;
                h = p;
                ++i;
            }
            return n;
        } finally {
            // Restore invariants even if c.add() threw
            if (i > 0) {
                // assert h.item == null;
                head = h;
                signalNotFull = (count.getAndAdd(-i) == capacity);
            }
        }
    } finally {
        takeLock.unlock();
        if (signalNotFull)
            signalNotFull();
    }
}

三. 锁

1. 锁状态
锁的状态只能升级不能降级。

2. 乐观锁与悲观锁

3. 自旋锁与适应性自旋锁

4. 公平锁与非公平锁

5. 重入锁与非重入锁

重入锁：同一个线程在外层方法获取锁的时候，在进入内层方法会自动获取锁，前提是锁对象是相同的。

6. 共享锁与排他锁

7. 读写锁

8. CAS

CompareAndSwap比较与交换，是一种无锁算法，原子类使用了CAS实现了乐观锁。

带来的问题:

循环时间长开销大，CAS操作如果长时间执行不成功，会导致其一直自旋，cpu消耗大。

9. 锁优化

9.1 锁升级

9.2 锁粗化

将多个连续的加锁，解锁操作连接在一起，扩展成为一个范围更大的锁，避免频繁的加解锁操作。

9.3 锁消除

通过逃逸分析，去除不可能存在共享资源竞争的锁，通过这种方式消除没有必要的锁。

10. synchronized底层实现

11. synchronized与ReentrantLock的区别

12. volatile关键字

volatile和synchronized的区别：

13. Atomic原子类实现

使用cas操作 + volatile + native方法保证同步。

14. AQS

AQS(AbstractQueuedSynchronizer)内部维护的是一个FIFO的双向同步队列，如果当前线程竞争锁失败，AQS会把当前线程以及等待状态信息构造成一个Node加入到同步队列中，同时在阻塞该线程。当获取锁的线程释放锁以后，会从队列中唤醒一个阻塞的节点线程。使用内部的一个state来控制是否获取锁，当state=0时表示无锁状态，state>0时表示已经有线程获取了锁。

15. AQS的组件

countDownLatch和CyclicBarrier的区别

16. 锁降级

锁降级是指将写锁降级为读锁，这个过程就是当前线程已经获取到写锁的时候，再获取到读锁，随后释放写锁的过程，这么做的目的为的就是保证数据的可见性。

17. 逃逸分析

Java程序员福利"常用资料分享"

上一篇 下一篇

猜你喜欢

热点阅读