Java集合类是JDK学习中的一个经典切入点,也是让初学者最初感受到Java魅力的地方之一,你一定不会忘记不需要关心大小的ArrayList,不用自己实现的Queue,和随处可见的HashMap。面试中,对Java基础的考察中,集合类和String相关是两个重点,这里集中整理了关于集合类的一些知识点。

集合类的结构

要求手绘结构图,同时抛出一些简单的线索勾引面试官提问(比如讲HashMap的HashTable的区别)。

Java集合类综合-LMLPHP

XX和XX的区别

ArrayList & Vector & LinkedList

  • 实现方式:

    • ArrayList、Vector 基于数组实现
    • LinkedList 基于链表实现
  • 同步问题:
    • ArrayList、LinkedList 不是线程安全的
    • Vector 是线程安全的,实现方式是在方法上加 synchronized 关键字进行修饰
  • 适用场景和性能消耗:
    • ArrayList 和 Vector 基于数组实现,所以随机位置增、删是 O(n) 的时间复杂度,另外可能会出现扩容的问题,也是 O(n) 的时间复杂度
    • LinkedList 不会出现扩容的问题,所以比较适合随机位置增、删。但是其基于链表实现,所以在定位时需要线性扫描,会消耗 O(n) 的时间复杂度
  • 扩容:
    • ArrayList默认初始容量为10,每次扩容为原来的1.5倍
    • Vactor默认初始容量为10,默认每次扩容为原来的2倍(可通过capacityIncrement设置)

HashMap & HashTable

  1. HashMap是非线程安全的,HashTable是线程安全的
  2. 扩容机制相同

HashMap & TreeMap

  1. HashMap实现了Map接口,不保障元素顺序。实现原理balabala
  2. TreeMap实现了SortedMap接口,是一个有序的Map。内部采用红黑树实现,红黑树是一种维护有序数据的高效数据结构,但具体算法没有掌握

HashMap & LinkedHashMap

  1. HashMap是无序的;如果希望容器按照自定义顺序遍历可使用TreeMap;如果希望按照插入顺序遍历,可使用LinkedHashMap
  2. LinkedHashMap是HashMap的一个子类,与HashMap相比,在Entry中增加了before、after两个引用,利用双向链表维护插入顺序
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

HashSet & HashMap

  1. HashMap实现了Map接口,原理balabala
  2. HashSet实现了Set接口,实质上封装了一个HashMap。在HashSet封装的HashMap中,entry.key为HashSet的元素(从而保证元素的唯一),entry.value统一指向一个static final的Object对象


05-06 10:26