Java容器面试题

Updated: at 10:12 AM

1. JAVA STL

1.1. STL基础

1.1.1. Iterable和Iterator的关系

Iterable

Iterable是一个接口，<1>表示的是是否可迭代 <2>其中有forEach方法的定义，可以通过forEach方法来表示元素的遍历 <3>其中包含了Iterator的定义，可以返回Iterator

Iterator

Iterator是迭代器，<1>其中有hasNext和Next定义，遍历到结尾就不再遍历了

class AbtractList<E> implements Iterable<E> {
    public Iterator<E> iterator() {
        return new Itr();
    }
    
    private class Itr implements Iterator<E> {}
}

1.1.2. 什么是fail-fast？fail-safe？COW？

fail-fast

fail-fast快速失败机制，迭代的时候如果发现原来的集合被修改，直接抛出Concurrent Modification Exception。（防止并发修改）

集合类有个modCount，生成迭代器进行遍历前会生成一个exceptedModCount = modCount，迭代器在遍历的时候直接访问原集合的内容，如果add/remove会让modCount改变，每次hasNext()先比较modCount和exceptedModCount是否相等，不相等则抛出Concurrent Modification Exception（并发修改异常）。

fail-safe

对于fail-safe来说，在遍历的时候不直接在集合内容上访问，而是先复制原来的内容，在拷贝的集合上遍历访问，因此不会抛出异常。

COW

写时复制，不发生写的时候都指向相同的。发生写的时候复制一份，指向新的容器。在复制的时候要加锁，即add/remove是加锁的，读不需要加锁（读写分离思想）。eg：CopyOnWriteArrayList

1.2. HashMap与ConcurrentHashMap

1.2.1. 介绍一下HashMap

HashMap是java内置的线程不安全的hash表，其解决hash冲突的方法是拉链法

JDK1.7之前是数组+链表，JDK1.8之后是数组+链表+红黑树

数组里面存放了键值对，在java7叫Entry，java8叫Node

数组+链表（元素长度小于6）+ 红黑树（当链表元素长度大于8）

**为什么是8？**根据泊松分布，负载因子默认0.75的时候，单个槽内元素个数为8的概率小于百万分之一，所以将7作为分水岭。大于等于8进行转换，小于等于6进行退化。

Hash的默认大小/负载因子/扩容是什么？为什么是2^n？

默认大小：16 负载因子：0.75 扩容因子：2

为什么是2^n？

将hashcode转化为桶用的是 h & (length - 1)，意思是hashcode除以桶长度的余数。&比%运算更快

HashMap比较key的时候用什么方法？什么时候重写hashCode()？

比较key的方法是p.hash == hash && p.key.equals(key)，也就是先比较其hash值。

hashCode()只有在hashMap中才会用到，如果key是自定义的Object都需要重新hashCode()，内置的Object类比如String就不需要。这是防止两个Object是相等的但是hashCode不相等，所以还是可以加入到hashSet里面。

为什么HashMap中的链表大小超过8的时候会自动转化为红黑树，当小于等于6的时候会重新变为链表？

超过8的时候转化是因为红黑树查找效率高，避免因为链表长度过长影响查找效率

大小为8是因为根据概率论在负载因子为0.75的时候超过8的概率是百万分之一

HashMap的get过程？

  1. 首先根据给定的key计算出其hashCode值，h ^ (h >>> 16)为了让高16位也参与运算

  2. 根据hashCode找到对应的桶（链表的头节点），公式 h & （length - 1）

  3. 遍历桶中的节点，依次判断给定的key是否与链表中的元素相同，先判断HashCode，再使用equals判断

