共计 4446 个字符，预计需要花费 12 分钟才能阅读完成。
List
有序集合，允许重复的元素，允许插入多个 null 元素，根据元素的索引访问元素
ArrayList
底层数组实现，无参构造器默认实现容量为 10 的空数组
查找直接由位置索引
public E get(int index) {rangeCheck(index);
return elementData(index);
}无索引位置直接插入，指定位置插入存在数组复制
public void add(int index, E element) {rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}删除存在数组复制
public E remove(int index) {rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}ArrayList 扩容，数组大小超过设定容量时自动扩容至 1.5 倍大小
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容至 1.5 倍大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//System.arraycopy 针对已存在的源数组和目的数组进行拷贝，Arrays.copyOf 拷贝需创建新的目的数组，底层调用 System.arraycopy
elementData = Arrays.copyOf(elementData, newCapacity);
}LinkedList
底层为双向链表实现
Vector
Stack
Set
不包含重复元素的集合，最多包含一个 null 元素
HashSet
特性：
- 基于 HashMap 实现，无序容器，侧重在存储数据的唯一性
- 允许存在 null 值
- 非线程安全实现
- HashSet 迭代遵循 fail-fast 机制
类成员变量，插入元素作为 map 的 key 对象，value 对象保持不变为 Object
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();无参构造函数
public HashSet() {map = new HashMap<>();
}HashSet 查找，插入，删除操作均借助 HashMap 实现
public boolean contains(Object o) {return map.containsKey(o);
}
public boolean add(E e) {return map.put(e, PRESENT)==null;
}
public boolean contains(Object o) {return map.containsKey(o);
}LinkedHashSet
特点：
- 继承于 HashSet，基于 LinkedHashMap 实现
- 有序容器，由 LinkedHashMap 实现迭代顺序于元素插入顺序一致
- 非线程安全实现
- LinkedHashSet 迭代遵循 fail-fast 机制
// 无参数构造函数默认调用 HashSet 构造函数
public LinkedHashSet() {super(16, .75f, true);
}
此构造函数使用 LinkedHashMap 实现，保证元素 FIFO
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}TreeSet
特点：
- 基于 TreeMap 实现，由 TreeMap 保证有序
- 增删查操作时间复杂度为 log(n)
- 非线程安全
- 迭代遵循 fail-fast 机制
- 不允许 null 值对象
成员变量，TreeSet 内部基于 TreeMap 实现
private transient NavigableMap<E,Object> m;
// 值对象固定为 Object
private static final Object PRESENT = new Object();
// 无参构造器
public TreeSet() {this(new TreeMap<E,Object>());
}迭代器：
// 升序迭代器
public Iterator<E> iterator() {return m.navigableKeySet().iterator();}
// 降序迭代器
public Iterator<E> descendingIterator() {return m.descendingKeySet().iterator();}Map
Map 并非 collection 的子接口或者实现类，每个 Entry 都持有两个对象，键对象和值对象，Map 可能会持有相同的值对象但键对象唯一
HashMap
特性：
- 非线程安全
- 键对象允许 1 个 null 值，值对象允许多个 null 值
- 父类是 AbstractMap
- 无序容器
HashTable
特性：
- 不允许 null 值
- 线程安全
- Hashtable 的父类是 Dictionary
- 无序容器
LinkedHashMap
特性：
- 非线程安全
- 有序容器，内部维护链接全部 Entry 双向指针实现迭代顺序与 Entry 插入顺序一致
LinkedHashMap 的 Node 继承于 HashMap 的 Node 同时增加头尾指针：
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);
}
}TreeMap
特性：
- 基于红黑树实现
- 有序容器，由 key 对象类实现 Comparable 接口或者是比较器 Comparator 实现排序
- 增删查改时间复杂度为 log(n)
- 非线程安全实现
TreeMap 的 put 方法
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}其中 compare 方法
final int compare(Object k1, Object k2) {
//comparator 为 TreeMap 的成员变量
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}- 基本数据类型包装类，String 类等默认实现 Comparable 接口，可直接作为 key 对象
-
自定义对象：
- 实现 Comparable 接口，重写 Compareto 方法
- 自定义比较器类，并且要让其实现 Comparator 接口，通过以下构造方法指定使用自定义比较器类
集合类线程安全实现
- 线程安全包装类
Set s = Collections.synchronizedSet(new HashSet(...));
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));fail-fast 机制
即快速失败机制，它是 Java 集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，此时程序会抛出 ConcurrentModificationException 异常，从而产生 fail-fast 机制。
// 如在 ArrayList 内部实现的迭代器中，当调用方法 next 或者 remove 时会首先检查 modCount == expectedModCount（创建迭代器时由 modCount 赋值）final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}正文完