Java 集合源码解析

集合的分类#

Collection 接口#

Collection 接口，下面有三个主要的子接口：List、Set 和 Queue。

List#

List 集合存储的是有序的数据集合，其数据结构特点是：读取快，修改慢，适合于读取多、写入修改少的场景

Arraylist： Object[] 数组底层是用数组实现的。其读取元素的时间复杂度是 O（1），修改写入元素的时间复杂度是 O（N）。线程不安全
Vector：Object[] 数组类似ArrayList 并且Vector 是线程安全的
Stack 先进后出的数据结构。继承了 Vector，线程安全。
LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set#

Set 集合中存储的元素是不重复的，但是其存储顺序是无序的。

HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
TreeSet (Set集合唯一的有序实现): 红黑树(自平衡的排序二叉树)

Queue#

队列是一个特殊的线性表，其数据结构特点是先进先出。 offer、poll 等方法都是队列独有的操作。

PriorityQueue: Object[] 数组来实现二叉堆表示优先级队列，其按照队列元素的大小进行重新排序。当调用 peek() 或 pool() 方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列的最小元素。
Deque（double ended queue）是双向队列的意思，它能在头部或尾部进行元素操作, LinkedList 和 ArrayDeque 都是 Deque 接口的具体实现。
ArrayQueue: Object[] 数组 + 双指针

Map 接口#

Map#

Map 集合与 List、Set、Queue 有较大不同，其实类似于 key/value 的数据结构。Map 中的元素是没有顺序的

HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap：红黑树（自平衡的排序二叉树）Map 集合的有序实现。

ArrayList源码分析#

ArrayList底层采用定长数组实现，可以根据集合大小进行自动扩容。

类成员变量#

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
   //默认的初始化大小
    pivate static final int DEFAULT_CAPACITY = 10;

  // new ArrayList<>(0)时会存在这里，按需扩容 0 ——> 1
    private static final Object[] EMPTY_ELEMENTDATA = {};

  // new ArrayList<>() 时会存在这里，然后按默认扩容 0 ——> 10
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   // 列表数据
    transient Object[] elementData;
  // 列表大小
    private int size;
}

当使用无参构造时 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，扩容时会检查这个逻辑，如果符合逻辑，就会把最小容量设为 DEFAULT_CAPACITY（10）。
如果是 new ArrayList<>(0)那么在扩容的时候，就不符合 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA那么扩容的时候就会把大小设置为最小需要扩容的大小（这里不理解没关系，下面看到扩容代码就理解了）

构造方法#

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //当 elementData = EMPTY_ELEMENTDATA ，扩容的时候是按需扩容
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

//无参构造，把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋给 elementData
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

核心方法源码解析#

ArrayList 核心的方法是获取、插入、删除、扩容。

获取#

public E get(int index) {
    //判断index是否越界
    Objects.checkIndex(index, size);
    return elementData(index);
}

//下面是判断index合法性的代码
if (index < 0 || index >= length)
    throw outOfBoundsCheckIndex(oobef, index, length);
return index

插入#

插入尾部

public boolean add(E e) {
    //数组改变次数加一
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        //扩容，下面会讲到
        elementData = grow();
    //插入元素
    elementData[s] = e;
    //数组长度 + 1
    size = s + 1;
}

插入指定位置

public void add(int index, E element) {
    //检查 index 合法性
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    //判断是否需要扩容数组大小
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    //把 index 之后的所有元素后移，再将元素插入至 index 处。
    System.arraycopy(elementData, index,elementData, index + 1,s - index);
    elementData[index] = element;
    size = s + 1;
}

删除#

删除某个位置的元素

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    //将 index 位置后的所有元素都往前挪一位，最后减少列表大小。
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        //index 位置后的所有元素都往前挪一位
        System.arraycopy(es, i + 1, es, i, newSize - i);
    //删掉的置为空
    es[size = newSize] = null;
}

删除具体的元素

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

扩容#

//调用有参 grow 方法
private Object[] grow() {
    return grow(size + 1);
}

//调用 newCapacity 方法
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
    //原大小
    int oldCapacity = elementData.length;
    //扩容到原来容量的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容的
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    //判断扩容的大小是否达到了MAX_ARRAY_SIZE  = Integer.MAX_VALUE - 8
    //如果达到的话扩容到最大 Integer.MAX_VALUE，没有达到的话就扩容到 MAX_ARRAY_SIZE
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

newCapacity - minCapacity <= 0 ：1.5倍当前容量小于最低需要扩容容量：

通过elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA判断是不是有参构造（参数非0）创建的数组。如果参数是0，说明elementData == EMPTY_ELEMENTDATA，这时候直接按需扩容。按需扩容只有第一次会按需扩容。

总结#

ArrayList 有如下特点：

底层基于**Object 数组**实现，读取速度快，修改速度慢（读取时间复杂度O(1)，修改时间复杂度O(N)）。
线程不安全。
ArrayList 每次默认扩容为原来的 1.5 倍。
ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响
ArrayList 支持高效的随机元素访问。通过元素的序号快速获取元素对象(对应于get(int index)方法)。
ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间