HashMap的put过程？头插法和尾插法的区别？
  1. 根据给定的键计算出HashCode值，h ^ (h >>> 16)
  2. 根据hashCode找到对应的桶，公式h & (len - 1)
  3. 如果当前没有元素就直接插入该桶位
  4. 如果当前key和要插入的key相等，则替换
  5. 如果当前桶的节点是树节点，调用putTreeVal()
  6. 遍历链表，遍历过程中如果key相等则替换，否则遍历到链表尾就插入。插入后判断大于8个就红黑树化（注意JDK1.7用的是头插法，有个坏处是并发的时候容易出错导致出现死循环。JDK1.8尾插法没有死循环，但是size++还是会有并发修改覆盖的问题）
  7. ++size并判断是否达到阈值，达到阈值就resize()
V putVal(int hash, K key, V value) {
    int idx = h & (n - 1);
    p = tab[h & (n - 1)];
    // 如果当前没有元素就直接插入该桶位
    if(p == null) {
        tab[idx] = newNode(...);
    }
    else {
        // 如果当前key和要插入的key相等，则替换
        if(p.hash == hash && key.equals(p.key)) {
            tab[idx] = V;
        }
        // 如果当前桶的节点是树节点，调用putTreeVal()
        else if(p instanceof TreeNode) {
            putTreeVal(...);
        }
        else {
            // 遍历链表
            for(int binCount = 0; ; ++binCount) {
                // 到达尾部，则尾插法插入元素
                if(p.next == null) {
                    p.next = newNode(...);
                    // 插入后判断大于8个就红黑树化。treeifyBin()中先判断如果数组数量大于64才去扩容。
                    if(binCount >= TREEFIY_THRESHOLD - 1) {
                        treeifyBin(...);
                    }
                    break;
                }
                // 遍历过程中如果key相等则替换
                if(p.hash == hash && key.equals(p.key)) {
                    p = V;
                    break;
                }
            }
        }
    }
    // ++size并判断是否达到阈值，达到阈值就resize()
    if(++size > threshold) {
        resize();
    }
}

上面这是伪代码，不是真实代码

HashMap的扩容机制？rehash的过程？

扩容时机是达到容量 * 负载因子0.75，就将数组扩容为原来的两倍

rehash的时候因为n & h变为 (2 * n ) & h，即后面的位还是不变的，只需要判断最高位是0还是1，是0则放在原位置，是1则放在位置 + len / 2。

1.2.2. ConcurrentHashMap原理？如何实现线程安全的？

ConcurrentHashMap的设计思路是这样：一个HashTable加一个锁 ，效率很低。所以采用分段锁的思想，把一个大的HashTable拆成多个segment，给各个segement加锁。

在JDK1.7中设置了16个Segment，Segment继承自ReentrantLock充当了可重入锁，每个Segment都维护一个HashTable（HashEntry数组），每次加锁只对单个Segment加锁，不影响别的Segment。

在JDK1.8中，ConcurrentHashMap的整体结构与JDK1.8的HashMap相同，采用的数组 + 链表/红黑树，链表是尾插法，加锁的粒度相比于1.7更细，只会对一个桶的节点加synchronized，而空桶和初始化桶，扩容都是用CAS，所以采用的是CAS+synchronized

为什么ConcurrentHashMap并发度高？

JDK1.7的ConcurrentHashMap采用了分段锁的思想，理论上支持Segment数组大小的并发线程数。各个Segment加锁互相不影响。

ConcurrentHashMap如何保证fail-safe的？

返回的是弱一致性迭代器

ConcurrentHashMap的put过程

JDK1.7：

  1. hashCode()得到key的hash值
  2. 通过hash值得高位 & 1111得到所在得Segment
  3. 如果Segment未初始化，通过CAS初始化
  4. 在Segment中，先自旋尝试Trylock()，尝试一定次数后阻塞Lock()，先找到指定得桶，再插入。

JDK1.8：

  1. 根据key的hashCode得到hash值
  2. 判断是否需要初始化，需要的话CAS初始化
  3. (n - 1) & hash得到桶，如果当前元素为空，则CAS尝试插入元素
  4. 如果元素hash值为MOVED，则说明正在扩容，且该桶已经扩容成功了，则协助扩容。
  5. 给桶的头节点加入synchronized，如果是树节点则插入树，如果是链表则尾插法，尾插之后判断是否需要treeify，首先会判断是否大于64。
  6. 最后判断是否要扩容
