Collection

Collection接口是所有集合的根接口。它的两个重要子接口分别为ListSet

Collection结构图

List 列表

List接口的实现类集合的元素均是有序可重复的。

ArrayList

特点:

  • 线程不安全
  • 允许元素为null。
  • 底层数据结构为Object[]数组,初始容量10,加载因子为1扩容增量0.5倍
  • 增删操作慢,查找快。
  • 支持快速随机访问。

LinkedList

特点:

  • 线程不安全
  • 允许元素为null。
  • 底层数据结构为双向链表,无初始容量,只需在链表尾部添加新结点即可。
  • 不支持快速随机访问。
  • 增删操作快,查找慢。

Vector

特点:

  • 允许元素为null。

  • 线程安全,每个方法都加了synchronized修饰符。

  • 底层数据结构为Object[]数组,初始容量10,加载因子为1,默认扩容增量为1倍

ArrayList与Vector的区别:

  • Vector所有类的方法都是同步的,可多个线程安全的访问同一个Vector对象,但单线程访问将会在同步操作花费大量时间。
  • ArrayList不是同步的,所以不需要保证线程安全时可优先使用ArrayList。

Set 集合

Set 接口的实现类集合的元素均是不允许重复的。

键一样,值不一样会被后来的值覆盖。键不一样,值一样是可以的。

HashSet

特点:

  • 无序

  • 线程不安全

  • 允许null元素

  • 底层实现为HashMap<E,Object>,加载因子为0.75,初始容量为16,扩容增量为1倍

TreeSet

特点:

  • 有序

  • 线程不安全

  • 不允许元素为null

  • 底层实现为TreeMap<·E,Object>,TreeMap底层数据结构为红黑树

Map

Map是一个双列集合,是所有Map集合的父接口

HashMap

特点:

  • 允许元素为null

  • 线程不安全

  • 底层实现为Map.Node<K,V>,数据结构为拉链表,即链表+数据。

  • 默认加载因子为0.75,可自己设置加载因子。默认初始容量为16, 长度始终保持2的n次方,扩容增量:1倍

HashMap底层实现:

1
2
3
4
5
6
7
8
9
10
// HashMap中的属性table 数据结构为拉链表(数组+链表)
transient Node<K,V>[] table;

// HashMap中的静态内部类Node<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}

可以看到table属性是Node<K,V>类型的对象,Node <K,V>又是一个链表的数据结构,故 table数组的

每个元素都是一个链表的头结点,请看图示。当链表中的个数超过8个时,会转换为红黑树,以减少搜索时间。

HashMap拉链表

HashTable

特点:

  • 不允许元素为null
  • 线程安全,使用synchronized修饰了方法。
  • 底层实现为HashTable.Entry<?,?>[],数据结构为链表
  • 默认加载因子为0.75,可自己设置加载因子。默认初始容量为11, 扩容增量:1倍 + 1

TreeMap

特点:

  • 允许元素为Null
  • 线程不安全
  • 底层实现为TreeMap.Entry<K,V>,数据结构为红黑树