Vector 源码分析#

底层实现与ArrayList相同，只不过他在方法上加了 synchronized 锁，使其线程安全

线程安全#

Vector 在每一个可能发生线程安全的方法加上 synchronized 关键字。这样就使得任何时候只有一个线程能够进行读写，这样就保证了线程安全。

//get 方法
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

//add方法
public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}

扩容#

我们知道，Vector 和 ArrayList 扩容的思路与 ArrayList 是相同，唯一的区别是 Vector 的扩容大小。那么vector是如何进行扩容的呢？我们来看下他的源码

private int newCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

如果 capacityIncrement 大于 0，那么就按照 capacityIncrement 去扩容，否则扩大为原来的 2倍。而 ArrayList 则是扩大为原来的 1.5 倍。

解释：我们注意到，vector的扩容是受到capacityIncrement的影响的，capacityIncrement是扩容增量，在构造方法中我们可以自定义。我们不自定义的话，默认为0。

//构造方法
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

Vector 与 ArrayList 的区别#

Vector 与 ArrayList 在实现方式上是完全一致的，但是它们在某些方法有些许不同：

Vector 是线程安全的，而 ArrayList 是线程不安全的。Vector 使用 synchronize 关键字实现同步。
Vector 默认扩容为原来的 2 倍，而 ArrayList 默认扩容为原来的 1.5 倍。

LinkedList 源码分析#

LinkedList 是链表的经典实现，其底层采用链表节点的方式实现。并且跟ArrayList一样，他是线程是不安全的。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 不仅实现了List 接口，还实现了 Deque 双向队列接口

核心数据结构#

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;
    }
}

//链表的大小
transient int size = 0;

//前置节点
transient Node<E> first;

//尾节点
transient Node<E> last;

采用的是链表节点的方式来实现的，并且每个节点都有前节点和后节点（双向链表）

核心方法#

查找#

