【Java面试提问解读】三：容器相关

作者: Cesarean | 来源:发表于2019-03-14 15:11 被阅读0次

【Java面试提问解读】三：容器相关
Java容器--2021面试题系列教程（附答案解析）--大白话解
Java的juc相关容器，工具，框架介绍
面试提问相关
面试总结Android
深入Java源码解析容器类List、Set、Map
【Java面试提问解读】二：异常解析
Java面试题
Nothing seek,Nothing find
解读Java同步器相关源码

面试公司：字节跳动西瓜视频

面试岗位：后台开发日常实习生

面试轮次：第一次面试

面试问题纵览

前言：这里的问题我答得一半一半，因为只会用而没有深入底层，而实际上面试的话对于这个容器的底层实现还是很重视的。这篇先讲面试问题，再写一些容器的基础。

ArrayList和LinkedList异同

均是非线程安全的
底层数据结构上ArrayList依靠数组实现，LinkedList依靠双向链表实现，且JDK1.6之前使用双向循环链表，JDK1.7之后取消循环。
一些查找以及修改的优缺点异同点参考数组和链表的对比。
内存占用上，LinkedList因为每个节点需要额外的前导和后继指针，所以需要消耗更多的空间；而ArrayList需要在数组结尾预留空间以保证当插入时不需要频繁进行内存申请。

HashMap底层实现
HashMap的底层实现是数组+链表；数组用于散列表，冲突的解决方案是拉链法，同时在JDK1.8之后有了一个改进就是当冲突链链长大于阈值（默认8）时，将该冲突链转化为红黑树，以保证查询的效率。（问到这里就可能扯到红黑树和二叉查找树了）
扩充：
@HashMap核心三大功能

确定索引
HashMap::put方法
扩容机制

@HashMap死循环

HashMap和HashTable异同

HashMap非线程安全，为了线程安全常用ConcurrentHashMap；HashTable是早期容器，线程安全
HashMap支持null键；而HashTable不支持null键；可通过以下源码确定

//Implements in HashMap
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//Implements in HashTable
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    ...
}

初始容量和扩容容量不同：
- 不指定初始容量时HashTable初始容量为11，而HashMap初始容量为16；
- 指定初始容量时HashTable初始容量为设定值，而HashMap初始容量将向上取2的幂次方，大于上限时取上限。
- 扩容时HashTable扩容为2n+1，而HashMap扩容为2n
- HashTable是为了素数容量，这样取模时可以减少冲突（可证明素数取模最易减少冲突）；HashMap是为了对取模和扩容的优化。
- 以上对于HashMap是因为其将一直保持自己的容量是2的幂。
底层数据结构在JDK1.8中HashMap引入红黑树后趋向不同

容器基础

首先上常用的类的类图，因为是通过IDEA自动生成的，所以有些implement线是多余的，但大体上能作为参考。

常用容器类图
然后我们需要先区分早期容器和现役容器
- 早期容器一般指Java 1.0/1.1时期的容器，从设计上可以找到很多的缺点，最重要的缺点就是早期的容器设计都是线程安全的，通过synchronized对容器方法加锁，使得容器的性能较为低下。在上图中我加入了三个早期容器，包括Vector，Stack，HashTable。记住这些容器应该尽量避免使用。（同时注意两点，Vector底层实现也是数组，且Stack是直接继承Vector）
- 现役容器也就是Java后期新引入的非线程安全的容器或者特殊线程安全的容器，前者方法都去除了synchronized，同时Collections工具类提供一系列的静态装饰器方法，可以将非线程安全的类转换为线程安全的类；后者会使用一些免锁的方式实现线程安全。不过后者如CopyOnWriteArrayList并没有添加在上图中，因为此处不做特别深入的讲解。
底层数据结构总结
- ArrayList：数组
- Vector：数组
- LinkedList：双向链表，JDK1.6之前使用双向循环链表，JDK1.7之后取消循环
- HashSet：分析源码，基于HashMap实现
- TreeSet：红黑树
- HashMap：JDK1.8前数组+链表，JDK1.8后数组+链表+红黑树
- HashTable：数组+链表
- TreeMap：红黑树

注意一下RandomAccess接口

该接口源码其实毫无定义

public interface RandomAccess {
}

实际的作用仅是标识类可以进行随机访问，那用途呢，参考Collections工具类的二分搜索

public static <T> int binarySearch(List<? extends T> list, T key, 
Comparator<? super T> c) {
    if (c==null)
        return binarySearch((List<? extends Comparable<? super T>>) list, key);

    if (list instanceof RandomAccess || list.size()  <BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key, c);
    else
        return Collections.iteratorBinarySearch(list, key, c);
}