ConcurrentHashMap的get过程

JDK1.7：

  1. key的hash值先得到具体的Segment，再通过一次hash计算定位到桶。
  2. 由于HashEntry的value是volatile修饰的，保证了内存是最新值
  3. ConcurrentHashMap的整个过程不需要加锁，很高效

JDK1.8：

基本同HashMap的get，不需要加锁

ConcurrentHashMap的扩容过程

JDK1.7:

每个Segment单独扩容，不受影响，扩容的时候加Segment锁即可。

JDK1.8：

扩容的时候，多个线程可以同时参与扩容，把旧数组的元素挪到新数组当中。每个线程负责扩容一个区间，且线程的扩容不是主动的，是在看到别的线程在扩容的时候去协助扩容。

最重要的是sizeCtl的含义，为0表示未初始化，为-1表示正在初始化。其他负数则表示正在扩容，具体的，-(1+n)表示有n个线程正在参与扩容。第一个扩容的线程是-2，为什么是-2不是-1是因为最后一个线程会多做一步重新检查一遍。第一个扩容的线程还要CAS创建newTab，为原数组的2倍大小。每个线程会通过transferIndex减去一个stribe，作为扩容的范围。扩容成功会将oldTab对应桶加入ForwardingNode，其hash值是-1，以后线程访问的时候计算得到hash为-1，即得知在扩容，于是协助扩容。其中对共享变量的修改用CAS，比如sizeCtl。

1.2.3. TreeMap/HashTable/LinkedHashMap/HashSet/Collections.synchronizedMap(map)

Collections.synchronizedMap(Map)

原理：

public class Collections {
    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }
    static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
        // 内部封装的原始 Map 对象
        private final Map<K,V> m;
        
        public V put(K key, V value) {
            // 同步块确保线程安全
            synchronized (mutex) {return m.put(key, value);}
        }
        
        public void clear() {
            // 同步块确保线程安全
            synchronized (mutex) {m.clear();}
        }
    }
}
什么是TreeMap？

TreeMap底层是由红黑树实现的集合结构，其API与HashMap类似

实现 SortMap 接口，按照键的顺序排序，默认升序

原理 TreeMap是一个基于红黑树和NavigableMap实现的，其中NavigabledMap是JDK1.6中扩展SortedMap

红黑树的插入、删除、遍历时间复杂度为O(lgN)，但是哈希表无法提供键值对的有序输出，红黑树是排序插入的，可以按照按照键的值大小有序输出。

HashTable为什么效率低？

HashTable会对整个哈希表上锁，效率低

HashMap、ConcurrentHashMap和HashTable的不同点？

HashMap是线程不安全的，HashTable是线程安全的，但是效率很低。ConcurrentHashMap的锁粒度更小，用了分段锁的思想，所以效率更高。

HashTable和HashMap的区别？

HashTable是不允许键或者值为null的，HashMap的键和值都可以为null。因为HashTable或者ConcurrentHashMap在value可以为null的时候会产生二义性，通过get(key)得到null，再通过contains(key)得到null不确定是本来就是null还是因为并发修改才是null的。

初始容量不同：HashMap初始容量为16，HashTable初始容量为11

扩容机制不同：HashMap扩容容量翻倍，HashTable扩容容量翻倍+1

线程安全不同：一个不安全一个安全

迭代器不同：HashMap是fail-fast，HashTable不是fail-fast（是什么？）

LinkedHashMap是什么？

LinkedHashMap是HashMap的子类，会用链表保存插入的顺序，在使用Iterator返回的时候是按照插入的顺序。缺点就是容量很大的时候插入速度慢。

HashMap和HashSet的区别？

HashSet底层是由HashMap来实现的，key存储元素，value是一个固定的Object

HashMap如何处理KV为null的？