LinkedList 查找需要从链表头结点（或尾节点）向后查找，时间复杂度为 O(N)，他不能像 ArrayList 那样随机访问指定位置的元素。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    //因为是双向的链表，如果获取的元素下标小于容量的一半，就直接从头查找，反之从尾部开始查找。
    if (index < (size >> 1)) {
        Node<E> x = first;
        //挨个遍历
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

插入#

public void add(int index, E element) {
    //底层调用了isPositionIndex方法，判断的是 index >= 0 && index <= size;的结果
    checkPositionIndex(index);
  //如果插入的位置在链表最后，直接调用 linkLast
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    //把last指向到新添加的元素上
    last = newNode;
    //判断之前的last是否为空，也就是说，该链表在添加元素之前是否为空，如果为空的话说明新节点是头节点，不为空的话把l.next 指向新的节点。
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    //把index位置的前节点指向新节点
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        //把index位置的前节点的下一个指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

删除#

移除特定元素

public boolean remove(Object o) {
    if (o == null) {
        //遍历节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                //调用unlink
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}


E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
    //删除的节点是头节点
        if (prev == null) {
            //把头结点设置为下一个节点
            first = next;
        } else {
            //把该节点的头节点指向该节点的下一个节点，然后把这个节点的前置节点置为空（删除）
            prev.next = next;
            x.prev = null;
        }
    //如果该节点是尾节点
        if (next == null) {
            //把尾节点设置为该节点的前驱节点
            last = prev;
        } else {
            //把把该节点的下一个节点的头节点设置为该节点的头节点，然后把该节点的下一个节点置为空
            //最后没有引用会被GC
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

总结#

底层基于链表实现，修改速度快，读取速度慢（读取时间复杂度O(N)，修改时间复杂度O(N)，因为要查找元素，所以修改也是O(N)）。
非线程安全。
与 ArrayList 不同，LinkedList 没有容量限制，所以也没有扩容机制。

Stack源码分析#

Stack 是先进后出的栈结构，通过继承 Vector 类，调用 Vector 类的方法实现。

public class Stack<E> extends Vector<E> {
    //无参构造
    public Stack() {}

    public E push(E item) {
        //调用vector方法，将元素插入数组尾部。
        addElement(item);
        return item;
    }


}

核心方法#

插入#

public E push(E item) {
    //调用vector方法，将元素插入数组尾部。
    addElement(item);
    return item;
}

删除#

pop 方法调用 Vector 的 removeElementAt 方法，删除的是数组最后一个元素，而不是第一个元素。

public synchronized E pop() {
    E       obj;
    int     len = size();
  //返回数组最后一个元素
    obj = peek();
    //删除
    removeElementAt(len - 1);
  //把元素返回
    return obj;
}

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    //返回的是数组的最后一个元素
    return elementAt(len - 1);
}

总结#

底层采用 Vector 实现，因此其也是采用数组实现，也是线程安全的。
先进后出的栈结构

HashSet 源码分析#

HashSet 是 Set 集合的哈希实现，其继承了 AbstractSet 抽象类，并实现了 Set 接口。不是线程安全的

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

成员变量#

HashSet 内部使用 HashMap 存储，而 PRESENT 则是存储在所有 key 上的 value。因此对于 HashSet 来说，其所有 key 的 value 都相同。

//hashSet内部是使用hashmap进行存储的
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
//存储的值
private static final Object PRESENT = new Object();

构造方法#

构造方法传入的参数都是用于初始化 HashMap 对象，主要有：initialCapacity（初始大小）、loadFactor（扩容因子）…
第 5 个方法使用 LinkedHashMap 实现的，而不是用 HashMap 实现的。而我们后面要讲到的 LinkedHashSet 其实就是使用 LinkedHashMap 实现的，其保存了插入元素的顺序。

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

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}


public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}


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


HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

核心方法#

添加#

直接调用了 HashMap 的 put 方法

public boolean add(E e) {

    //PRESENT是为空的，插入成功，那么就返回 true，否则返回 false。
    return map.put(e, PRESENT)==null;
}

删除#

直接调用了 HashMap 对象的 remove 方法

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

总结#

HashSet主要是调用了HashMap 的方法，所以我们把HashMap弄懂就好了。

LinkedHashSet 源码分析#

LinkedHashSet 继承了 HashSet，在HashSet基础上维护了元素的插入顺序。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

构造方法#

LinkedHashSet 他调用的都是HashSet 的三个参数构造方法，也就是上面说到的第五种构造方法

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

LinkedHashMap 本身维护了元素的插入顺序，所以说LinkedHashSet 可以实现此功能

总结#

LinkedHashSet 是在 HashSet 的基础上，维护了元素的插入顺序。虽然 LinkedHashSet 使用了 HashSet 的实现，但其却调用了 LinkedHashMap 作为最终实现，从而实现了对插入元素顺序的维护。

TreeSet 源码分析#

TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

//继承关系
public interface NavigableSet<E> extends SortedSet<E>

public interface SortedSet<E> extends Set<E>

成员变量#

//具体的实现类
private transient NavigableMap<E,Object> m;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

构造方法#

如果我们没有指定传入的 Map 类型，TreeSet 将默认采用 TreeMap 来实现。而你传入了 NavigableMap 类型的对象，那么就按照传入的对象类型来实现。

// 默认采用TreeMap实现
public TreeSet() {
    this(new TreeMap<E,Object>());
}
// 指定实现类型
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
// 指定TreeMap的比较器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
// 指定初始集合
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 指定比较器以及初始集合
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

核心方法#

TreeSet 的核心方法实现直接采用了 TreeMap 的实现。

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

public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

总结#

TreeSet 的实现与 HashSet 类似，都是直接采用了 TreeMap 的方法实现
都能保证元素唯一，并且都不是线程安全的。
TreeSet 用于支持对元素自定义排序规则的场景。

PriorityQueue 源码分析#

PriorityQueue 是一个优先级队列，其底层原理采用二叉堆实现

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

PriorityQueue 继承了 AbstractQueue 抽象类，具有队列的基本特性。

成员变量#

//队列数据
transient Object[] queue; // non-private to simplify nested class access

private static final long serialVersionUID = -7720805057305804111L;

private static final int DEFAULT_INITIAL_CAPACITY = 11;

//大小
int size;

//比较器
private final Comparator<? super E> comparator;

transient int modCount;

PriorityQueue 底层采用数组存储数据
Comparator 的实现决定了他一个最大堆还是最小堆。默认 PriorityQueue 是个最小堆。

构造方法#

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}


public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}


public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}


public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}


public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}


public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}


public PriorityQueue(SortedSet<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initElementsFromCollection(c);
}

PriorityQueue 的构造方法功能都类似。如果传入的是普通集合，那么会将其数据复制，最后调用 heapify 方法进行二叉堆的初始化操作。
如果传入的数据是 SortedSet 或 PriorityQueue 这些已经有序的数据，那么就直接按照顺序复制数据即可。

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}

heapify方法#

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}


private static <T> void siftUpComparable(int k, T x, Object[] es) {
     // 比较器comparator为空，需要插入的元素实现Comparable接口，用于比较大小
        Comparable<? super T> key = (Comparable<? super T>) x;
      // k>0表示判断k不是根的情况下，也就是元素x有父节点
        while (k > 0) {
            // 计算元素x的父节点位置[(k-1)/2]
            int parent = (k - 1) >>> 1;
            // 取出x的父亲e
            Object e = es[parent];
            // 如果新增的元素k比其父亲e大，则不需要"上移"，跳出循环结束
            if (key.compareTo((T) e) >= 0)
                break;
            // x比父亲小，则需要进行"上移"
            // 交换元素x和父亲e的位置
            es[k] = e;
            // 将新插入元素的位置k指向父亲的位置，进行下一层循环
            k = parent;
        }
      // 找到新增元素x的合适位置k之后进行赋值
        es[k] = key;
}
// 这个方法和上面的操作一样，不多说了
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator .compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

