【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);
  }
  

  • 那么对于以上的总结是什么呢，也就是遍历方式的选择，对于实现了RandomAccess的容器，优先索引遍历；而对于没有实现的，优先iterator遍历