JDK8之前，NULL被当作0处理，JDK9之后会单独维护NULL

1.3. ArrayList

1.3.1. ArrayList的原理？扩容机制

  1. 无参创建的ArrayList，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素时才分配容量，默认是10。以后扩容为原来的1.5倍。

  2. 最后是用的Arrays.copyOf(elementData, newSize)进行的扩容。第一个参数是老数组，第二个参数是扩容后数组的长度。Arrays.copyOf()先创建一个新数组，再把老数组的元素移到到新数组里面。

  3. ArrayList可以添加多个null

ArrayList默认大小

默认大小10，最大Integer.MAX - 8。负载因子：1。扩容因子：1.5

使用new ArrayList(int initialCapacity)会不会初始化数组大小？

会初始化数组大小，this.elementData = new Object[initialCapacity];如果是无参构造器创建的，this.elemenData = EMPTY数组{}，不会初始化大小。

ArrayList的数组为什么要用transient修饰？

transient Object[] elementData是因为ArrayList有些元素是默认的（扩容出来但是没用过），如果一起序列化就会导致序列化后体积增大。ArrayList使用readObject和writeObject来实现定制序列化，保证只序列化非默认元素。

readObject()和writeObject()

outputStream和InputStream含有readObject和writeObject方法，可以实现对象序列化和反序列化。如果对象本身实现了private的readObject和writeObject，则outputStream和inputStream的readObject和writeObject会反射调用Object自己实现的readObject和writeObject去序列化。

1.3.2. ArrayList并发安全问题解决方案？

  1. **Collections.synchronizedList(list)**将ArrayList转化为线程安全的容器
  2. 使用CopyOnWriteArrayList代替ArrayList
  3. 使用Vector代替ArrayList
  4. 为add()方法加锁
  5. 使用ThreadLocal()
ArrayList并发中是否越界？

并发中有可能出现下标越界异常，它本身是对List的modCount++后再对size++，这两个变量都有并发修改的可能。

CopyOnWriteArrayList如何保证写并发和独写的问题？适合什么场景？

CopyOnWriteArrayList在add的时候会给整个添加过程加上ReentrantLock保证不会出现并发问题，并且他会做一个复制操作，复制完之后再将数组指向新复制出来的。保证读的并发性，体现“独写分离”。

适合读多写少的场景，因为写的效率很低。支持fail-safe。

1.3.3. Array和ArrayList有什么区别？ArrayList与LinkedList区别？ArrayList与Vector的区别？什么时候用Array？

Array和ArrayList的区别？

Array数组可以包含基本数据类型和引用类型，ArrayList只能包含引用类型

Array数组的空间是固定的，ArrayList的大小是动态变化的

对于基本数据类型，Arraylist使用自动装箱，但是这种方式相对较慢。如果我们需要的元素数量固定那么使用Array效率高一些

ArrayList和LinkedList的区别？
  1. 底层实现：ArrayList是数组，LinkedList是双向链表
  2. 随机访问：ArrayList支持随机访问O(1)，LinkedList不支持O(N)
  3. 插入速度：LinkedList O(1)插入，ArrayList需要插入挪动元素
  4. 内存空间占用：ArrayList的空间占用体现在数组尾部会预留一定的容量空间，而LinkedList的空间花费主要体现在它的每个节点都比ArrayList消耗的空间更大一些，因为要存储直接后继和直接前驱。
ArrayList与Vector的区别？
  1. Vector的所有方法都是同步的，但是一个线程访问要消耗大量的同步空间
  2. ArrayList是不安全的，速度比Vector更快
怎么设计一个线程安全的LinkedList？

  1. List list = Collections.synchronizedList(new LinkedList());

  2. LinkedList换成ConcurrentLinkedQueue

详见ArrayBlockingQueue 源码分析 | JavaGuide中的阻塞队列，阻塞队列有ArrayBlockingQueue，ConcurrentLinkedQueue，SynchronousQueue，DelayQueue