核心方法#

获取#

PriorityQueue 没有查询方法，他有获取数据的 peek 方法。

public E peek() {
    return (E) queue[0];
}

插入#

PriorityQueue 的数据插入过程，就是往二叉堆插入数据的过程。

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    //判断是否需要扩容
    if (i >= queue.length)
        grow(i + 1);
    //
    siftUp(i, e);
    size = i + 1;
    return true;
}

// 上移，x表示新插入元素，k表示新插入元素在数组的位置
private void siftUp(int k, E x) {
    // 如果比较器comparator不为空，则调用siftUpUsingComparator方法进行上移操作
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        // 如果比较器comparator为空，则调用siftUpComparable方法进行上移操作
        siftUpComparable(k, x, queue);
}

插入的代码最终的逻辑是在 siftUpComparable 方法中，而该方法其实就是二叉堆插入逻辑的实现。

删除#

PriorityQueue 的数据删除过程，其实就是将数据从二叉堆中删除的过程。

public boolean remove(Object o) {
    //获取元素的位置
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        //移除元素
        removeAt(i);
        return true;
    }
}

E removeAt(int i) {
    // assert i >= 0 && i < size;
    final Object[] es = queue;
    modCount++;
    int s = --size;
    //要移除的元素正好是尾部的元素，直接移除
    if (s == i) // removed last element
        es[i] = null;
    else {
        //获取最下面的元素
        E moved = (E) es[s];
        es[s] = null;
        //对删除的节点进行下沉操作
        siftDown(i, moved);
        // es[i] == moved 表示删除节点没下沉
        // 意思是其就是该子树最小的节点
        // 这种情况下就需要进行上浮操作
        // 因为可能出现删除节点父节点大于删除节点的情况
        if (es[i] == moved) {
            siftUp(i, moved);
            if (es[i] != moved)
                return moved;
        }
    }
    return null;
}

poll#

public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

扩容#

PriorityQueue 的扩容非常简单。如果原来的容量小于 64，那么扩容为原来的两倍，否则扩容为原来的 1.5 倍。

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

总结#

PriorityQueue 的实现是建立在二叉堆之上的，所以弄懂二叉堆就相当于弄懂了 PriorityQueue
PriorityQueue 默认情况下是最小堆，我们可以改变传入的比较器，使其成为最大堆。
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：
- PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
- PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
- PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
- PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行。

ArrayDeque源码分析#

双向队列实现，底层采用数组实现，实现了 Deque 接口

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

成员变量#

底层使用数组存储

// 数据数组
transient Object[] elements;
// 头结点
transient int head;
// 尾节点
transient int tail;

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法#

