三大集合

前言

java 的集合类主要在 util 包中，主要有三种，分别是 list、map 和 set。其中 list 和 set 的上层接口同是 Collection，map 则实现了 Map 接口。值得一提的是，Collection 接口下除了 list 和 set，还有 queue，也就是我们常说的队列了。队列的实现类主要有 lindkedList。

下面，就让我们分别说明三大集合的特点吧。

导航

• 前言
• List
• Map
  • HashMap 与 LinkedHashMap、TreeMap
  • ConcurentHashMap
• Set

List

List 是非常常见的使用类型，主要实现类有 ArrayList、LinkedList 和 Vector。其中 Vector 已经基本不再使用了，如果需要保证并发安全的话，可以使用并发包下的 CopyOnWriteList。而 ArrayList 和 LinkedList，常考察的点是两者的区别。而从名字上我们就可以看出来，ArrayList 的底层实现是数组，LinkedList 的底层实现是链表，具体来说是双向链表——而这，也为 LinkdedList 实现 Queue 与 Deque(双向队列)提供了可能。

因为底层实现的不同，ArrayList 与 LinkedList 有如下区别：

• ArrayList 实现了 RandomAccess 接口，支持通过下标对元素进行快速访问，LinkedList 不支持。
• ArrayList 插入、删除操作可能触发数组扩容或者减容，代价较大，而 LinkedList 只需维护相关指针，代价很小

Map

Map 主要分为 Hashtable、HashMap、TreeMap 和 LinkedHashMap。Hashtable 虽是线程安全的，但是其内部方法均以 synchronized 修饰，同步代价较高，基本可以用支持并发的 ConcurentHashMap 代替。

HashMap 与 LinkedHashMap、TreeMap

HashMap 主要采用数组+链表/红黑树的方式实现。也就是初始化数组 table（初始容量为 16），然后根据哈希函数 hashCode()%table.length()确定元素在数组中的位置，转化为链表的节点进行存储。因为 table 始终是 2 的 n 次方，根据公式 a % (2^n) = a & (2^n - 1)，哈希函数转变为了 hashCode() & (table.length()-1)。而扩容时，也因为容量保持 2 的 n 次方，所以新散列位置等于原先的位置或者原先位置+原容量。

为什么 table.length()始终是 2 的 n 次方呢？原因很简单，因为初始值为 2 的次方，而每次扩容都*2。

当 table[i]的链表节点数大于等于 8 时，将会把链表转为红黑树以提升查找效率。而待数量小于等于 6 时，会把红黑树重新转换成链表。

LinkedHashMap 继承了 HashMap，运用模板方法模式重写了

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

三个方法，从而维护了每个节点的 before、after 指针，以此来实现节点的顺序访问。

除了 LinkedHashMap，TreeMap 也是有序的，但是两者有序的方式不同。根据上文可知，LinkedHashMap 主要依靠维护双向链表以实现按插入、最近最少使用顺序访问，而 TreeMap 的底层实现就与 LinkedHashMap 不同，是红黑树。所以 TreeMap 的有序是依靠 compareTo()方法的。所以，TreeMap 的存储对象必须实现 Comparable 接口，又或者创建时传入 Comparator 比较器。

ConcurentHashMap

ConcurentHashMap 作为支持并发的 HashMap，其底层数据结构和 HashMap 类似，但用了大量处理来支持并发。首先，get()方法是不加锁的，put()方法分为两种情况：

• 如果 table[i]==null，那么将用 cas 操作使 table[i]=newNode
• 如果 table[i]!=null,那么将会 syncronized(table[i])，将节点加入链表末尾或插入数

Set

实现 Set 接口的类主要有 HashSet、LinkedHashSet、TreeSet。而因为 map 的 key 值定义完美满足了 set 的要求，所以借助于各种 map，set 的实现非常简单：

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}