Java 集合类总结

Java 集合框架

集合框架分为Collection体系，和Map体系。

• Collection
  • List
  • Set
  • Queue
• Map

常用集合分类

非线程安全

• ArrayList
• LinkedList
• HashSet
• HashMap

线程安全，过时

• Vector
• HashTable

线程安全，推荐

• CopyOnWriteArrayList
• CopyOnWriteArraySet
• ConcurrentHashMap

常见集合源码分析

ArrayList 源码分析

底层结构：数组

// 底层数据结构：数组
transient Object[] elementData; // non-private to simplify nested class access
// 初始容量10
private static final int DEFAULT_CAPACITY = 10;

扩容

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:
    // 快速复制元素 Arrays.copy() --> System.arraycopy()
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList 源码分析

底层结构：双链表

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

// 初始大小0
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

HashMap 源码分析

底层结构：哈希表+链表/红黑树

数组（也称哈希桶数组）

transient Node<K,V>[] table;

链表（或红黑树）

// 单链表节点，
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 维护桶中的单链表

    ...
}
// 红黑树节点，
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

哈希定位

对key的hashCode进行扰动，hash值更均匀

哈希碰撞

• 链地址法
• 链表长度到达8，则链表换为红黑树

// 对hashCode进行扰动
static final int hash(Object key) {
    int h;
    // h = key.hashCode() 为第一步 取hashCode值
    // h ^ (h >>> 16)  为第二步 高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// hash定位，对table长度取模
// 由于 table 的长度是 2 的幂，所以 hash & (length -1) 相当于 hash % length
index = hash & (length -1)

扩容

初始容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

• 每次扩容，增加一倍，长度保持为2的幂
• 扩容后，将所有Node移动到新的哈希桶中，开销较大
• 扩容后，所有Node重新定位

LinkedHashMap 源码分析

底层结构：双链表

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    LinkedHashMapEntry<K,V> before, after; // 维护双链表，使结点有序
    ...
}

排序

默认仅按插入顺序排序，如果 accessOrder为 true，则每次访问元素都会将该元素放到链表尾部。

// 是否按访问顺序重排元素，可以利用这个实现LruCache
final boolean accessOrder;

总结

1. LinkedHashMap 基于 HashMap 实现，在原结点的基础上增加双链表引用，这样，容器中的元素在逻辑上就有两种存储结构：哈希表与双链表。由于双链表，实现了元素排序。
2. LruCache 就是基于 LinkedHashMap 实现的。