//无参构造，默认大小 16
public ArrayDeque() {
    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    elements =
        new Object[(numElements < 1) ? 1 :
                   (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                   numElements + 1];
}

public ArrayDeque(Collection<? extends E> c) {
    this(c.size());
    copyElements(c);
}

核心方法#

offer#

public boolean offer(E e) {
    return offerLast(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[tail] = e;
    if (head == (tail = inc(tail, es.length)))
        grow(1);
}

static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;
    return i;
}

总结#

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

HashMap 源码分析#

HashMap 是 Map 基于哈希散列算法的实现，其在 JDK1.7 中采用了数组+链表的数据结构。在 JDK1.8 中为了提高查询效率，采用了数组+链表+红黑树的数据结构。

继承了 AbstractMap，实现了 Map 接口。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

简介#

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

成员变量#

 /**
   * 缺省table的初始容量大小16
   */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * table 的最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 缺省的负载因子的大小，不建议修改
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 由链表转换为树的树化阈值，当桶(bucket)上的结点数大于这个值时会转成红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 树降级成为链表的阈值，当桶(bucket)上的结点数小于这个值时树转链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 当桶中的bin被树化时最小的table capacity大小
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 哈希表，存储元素的数组，总是2的幂次倍
 */
transient Node<K,V>[] table;

/**
 * 存放具体元素的集
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 *
 * 当前hash表中元素的个数，不等于数组table的长度
 */
transient int size;

/**
 * 哈希表，存储元素的数组，总是2的幂次倍
 */
transient Node<K,V>[] table;

/**
 * 存放具体元素的集
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 *
 * 当前hash表中元素的个数，不等于数组table的长度
 */
transient int size;

构造方法#

 /* ---------------- Public operations -------------- */
//默认的构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


public HashMap(int initialCapacity, float loadFactor) {
    //数据校验：
    //如果initialCapacity小于0 直接抛出非法initialCapacity的异常
    if (initialCapacity < 0){
         throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    }
    //如果initialCapacity超过最大值，给她设置为最大值
    if (initialCapacity > MAXIMUM_CAPACITY){
          initialCapacity = MAXIMUM_CAPACITY;
    }
    //loadFactor 必须大于0
    if (loadFactor <= 0 || Float.isNaN(loadFactor)){
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    }
    //赋值
    this.loadFactor = loadFactor;
    //计算threshold
    /**
     * Returns a power of two size for the given target capacity.
     * 该方法返回一个大于等于当前 initialCapacity 的一个数字，并且这个数字一定是2的次方数
     * 例如给个7 返回8 给个9 返回16
        static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    */
    //找到大于或等于 cap 的最小2的幂
    this.threshold = tableSizeFor(initialCapacity);
}


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

核心方法#

get#

//套娃getNode方法
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    //引用当前HashMap的散列表
    Node<K,V>[] tab;
    //桶中的头元素、临时元素
    Node<K,V> first, e;
    //n ： table长度
    int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //找到key 的桶的位置并且头存在
        (first = tab[(n - 1) & hash]) != null) {
        //头相等，直接返回了
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //头不相等
        if ((e = first.next) != null) {
            //树化了
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //链，向下寻找
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

(n - 1) & hash 等价于对 length 取余，但取余的计算效率没有位运算高

/**
 * 计算键的 hash 值
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash 方法并不是直接用 key.hashCode 方法产生的哈希值， hash 方法中的 (h = key.hashCode()) ^ (h >>> 16) 其实是将 hash 值的高 16 位于低 16 位进行一次异或运算，从而加大低位信息的随机性
我们最终会用 n - 1 和 hash 进行与运算， n - 1 非常小会导致做与操作时，无论 hash 值的高 4 位是什么值，n - 1 & hash 的值的高四位都为 0。也就是说hash 只有低4位参与了计算，高位的计算可以认为是无效的。这样会导致哈希出来的值只受 hash 低 4 位的影响，大大增加哈希碰撞的概率。

put#

/**
 * put套娃putval 但是参数传递的时候有一个方法———— 扰动函数
 * 根据key经过扰动之后得到一个hash值
 * 作用：让key的hash的值的高16位也参与路由运算
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 *
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * 如果定位到的数组位置没有元素 就直接插入。
 * 如果定位到的数组位置有元素就和要插入的 key 比较
 * 如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，
 * 如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入
 * 如果不是就遍历链表插入(插入的是链表尾部)。
 * 当链表长度大于阈值（默认为 8）并且 HashMap 数组长度超过 64 的时候才会执行链表转红黑树的操作，
 * 否则就只是对数组扩容
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    //tab: 引用当前的hashmap 的散列表
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //延迟初始化的逻辑，第一次调用putval 的时候会初始化hashmap对象中最耗费内存的散列表
    //table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0){
       n = (tab = resize()).length;
    }
    //(n - 1) & hash 确定寻找桶的位置 HashMap使用了(n - 1) & hash的方式取数组下标
    //如果寻址找到的桶位刚好是null，直接把k-v封装为node扔进去就行了（此时，这个结点是放在数组中）
    if ((p = tab[i = (n - 1) & hash]) == null){
        tab[i] = newNode(hash, key, value, null);
    }else {//桶已经存在元素了，不为空
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))){
             // 将第一个元素赋值给e，用e来记录
            e = p;
        }
        // hash值不相等，即key不相等；为红黑树结点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//链表节点
            for (int binCount = 0; ; ++binCount) {
                //直接到达链表底部
                if ((e = p.next) == null) {
                    //把新节点插入到尾部
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值(默认为 8 )，执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作
                    //以减少搜索时间。否则，就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //跳出
                    break;
                }
                //在查找的时候如果找到了一个跟key相同的值，并且hash也相同的话直接跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))){
                    break;
                }
                // 用于遍历桶中的链表
                p = e;
            }
        }
         // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { // existing mapping for key
            //记录e 的value
            V oldValue = e.value;

            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null){
                //新的值替换旧的值
                e.value = value;
            }
            //回调
            afterNodeAccess(e);
            //返回旧的值
            return oldValue;
        }
    }
    //结构修改次数，替换node元素的value不计数
    ++modCount;
    // 插入新的元素size自增，如果自增后的值的实际的大小大于阈值则扩容
    if (++size > threshold){
        resize();
    }
    //插入后回调
    afterNodeInsertion(evict);
    return null;
}

如果桶数组 table 为空，那么通过扩容的方式初始化 table 数组。
如果插入的桶为空，那么直接插入。如果插入的桶不为空，那么判断是否与该桶第一个节点相同。如果相同，那么直接退出。否则根据节点不同类型，调用不同的插入方式。如果是红黑树节点，那么调用 putTreeVal 方法。如果是链表节点，那么直接插入链表尾部。在遍历链表的过程中，会判断节点是否存在。如果存在，则会直接跳出循环。
根据条件判断 key 是否存在，如果存在则根据参数判断是否替换旧值。
最后根据参数判断是否扩容。

remove#

//套娃removeNode方法，返回移除的key的value
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}


final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //寻址，判断不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
         //找到key 的桶的位置并且存在数据
        (p = tab[index = (n - 1) & hash]) != null) {
        //node查找到的结果
        //e:当前node的下一个元素
        Node<K,V> node = null, e; K k; V v;

        //第一种情况，当前桶位中的元素就是你要删除的元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))){
             node = p;
        }
        //可能是链表，也可能是树
        else if ((e = p.next) != null) {
            //是数
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //是链表
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //matchValue 是否需要对比value 的值 默认false
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //如果是树
            if (node instanceof TreeNode){
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            }else if (node == p){
                //之前的位置直接指向下一个节点
                tab[index] = node.next;
            }else{
                //当前元素的下一个值，指向要删除元素的下一个位置
                p.next = node.next;
            }
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

定位桶位置
遍历链表并找到键值相等的节点
删除节点

resize扩容#

/**
 * 为什么要使用扩容方法？
 * 为了解决哈希冲突导致的链化影响查询的效率问题，所以使用了扩容
 * 进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。
 * 在编写程序中，要尽量避免 resize。
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    //表示引用扩容之前的hash表
    Node<K,V>[] oldTab = table;
    //表示扩容之前的table的数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //扩容之前的扩容阈值，触发本次扩容的阈值
    int oldThr = threshold;
    //扩容之后的大小、下次触发扩容的扩容阈值
    int newCap, newThr = 0;
    //条件成立，说明hashmap中的散列表已经初始化了，是一次正常的扩容
    if (oldCap > 0) {
        //扩容之前的table数组的大小已经到达最大值了，此时不进行扩容了。
        if (oldCap >= MAXIMUM_CAPACITY) {
            //设置这种情况说明几乎不会再触发扩容了
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //oldCap左移一位，实现数据翻倍，并且赋值给newCap 。
        //此时如果newCap比table数组的最大的小，并且oldCap>=16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY){
            newThr = oldThr << 1; // double threshold / threshold翻倍
        }
    }
    //此时的oldCap == 0，说明hash中的散列表为null
    //1. 通过new HashMap(inintCap,loadFactor)
    //2. 通过new HashMap(inintCap)
    //3. 通过new HashMap(map) 并且这个map是有值的
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //此时的oldCap == 0 oldThr == 0
    //new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16
    }
    //newThr == 0 的时候通过newCap * loadFactor;计算newThr
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})
        //创建出一个更大的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //扩容前存在数据
    if (oldTab != null) {
        //当前的node节点
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //当前桶位中存在数据，但是不确定是链表还是红黑树我们不知道
            if ((e = oldTab[j]) != null) {
                //方便GC
                oldTab[j] = null;
                //第一种情况，当前桶位只有一个元素，没有碰撞，这种情况计算新的位置，放进去
                if (e.next == null){
                    newTab[e.hash & (newCap - 1)] = e;
                }
                //第二种情况：当前桶位树化
                else if (e instanceof TreeNode){
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                }
                //第三种情况：链表
                else { // preserve order
                    //低位的链表：存放在扩容之后的数组的下标位置，与当前数组的下标位置是一致的
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表：存放在扩容之后的数组的下标位置为当前数组下标位置+扩容之前的数组的长度
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //寻址操作
                        //hash-> .... 1 1111
                        //hash-> .... 0 1111
                        //0b          1 0000
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null){
                                 loHead = e;
                            }else{
                              loTail.next = e;
                            }
                              loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //原索引放进新的桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容的时候，寻址很巧妙的利用了hashmap中table的长度为2的幂这一点。将原先的节点哈希值通过与旧的桶长度进行与操作 e.hash & oldCap区分为高位节点（loHead）和低位节点（loTail）。如果为0说明高位的hash值为0，如果为1的话说明高位的hash值为1。那么在重新分配位置的时候，高位hash为0的即使扩容后寻址还是原位置，高位hash为1的，扩容后的位置刚好是现在的位置 + 扩容前桶的大小

HashMap面试题#

HashMap底层实现#

JDK1.8之前#

在JDK1.8之前，HashMap 的底层实现是由数组和链表结合在一起使用的，也就是链表散列 ，HashMap通过key 的hashCode 经过扰动函数（hash()）处理得到一个hash值，然后再通过（ n - 1）& hash 判断当前元素存放的位置（n是数组的长度），如果当前位置存在元素的化，判断插入元素与当前位置的元素的hash值和key是否相同，相同的化直接覆盖，不同则通过拉链法解决冲突。

扰动函数存在的作用就是防止一些实现比较差的hashCode 函数，也可以理解为减少碰撞。

JDK1.7 的扰动函数

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK1.8 的扰动函数

static final int hash(Object key) {
  int h;
  // key.hashCode()：返回散列值也就是hashcode
  // ^ ：按位异或
  // >>>:无符号右移，忽略符号位，空位都以0补齐
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比之后我们不难看出JDK1.8 的性能显然要高于JDK1.7

JDK1.8之后#

插入的时候由数组+链表的方式改成了数组+链表或红黑树
插入的方式改为尾插法
扩容的时候1.7需要对原来的元素重新计算，1.8后采用更为简单的方式，通过高位判断（具体查看扩容源码后面的说明）
当链表的长度大于阈值（缺省为8）的时候，链表会转换为红黑树，以此来减少时间。（转换为红黑树之前会先进行判断，如果数组的长度小于64 的话，会首先进行数组扩容）

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //MIN_TREEIFY_CAPACITY  = 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //....
}

HashMap 的长度为啥是 2 的幂次方#

我们知道，hash值的范围 -2^32 ~ 2^32 - 1 ，显然这个范围我们的内存是放不下的，所以不能直接拿出来用，要进行取模运算。我们首先想到的是取余，如果在取余的时候，除数是2的幂次就等价于于（&）除数减一的与运算，而且还能提高计算的效率，（ hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方）这也就解释了HashMap 的长度为啥是 2 的幂次方

HashMap 多线程操作（扩容）导致死循环的问题#

JDK1.8后，除了对hashmap增加红黑树外，对原有造成死锁的关键原因点（新table复制在头端添加元素）改进为依次在末端添加新的元素。虽然JDK1.8后添加红黑树改进了链表过长查询遍历慢问题和resize时出现导致put死循环的bug，但还是非线性安全的，比如数据丢失等等。因此多线程情况下还是建议使用concurrenthashmap。

死循环主要是发生在transfer里面的

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

死循环原因

如果两个线程同时触发扩容，在移动节点时会导致一个链表中的2个节点相互引用，从而生成环链表

HashMap的扰动函数#

为了解决hash碰撞问题，让高十六位和低十六位做异或运算（二进制位相同为0，不同为1）
为了混合原始哈希码的高位和低位，来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，使高位的信息也被保留下来

链表和红黑树的转换时机#

//将链表转化为红黑树的阀值
static final int TREEIFY_THRESHOLD = 8;

//将红黑树转回为链表的阀值
static final int UNTREEIFY_THRESHOLD = 6;

//将链表转为红黑树的最小entry数组的长度为 64
//当链表的长度 >= 7，且entry数组的长度>= 64时，才会将链表转为红黑树。否则扩容
static final int MIN_TREEIFY_CAPACITY = 64;

为什么不使用AVL树而使用红黑树？#

红黑树和AVL树都是最常用的平衡二叉搜索树，它们的查找、删除、修改都是O(lgn)
AVL树和红黑树有几点比较和区别：
1. AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。
2. 红黑树更适合于插入修改密集型任务。
3. 通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。

解决hash冲突的方法#

拉链法
再hash法：有多个hash函数，如果冲突之后继续hash
扰动函数
开放定址法：一旦发生了冲突，就去寻找下一个空的散列地址。
建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

LinkedHashMap 源码分析#

LinkedHashMap 是在 HashMap 的基础上，增加了对插入元素的链表维护

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

继承了 HashMap 类，实现了 Map 接口

类成员变量#

// 链表头节点
transient LinkedHashMap.Entry<K,V> head;

// 链表尾节点
transient LinkedHashMap.Entry<K,V> tail;

// 通过iterator访问时的顺序，true表示按照访问顺序，false表示按照插入顺序。
final boolean accessOrder;

LinkedHashMap 的类成员变量中增加了 head 和 tail 两个变量，从而实现了对插入元素的链表维护

构造方法#

构造方法都是进行了一些类成员变量的参数设置，这里不再赘述

核心方法#

get#

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //按照访问顺序
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

//把节点挪到链表的尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
      //尾部节点不是 e 节点，那么将其挪到尾部
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

如果 accessOrder 为 true，那么表示访问时就要按照访问顺序去访问。在get 方法中，我们每访问一个节点，我们就会将该节点放入链表尾部，所以我们通过 iterator 访问链表时就是按照访问顺序得到的遍历（越早访问的越在后面）。

put、remove#

LinkedHashMap 没有 remove 和 put方法的实现，都是直接使用了 HashMap 中的的 remove 和 put 方法

遍历#

举例说明

Map<String, String> hashMap = new LinkedHashMap<>();
hashMap.put("name", "thy");
hashMap.put("age", "18");
hashMap.put("address", "henan");
Iterator<String> iterator = hashMap.keySet().iterator();
while (iterator.hasNext()) {
    // name,age,address
    String key = iterator.next();
    System.out.println(key + "," + hashMap.get(key));
}

上面的代码输出之后是：name、age、address，其按照插入顺序访问，但是HashMap却是address、name、age。
要弄清楚为什么那么我们就必须看看其源码是如何实现的。我们先进入 hashMap.keySet().iterator() 这块的代码看看，即 LinkedHashMap.keySet 方法：

//Iterator<String> iterator = hashMap.keySet().iterator();追源码
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new LinkedKeySet();
        keySet = ks;
    }
    return ks;
}

public final Iterator<K> iterator() {
    return new LinkedKeyIterator();
}

public final K next() { return nextNode().getKey(); }

// LinkedHashIterator.nextNode
final LinkedHashMap.Entry<K,V> nextNode() {
    // 将下个节点赋值给 e
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    // 更新 next 属性
    next = e.after;
    return e;
}

从上面的方法我们可以看到其把 next 节点直接赋值给 e 并返回。而每一次进行 nextNode 操作都会更新 next 属性到下一个节点。我们从构造方法可以看到 LinkedHashIterator 的构造方法可以看到，next 节点首次赋值是指向了头结点。
首先从头结点开始遍历，一直遍历到尾节点。而链表的顺序则是我们一直在维护的。默认情况下按照插入顺序排列，如果设置了 accessOrder，那么就按照访问顺序排列。每次访问到一个节点，就将其放到尾部。所以如果设置 accessOrder 为 true，那么越近访问到的节点就会越慢访问到。

关于遍历的坑#

使用下面的方式遍历的时候会抛出异常 ConcurrentModificationException，原因在下面：

public static void main(String[] args) {
    LinkedHashMap<String,Integer> map = new LinkedHashMap<>(10,0.75f,true);
    map.put("1",1);
    map.put("2",2);
    map.put("3",3);
    for (String s : map.keySet()) {
        System.out.println(map.get(s));
    }
}

new LinkedHashMap时，若指定accessorder为true，则get方法会调用afterNodeAccess方法，改变元素的位置，将其插入尾部，同时modCount++，所以调用Iterator 的next时，发现expectedModCount和modCount不一样，抛出ConcurrentModificationException；这是同步容器类的fail-fast机制；
正确的遍历方式如下：

LinkedHashMap<String,Integer> map = new LinkedHashMap<>(10,0.75f,true);
map.put("1",1);
map.put("2",2);
map.put("3",3);
for (Map.Entry<String, Integer> entries : map.entrySet()) {
    System.out.println(entries.getKey() + ":" +  entries.getValue());
}

总结#

LinkedHashMap 相对于 HashMap 维护了一个插入元素的顺序，但其大部分的实现都直接调用了 HashMap 的实现。所以相对于 HashMap 来说，LinkedHashMap 还是比较好理解的。
LinkedHashMap 继承了 HashMap，直接调用了 HashMap 的实现。
LinkedHashMap 维护了插入元素的顺序，可以根据 accessOrder 来设定是按照访问顺序遍历，还是按照插入顺序遍历。

面试常问#

LinkedHashmap是做到了哪两种有序？详细说说怎么实现的
- 插入顺序
  - linkedhashmap重写了hashmap中的newNode方法，在newNode的时候实现有序。
- 访问顺序
  - 在get的时候调用了afterNodeAccess 方法，改变元素的位置，将其插入尾部，同时modCount++，所以在遍历的时候只能使用 EntrySet来遍历，否则会抛出ConcurrentModificationExceptioni

TreeMap源码分析#

TreeMap 是 Map 集合的有序实现，其底层是基于红黑树的实现，能够早 log(n) 时间内完成 get、put 和 remove 操作。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

成员变量#

// 比较器。根据这个比较器决定TreeMap的排序。
// 如果为空，表示按照key做自然排序（最小的在根节点）。
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;

private transient int size = 0;

/**
 * The number of structural modifications to the tree.
 */
    private static final boolean RED   = false;
    private static final boolean BLACK = true;

private transient int modCount = 0;


   static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
   }

从 TreeMap.Entry 的属性我们可以知道其实一个红黑树节点的实现。

构造方法#

四个构造方法

public TreeMap() {
    comparator = null;
}

//带比较器的
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}


public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}


public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
    }
}

核心方法#

get#

//套娃调用getEntry
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
      //核心查找逻辑
        while (p != null) {
            int cmp = k.compareTo(p.key);
            //查找的值小于根节点，找左子树
            if (cmp < 0)
                p = p.left;
            //大于根节点找右子树
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

//使用比较器get
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

put#

红黑树的插入逻辑

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 如果根节点为 null，将新节点设为根节点
    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
    //为 key 在红黑树找到合适的位置
    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;
}

总结#

TreeMap 是 Map 集合的经典红黑树实现，所以弄懂了红黑树的查询、插入、删除，TreeMap 的源码自然不再话下。但要注意的是，TreeMap 的遍历并不是从根节点开始遍历，而是根据 key 的大小从小到大输出，或者从大到小输出。到底是升序还是降序，取决于传入的 Comparator，默认是升序，即从小到大输出。

相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

Collection.synchronized#

Collections.synchronized 的实现原理

 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        private static final long serialVersionUID = 3053995032091335093L;

        final Collection<E> c;  // Backing Collection
        final Object mutex;     // Object on which to synchronize


        public boolean add(E e) {
            synchronized (mutex) {return c.add(e);}
        }
        public boolean remove(Object o) {
            synchronized (mutex) {return c.remove(o);}
        }

里面的mutex是共享的资源对象，每次访问的时候都会加锁：synchronized(mutex){}