参考
https://www.jianshu.com/p/ee0de4c99f87

迭代器原理

要想成为迭代器,必须实现Iterable接口,而且还要重写它的iterator()方法进行返回迭代器对象.
如果不重写foreach方法,就调用默认的方法,这个我们在下面会讲到.
关于spliterator方法不做讲解

Iterable

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() { ... }
}

Iterable的意思是可迭代的;可迭代对象;
Collection集合接口继承它,重写iterator()方法,调用它用来返回一个迭代器,可使用迭代器进行遍历.
也可调用它的foreach方法,它里面有一个for循环也可进行遍历.

下面我们按照顺序先来看看iterator()方法,

Iterator

public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

Iterator的意思是迭代器,说明实现它的类就成了迭代器,必须重写hasNext() next()两个方法.
其中hasNext()是用来判断是否有下一个值,有返回true(才能往下进行迭代),无返回false(终止迭代).
next()方法是用来返回下一个要遍历的值,如果hasNext()为true,才能执行next()来返回下一个值.(这时有明确的先后关系的)

所以说迭代器遍历数据的原理,遍历数据的顺序

先通过iterator()获取迭代器,
调用迭代器的hasNext()方法,看是否能迭代,
如果可迭代,调用迭代器的next()方法返回下一个迭代的值,
执行循环体,执行完之后,再进行判断hasNext()方法 …

for循环就是使用迭代器来循环的,其本质上和while循环无太大区别,只不过简化了写法,
下面是两种用法示例,其效果是相同的.(这里的HashMap在后面会进行讲解)

HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");
// 方法1
Set<Map.Entry<String, String>> entries = hashMap.entrySet();
for (Map.Entry<String,String> e:entries)
{
    System.out.println(e);
}

// 方法2
Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();
Map.Entry<String, String> e2;
while (iterator.hasNext())
{
    e2=iterator.next();
    System.out.println(e2);
}

分析完了iterator(),我们来分析一下foreach方法,它的参数是Consumer,下面我们来看一下

Consumer

/* 拿出`Iterable`的foreach方法,方便查看 */
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

/* 这是一个函数接口 */
@FunctionalInterface
public interface Consumer<T> {
    void accept(T t);

    default Consumer<T> andThen(Consumer<? super T> after) {
        Objects.requireNonNull(after);
        return (T t) -> { accept(t); after.accept(t); };
    }
}

下面进行改写

HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");
// 全写
hashMap.entrySet().forEach(new Consumer<Map.Entry<String, String>>()
{
    @Override
    public void accept(Map.Entry<String, String> e)
    {
        System.out.println(e);
    }
});
// 简写,Java8 函数式编程写法
hashMap.entrySet().foreach(e ->{
    System.out.println(e);
});

当然你也可以重写它的foreach方法,这里本质上我们将讲完了集合是如果遍历的数据.

ArrayList

extends,implements关系

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public interface List<E> extends Collection<E> {

public interface Collection<E> extends Iterable<E> {

实现了List(列表)接口,
List继承Collection(集合)节口,
而Collection节口又继承了Iterable(迭代器)接口,才可以使迭代成为可能.

基本属性

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;

private int size;

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

protected transient int modCount = 0;

可以看出,默认容量大小是10.后面会讲到最小为10.
内部是由Object数组构成的.
size用于记录集合的大小.添加+1,移除-1,清除=0.
modCount结构改变一次,就+1

构造方法

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

无参构造默认为空.
有参构造可指定集合默认大小.

增

尾插入

public boolean add(E e) {
    // 要想知道此方法干什么的,就要进入方法
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 进入之后,要先执行`calculateCapacity(elementData, minCapacity)`
    // 再把执行的结果传入ensureExplicitCapacity方法
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果elementData数组内容为空{}
    // 默认容量是10, minCapacity为`size + 1`
    // 返回二者最大的值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // 不为空,直接返回`size + 1`
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // 确定可以插入数据, 结构将要改变, 记录数+1
    modCount++;

    // 如果容量大于数组的长度,进行扩容操作
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // 获取原长度
    int oldCapacity = elementData.length;
    // 1.5倍扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 扩容后还是没有`size + 1`大,也就是1.5扩容后超出Integer范围,为负数了.
    // 新扩容大小为`size + 1`
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    //如果扩容后,比MAX_ARRAY_SIZE还大(MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8)
    // 新扩容最大为Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // 进行扩容,把原数组大小改为newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

由上面注释,我们可以知道,在插入的时候,会进行对数组大小初始化,也就是容量.
在插入之前先进行试探,如果超出数组长度进行1.5倍扩容.
如果扩容后大小还是没试探数(size + 1)大的话,扩容就为试探数.
如果扩容后大小超出默认最大值,扩容大小就为Integer.MAX_VALUE
添加成功会返回true,内部的结构变化记录数modCount在扩容,插入前会+1

指定位置插入

public void add(int index, E element) {
    // 检查下标index是否符合要求
    rangeCheckForAdd(index);

    // 进行扩容,和 结构记录数+1
    ensureCapacityInternal(size + 1);

    // 这个我下面来举例子说明
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 指定位置插入
    elementData[index] = element;

    // 大小+1
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

关于上面的System.arraycopy(elementData, index, elementData, index + 1,size - index);
举个例子:
例如长度为10的原数组,数据为{11,22,33,null,null,null,null,null,null,null}此时size=3.
执行add(1,88);数组就会变为{11,88,22,33,null,null,null,null,null,null}此时size=4.
参数含义

原数组
从元数据的起始位置开始
目标数组
目标数组的开始起始位置
要copy的数组的长度

也就是把>=index的数据下标都+1了,在index位置插入你指定的数据.

删

删除指定的第一个数据

public boolean remove(Object o) {
    
    // 直接查找,找到进行删除,返回true.
    // 这里删除的是第一个数据,所以最多只能删除一个.

    // 如果找不到,则返回false.
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    // 数据结构要改变,记录数+1
    modCount++;

    // 计算下标要改变的元素数量
    // 把numMoved个数据的下标都-1，往前移一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
         
    // 把最后一个数据指针为null,进行垃圾回收
    elementData[--size] = null;
     // {11,22,33,44}
     // {11,33,44,44}
     // {11,33,44,null}
}

指定位置进行删除

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;

    return oldValue;
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
    return (E) elementData[index];
}

同上,主要是删除前检查指定的index是否符合.

改

指定位置修改

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

private void rangeCheck(int index) {
    // 下标越界抛异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

把指定位置的数据进行修改,把旧值进行返回.

查

获取指定位置数据

public E get(int index) {
    // 检查是否符合,下标越界抛异常
    rangeCheck(index);

    // 直接返回指定位置数据
    return elementData(index);
}

这个没什么好说的,直接获取值.

其他方法

交集，差集，并集

public static void main(String[] args)
    {
        // 下面操作只对list1进行改变，不会改变list2

        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3));
        List<Integer> list2 = new ArrayList<>(Arrays.asList(3, 4, 5));
        //交集
        //list1.retainAll(list2);
        //System.out.println(list1);//[3]

        //差集
        //list1.removeAll(list2);
        //System.out.println(list1);//[1, 2]

        //并集
        //list1.addAll(list2);
        //System.out.println(list1);//[1, 2, 3, 3, 4, 5]
    }

size返回集合大小

1
2
3

public int size() {
    return size;
}

clear清空数据

public void clear() {
    modCount++;

    // 设为null,方便垃圾回收
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    // 大小为0
    size = 0;
}

isEmpty检查是否为空

1
2
3

public boolean isEmpty() {
    return size == 0;
}

indexOf返回第一个指定数据的下标

public int indexOf(Object o) {
    // 查找,找到返回下标,找不到返回-1
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf返回最后一个指定数据的下标

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

contains是否含有某个数据

1
2
3

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

subList截取集合

如果集合是{a,b,c,d,e},截取subList(2,3);//{c}
所以,区间表示[2,3)包含前面的,不包含后面的.(前包后不包)

public List<E> subList(int fromIndex, int toIndex) {
    // 检查下标是否符合要求,
    subListRangeCheck(fromIndex, toIndex, size);
    
    // 返回截取的新集合,所以不会改变原集合.
    return new SubList(this, 0, fromIndex, toIndex);
}

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}

LinkedList

继承关系

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

public interface List<E> extends Collection<E> {

public interface Collection<E> extends Iterable<E> {

public interface Deque<E> extends Queue<E> {

public interface Queue<E> extends Collection<E> {

实现了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;

右上面可以看到,他是双向的链接,内部由头和尾节点进行维护.

构造方法

1 2	public LinkedList() { }

增

头插入

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public void push(E e) {
    addFirst(e);
}

public void addFirst(E e) {
    // 进入头插入方法
    linkFirst(e);
}

private void linkFirst(E e) {
    // 获取头节点
    final Node<E> f = first;

    // 构造节点,再进行插入
    // 节点的上一个为null,下一个为头节点
    final Node<E> newNode = new Node<>(null, e, f);

    // 头节点指针指向当前节点
    first = newNode;
    if (f == null)
        // 如果插入的是第一个数据
        // 将首尾节点都指向当前节点
        last = newNode;
    else
        // 如果不是第一个数据
        // 将插入前的头节点上一个节点指针指向当前节点
        f.prev = newNode;

    // 链表大小+1
    size++;

    // 结构记录数+1
    modCount++;
}

尾插入

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

public boolean add(E e) {
    linkLast(e);
    return true;
}

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

public void addLast(E e) {
    linkLast(e);
}

void linkLast(E e) {
    // 获取尾节点
    final Node<E> l = last;

    // 构造节点,再进行插入
    // 节点的上一个为尾节点,下一个为null
    final Node<E> newNode = new Node<>(l, e, null);
    
    // 尾节点指针指向当前节点
    last = newNode;

    if (l == null)
        // 如果插入的是第一个数据
        // 将首尾节点都指向当前节点
        first = newNode;
    else
        // 如果不是第一个数据
        // 进行追加
        l.next = newNode;

    // 链表大小+1
    size++;

    // 结构记录数+1
    modCount++;
}

public boolean add(E e) {
    // 添加节点至尾部,并作为最后一个节点
    linkLast(e);

    // 添加成功返回true
    return true;
}

可以看出,如果当前插入的是第一个节点,将首尾节点都指向当前节点.
如果不是,就将尾节点指向当前节点,插入前的尾节点的下一个节点指向当前节点,
也就是把当前节点追加到链表最后.

指向位置插入

public void add(int index, E element) {
    // 检查是否合法
    checkPositionIndex(index);

    if (index == size)
        // 如果等于size,直接在链表后追加,
        // 这个我们已经上面讲过了.
        linkLast(element);
    else
        // 先执行`node(index)`获取到要插入位置的节点,
        // 把节点作为linkBefore方法的第二个参数进行插入数据.
        linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {
    // 下标不合法要求,抛出索引越界异常
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    // 不同数组的是它可以等于size的大小.
    // 范围在区间[0,size]
    return index >= 0 && index <= size;
}

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

void linkBefore(E e, Node<E> succ) {
    // 获取指定位置的上一个节点
    final Node<E> pred = succ.prev;

    // 构造节点
    final Node<E> newNode = new Node<>(pred, e, succ);

    // 在插入位置的前后进行连接,
    // 如果上一个节点为空,就把当前节点设为头节点.
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;

    // 大小+1,结构记录数+1
    size++;
    modCount++;
}

删

删除第一个

为空抛异常

public E remove() {
    // 默认删除第一个,表示它是FIFO(First In First Out先进先出)
    return removeFirst();
}

public E pop() {
    return removeFirst();
}

public E removeFirst() {
    // 获取头节点
    final Node<E> f = first;
    
    // 头节点为空抛异常
    if (f == null)
        throw new NoSuchElementException();
    
    // 取消非空的头节点f的连接,并返回取消节点的值
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {

    // 获取头节点的值,用于返回
    final E element = f.item;
    
    // 获取头节点的下一个节点
    final Node<E> next = f.next;
    
    // 使头节点与链表断开,方便垃圾回收
    f.item = null;
    f.next = null;
    
    // 头节点指向下一个节点
    first = next;
    
    if (next == null)
        // 如果删除的是最后一个值,last指针也指向空.
        // 链表头尾都指向空,表示无数据
        last = null;
    else
        // 下一个节点非空,
        // 让下一个节点与原头节点断开连接.
        next.prev = null;
        
    // 大小-1,结构记录数+1,返回删除的值.
    size--;
    modCount++;
    return element;
}

为空返回null

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

删除最后一个

为空抛异常

public E removeLast() {
    // 获取尾节点
    final Node<E> l = last;
    // 尾节点为空抛异常
    if (l == null)
        throw new NoSuchElementException();
    // 取消非空的尾节点l的连接,并返回取消节点的值
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    // 获取尾节点的值,用于返回
    final E element = l.item;
    
    // 获取尾节点的上一个节点
    final Node<E> prev = l.prev;
    
    // 使尾节点与链表断开,方便垃圾回收
    l.item = null;
    l.prev = null;
    
    // 尾节点指向上一个节点
    last = prev;
    if (prev == null)
        // 如果删除的是最后一个值,first指针也指向空.
        // 链表头尾都指向空,表示无数据
        first = null;
    else
        // 上一个节点非空,
        // 让上一个节点与原头节点断开连接.
        prev.next = null;
        
    // 大小-1,结构记录数+1,返回删除的值.
    size--;
    modCount++;
    return element;
}

为空返回null

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

删除指定位置元素

public E remove(int index) {
    // 检查下标是否符合,不同于插入的是`范围[0,size-1]`
    checkElementIndex(index);
    
    // node方法在前面已经说了,查找到index位置的节点,
    // 并作为unlink方法的参数,进行删除节点,并返回数据.
    return unlink(node(index));
}

private void checkElementIndex(int index) {
    // 下标不符合,抛出索引越界异常
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    // 不同于插入的是`它不可以等于size的大小`.
    // 范围在区间[0,size-1]
    return index >= 0 && index < size;
}

E unlink(Node<E> x) {
    // 获取指定位置节点的值,用于返回
    final E element = x.item;
    
    // 分别获取到它的上一个节点,和下一个节点.
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 这里把`指定位置的节点称为'我'`
    if (prev == null) {
        // 如果我的上一个节点为空,表示我是头节点,
        // 我删除之后,头节点就要指向我的下一个节点.
        first = next;
    } else {
        // 如果我不是头节点,
        // 我被删除了,我的上一个节点和下一个节点需要建立连接,
        // 方法是:使我的上一个节点的next指针指向下一个节点,
        prev.next = next;
        // 再使我与上一个节点断开连接.
        x.prev = null;
    }

    // 道理同上,
    if (next == null) {
        // 是尾节点,
        // 我被删除了,尾节点指向我的上一个节点.
        last = prev;
    } else {
        // 不是尾节点,
        // 我被删除了,我的上下节点也是需要建立连接,
        // 方法是:使下节点的prev指向上节点
        next.prev = prev;
        // 再使我与下一个节点断开连接.
        x.next = null;
    }

    // 清除node节点保存的数据,
    // 因为在之前我们讲过,Node节点里面只有三个属性{值,上,下}
    // 所以,前面设置了上下指向null并与链表断开连接,这里再设置值为null,
    // 这个节点就要被垃圾回收,起到了删除节点的作用.
    x.item = null;
    
    // 大小-1,结构记录数+1,返回删除的值.
    size--;
    modCount++;
    return element;
}

删除指定的第一个数据

public boolean removeFirstOccurrence(Object o) {
    // 删除指定的第一个数据,其实也就是`remove(Object o)`方法.
    // 删除成功返回true,否则false.
    return remove(o);
}

public boolean remove(Object o) {
    // 从前往后查找,找到进行删除,返回true.
    // 这里删除的是第一个数据.
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // 在上面我们已经提到,
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 如果找不到,则返回false.
    return false;
}

删除指定的最后一个数据

public boolean removeLastOccurrence(Object o) {
    // 从后往前查找,找到进行删除,返回true.
    // 这里删除的是最后一个数据.
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 如果找不到,则返回false.
    return false;
}

改

指定位置修改

public E set(int index, E element) {
    // 检查下标是否符合,不同于插入的是`范围[0,size-1]`
    checkElementIndex(index);
    
    // 获取的指定位置的节点,
    Node<E> x = node(index);
    
    // 获取该节点的值进行返回,
    E oldVal = x.item;
    
    // 把节点值进行替换为新数据.
    x.item = element;
    return oldVal;
}

查

获取第一个节点数据

为空抛异常

public E element() {
    return getFirst();
}

public E getFirst() {
    // 获取头节点,为空抛异常.
    // 非空直接把值返回.
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

为空返回null

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

获取最后一个节点数据

为空抛异常

public E getLast() {
    // 获取尾节点,为空抛异常.
    // 非空直接把值返回.
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

为空返回null

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

获取指定位置节点数据

public E get(int index) {
    // 检查下标是否符合,不同于插入的是`范围[0,size-1]`
    checkElementIndex(index);
    
    // 通过`node(index)`找到指定位置的节点,
    // 并返回节点的值.
    return node(index).item;
}

其他方法

size返回集合大小

1
2
3

public int size() {
    return size;
}

clear清空数据

public void clear() {
    
    // 从头节点开始往后循环,直至找到为null的节点.
    for (Node<E> x = first; x != null; ) {
        // 获取下一个节点
        Node<E> next = x.next;
        // 把三个属性设为空,断开连接并GC
        x.item = null;
        x.next = null;
        x.prev = null;
        // 把当前循环节点指向下一个节点.
        x = next;
    }
    
    // 头尾节点指向为空,表示集合为空.
    first = last = null;
    // 大小为0
    size = 0;
    
    // 结构记录数+1
    modCount++;
}

indexOf返回第一个指定数据的下标

public int indexOf(Object o) {
    // 初始化index,如果找到数据进行返回使用,
    // 从前往后循环查找数据,并返回下标.
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    // 如果找不到返回-1
    return -1;
}

lastIndexOf返回最后一个指定数据的下标

public int lastIndexOf(Object o) {
    // 初始化index,如果找到数据进行返回使用,
    // 从后往前循环查找数据,并返回下标.
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    // 如果找不到返回-1
    return -1;
}

contains是否含有某个数据

1
2
3

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

Vector

同ArrayList一样,只不过Vector的方法都加了synchronized,数组的扩容机制不同(默认2倍扩容).
只要看到了ArrayList,Vector也就好理解了,这里就不做过多的阐述了.

extends,implements关系

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

和ArrayList继承关系相同.

基本属性

// 底层数组维护,长度默认10
protected Object[] elementData;

// 记录元素个数,作为size()返回
protected int elementCount;

// 集合的增量,扩容时使用,默认0
protected int capacityIncrement;

// 默认数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

同ArrayList一样,也是由数组进行维护,但是增加了扩容增量的概念,后面会讲到.
为什么要有Vector呢? 下面我们来继续往下看

构造方法

public Vector() {
    this(10);
}

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

由上可以看出,底层维护的数组长度默认10,扩容增量默认0

增

尾插入

// 无返回值
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

// 有返回值,成功插入返回true
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 如果指定增量,并且增量>0,扩容后大小`原容量+增量`
    // 否则,扩容后大小`2倍原容量`,增量默认为0,也就是默认2倍扩容.
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

指定位置插入

public void add(int index, E element) {
    insertElementAt(element, index);
}

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

删

删除指定下标数据

// 返回被删除的值
public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

// 无返回值
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

删除第一个指定数据

public boolean remove(Object o) {
    return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

删除全部

public void clear() {
    removeAllElements();
}

public synchronized void removeAllElements() {
    modCount++;
    // Let gc do its work
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

改

修改指定位置数据

// 返回原值
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 无返回值
public synchronized void setElementAt(E obj, int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    elementData[index] = obj;
}

查

返回第一个数据

public synchronized E firstElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(0);
}

返回最后一个数据

public synchronized E lastElement() {
    if (elementCount == 0) {
        throw new NoSuchElementException();
    }
    return elementData(elementCount - 1);
}

返回指定位置数据

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

    return elementData(index);
}

public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

其他方法

size返回集合大小

1
2
3

public synchronized int size() {
    return elementCount;
}

setSize设置集合大小

public synchronized void setSize(int newSize) {
    modCount++;
    if (newSize > elementCount) {
        // 如果`新大小 大于 原集合大小`
        // 进入扩容方法,判断是否需要扩容,
        // 大于内部数据长度就进行扩容,
        // 只是进行扩容,并不会改变集合的大小,
        // 下面指定`elementCount = newSize;`才会改变集合大小.
        ensureCapacityHelper(newSize);
    } else {
        // 如果小于原集合大小,就进行删除数据,
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    // 改变集合的大小.
    // 如果原数据{a,b,c,d}默认容量10.
    // 执行`setSize(5);`,因为5<10,不会进行扩容,
    // 集合变为{a,b,c,d,null},容量不变还是10,集合大小变为5了.
    
    // 如果执行`setSize(2);`,
    // 集合变为{a,b},容量10,集合大小变为2了
    elementCount = newSize;
}

isEmpty

1
2
3

public synchronized boolean isEmpty() {
    return elementCount == 0;
}

indexOf

返回第一个数据的下标

1
2
3

public int indexOf(Object o) {
    return indexOf(o, 0);
}

返回[index,elementCount-1]第一个数据的下标

public synchronized int indexOf(Object o, int index) {
    if (o == null) {
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf

返回最后一个数据的下标

1
2
3

public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

返回[0,index]最后一个数据的下标

public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

capacity返回容量

也就是内部数组的长度

1
2
3

public synchronized int capacity() {
    return elementData.length;
}

contains是否含有某个数据

1
2
3

public boolean contains(Object o) {
    return indexOf(o, 0) >= 0;
}

subList截取集合

如果集合是{a,b,c,d,e},截取subList(2,3);//{c}
所以,区间表示[2,3)包含前面的,不包含后面的.(前包后不包)

public synchronized List<E> subList(int fromIndex, int toIndex) {
    return Collections.synchronizedList(super.subList(fromIndex, toIndex),
                                        this);
}

trimToSize内部数组长度变为集合大小

public synchronized void trimToSize() {
    modCount++;
    int oldCapacity = elementData.length;
    if (elementCount < oldCapacity) {
        elementData = Arrays.copyOf(elementData, elementCount);
    }
}

HashMap

extends,implements关系

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

属性

// 把key和value封装成Node节点,数组的长度是2次幂.
// 每个Node本质都是一个单向链表.
transient Node<K,V>[] table;

// 负载因子
final float loadFactor;

// 阈(yù)值,达到阈值会进行扩容操作.
// 如果不大于容量极限的情况下,阈值=数组长度*负载因子
int threshold;

// HashMap的大小,它代表HashMap保存的键值对的多少
transient int size;

// 结构改变记录数,HashMap被改变的次数
transient int modCount;

// 默认的初始容量.
// 直接写出1<<4而不写成16,是因为位运算速度快,写成16也要把16转成2进制进行处理.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 负载因子的默认大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// HashMap容量极限2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 链表数量等于8时会转为红黑树储存
static final int TREEIFY_THRESHOLD = 8;

// 链表长度小于6时会转为单向链表储存
static final int UNTREEIFY_THRESHOLD = 6;

// 红黑树最小长度为64
static final int MIN_TREEIFY_CAPACITY = 64;

/*
因为Node是继承Map.Entry<K,V>的,`static class Node<K,V> implements Map.Entry<K,V>`
所以,它是一个Set集合,里面无序不重复的放入了Node节点.
Node节点封装了key,value,它的使用会在后面目录`查`中的entrySet方法中用到.
*/
transient Set<Map.Entry<K,V>> entrySet;

构造函数

HashMap()

1
2
3

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

无参构造方法
构造一个空的HashMap，初始容量为16，负载因子为0.75
注意:(此时还未指定初始容量,在扩容时指定默认16)

HashMap(int initialCapacity)

1
2
3

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

构造一个空的HashMap，指定容量，负载因子也为0.75
HashMap(int initialCapacity)这个构造方法调用了下面的构造方法.

HashMap(int initialCapacity, float loadFactor)

// 3.构造一个空的初始容量为initialCapacity，负载因子为loadFactor的HashMap
public HashMap(int initialCapacity, float loadFactor) {
    // 判断指定容量是否合法
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 容量最大为 MAXIMUM_CAPACITY,也就是2^30
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 判断负载因子是否合法
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 
    this.loadFactor = loadFactor;
    // 初始化阈值
    this.threshold = tableSizeFor(initialCapacity);
}

构造一个空的HashMap，指定容量，指定负载因子
设置阈值,阈值=容量*负载因子,当HashMap的size到了阈值时,就要进行resize,也就是扩容.
tableSizeFor(initialCapacity)的主要功能就是返回一个2的次方数,如给定18,返回2的5次方(32)

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

注意 HashMap要求容量必须是2的次方数.
这里cap为指定的容量,并且范围是[0,MAXIMUM_CAPACITY],如果指定容量小于等于2^n,就返回2^n,这里n取[0,30]
直接演示一下,为什么要使用右移运算,因为int是32位,
假设开始的n为00000000 000001xx xxxxxxxx xxxxxxxx,这里我们只管最前面那个1的值,后面都不管.
n |= n >>> 1;可以理解为n = n | (n >>> 1);
>>>右移运算可以理解为无论正负右移n位,右边去除n位,左边补n个0
按位或运算只要有一个是1,结果就为1
如果还是不懂这两个运算,可以查看
位运算

第一次右移n |= n >>> 1;
00000000 000001xx xxxxxxxx xxxxxxxx
00000000 0000011x xxxxxxxx xxxxxxxx
第二次右移n |= n >>> 2;
00000000 0000011x xxxxxxxx xxxxxxxx
00000000 00000111 1xxxxxxx xxxxxxxx
第三次右移n |= n >>> 4;
00000000 0000011x xxxxxxxx xxxxxxxx
00000000 00000111 11111xxx xxxxxxxx
…

由上我们可知,n为指定的容量-1,右移31次,可以把第一个1后面全部变为1,最后+1就成了2的次方数.

HashMap(Map<? extends K, ? extends V> m)

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

构造一个和指定Map有相同映射的HashMap，初始容量能充足的容下指定的Map,负载因子为0.75
直接看putMapEntries(m, false);


/**
 * 将m的所有元素存入本HashMap实例中
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //得到 m 中元素的个数
    int s = m.size();
    //当 m 中有元素时，则需将map中元素放入本HashMap实例。
    if (s > 0) {
        // 判断table是否已经初始化，如果未初始化，则先初始化一些变量。（table初始化是在put时）
        if (table == null) {
            // 根据待插入的map 的 size 计算要创建的　HashMap 的容量。
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 把要创建的　HashMap 的容量存在　threshold　中
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果table初始化过，因为别的函数也会调用它，所以有可能HashMap已经被初始化过了。
        // 判断待插入的　map 的 size,若　size 大于　threshold，则先进行　resize()，进行扩容
        else if (s > threshold)
            resize();
        //然后就开始遍历 带插入的 map ，将每一个 <Key ,Value> 插入到本HashMap实例。
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // put(K,V)也是调用　putVal　函数进行元素的插入
            putVal(hash(key), key, value, false, evict);
        }
    }
}

在下面目录增中介绍resize扩容和putVal添加

增

这里是HashMap最难理解的两个方法,resize扩容和putVal添加,当然红黑树就不看了.

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

进入putVal插入方法之前,先看一下下面的hash操作

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里是使高16位与低16位进行异或运算,异或运算同为0,不同才为1,
举个例子:
1111 1111 1111 1111 0100 1100 0000 1010=原hashcode
0000 0000 0000 0000 1111 1111 1111 1111=右移16位
1111 1111 1111 1111 1011 0011 1111 0101=异或结果
这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，
这样高位的信息被变相的保留了下来。掺杂的元素多了，那么生成的hash值的随机性会增大(冲突几率减小)。

刚才我们漏掉了resize()和putVal()两个函数，现在我们按顺序分析一波：

resize扩容

首先resize() ,先看一下哪些函数调用了resize()，从而在整体上有个概念：
在这里插入图片描述

    final Node<K,V>[] resize() {
        // 保存当前table
        Node<K,V>[] oldTab = table;
        // 保存当前table的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 保存当前阈值
        int oldThr = threshold;
        // 初始化新的table容量和阈值 
        int newCap, newThr = 0;
        /*
        1. resize（）函数在size　> threshold时被调用。oldCap大于 0 代表原来的 table 表非空，
           oldCap 为原表的大小，oldThr（threshold） 为 oldCap × load_factor
        */
        if (oldCap > 0) {
            // 若旧table容量已超过最大容量，更新阈值为Integer.MAX_VALUE（最大整形值），这样以后就不会自动扩容了。
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
             // 容量翻倍，使用左移，效率更高
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 阈值翻倍
                newThr = oldThr << 1; // double threshold
        }
        /*
        2. resize（）函数在table为空被调用。oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为      
           HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
           或 HashMap(Map<? extends K, ? extends V> m)，导致 oldTab 为 null，oldCap 为0， oldThr 为用户指定的 HashMap的初始容量。
    　　*/
        else if (oldThr > 0) // 初始容量设置为阈值
            //当table没初始化时，threshold持有初始容量。还记得构造函数中的threshold = tableSizeFor(t)么;
            newCap = oldThr;
        /*
        3. resize（）函数在table为空被调用。oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()无参构造函数创建的　HashMap，所有值均采用默认值，oldTab（Table）表为空，oldCap为0，oldThr等于0，
        */
        else {               // 初始阈值为零表示使用默认值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 新阈值为0,也就是上面阈值翻倍之后>=MAXIMUM_CAPACITY时,或原容量小于16时
        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"})
        // 初始化table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {// 原表有数据
            // 把 oldTab 中的节点　reHash 到　newTab 中去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 若节点是单个节点，直接在 newTab　中进行重定位
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 若节点是　TreeNode 节点，要进行 红黑树的 rehash　操作
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 若是链表，进行链表的 rehash　操作
                    else {
                        // 记录rehash之后,索引不变的链表,下标j
                        Node<K,V> loHead = null, loTail = null;
                        
                        // 记录rehash之后,索引改变的链表,下标j+oldCap
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
                        do {
                            next = e.next;
                            // 根据算法　e.hash & oldCap 判断节点位置rehash　后是否发生改变
                            //最高位==0，这是索引不变的链表。
                            if ((e.hash & oldCap) == 0) { 
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //最高位==1 （这是索引发生改变的链表）
                            else {  
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {  // 原bucket位置的尾指针不为空(即还有node)  
                            loTail.next = null; // 链表最后得有个null,表示最后一个节点
                            newTab[j] = loHead; // 链表头指针放在新桶的相同下标(j)处
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // rehash　后节点新的位置一定为原来基础上加上　oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
}

xxxxxxxx xxxxxxxx xxxxxxxx xxx10111 =假设当前循环节点e.hash
00000000 00000000 00000000 00010000 =16
00000000 00000000 00000000 00001111 =15
00000000 00000000 00000000 00000111 =7原定位`e.hash & 15`

00000000 00000000 00000000 00100000 =32(2倍扩容)
00000000 00000000 00000000 00011111 =31
00000000 00000000 00000000 00001111 =7+16 原定位`e.hash & 31`

扩容的情况

size > threshold,进行2倍扩容(不一定)
table==null(初始化)

扩容(resize)其实就是重新计算容量；而这个扩容是计算出所需容器的大小之后重新定义一个新的容器，将原来容器中的元素放入其中。

putVal添加

下面介绍putVal方法,先介绍他们
参数1:hashkey的hashcode高16位与低16位异或运算得出的一个int值
参数2:keykey
参数3:valuevalue
参数4:onlyIfAbsent它翻译为只有在没有,为true表示不覆盖,为false表示覆盖旧值
参数5:evict它翻译为逐出,为false表示创建模式,为true则为非创建模式

调用它的其中三种情况:

构造函数HashMap(Map<? extends K, ? extends V> m)中调用putMapEntries(m, false);,会调用putVal(hash(key), key, value, false, evict);
把传入的Map构造成HashMap时,把Map中的值添加到HashMap中,表示不覆盖,是创建模式.
添加数据put(K key, V value)中调用putVal(hash(key), key, value, false, true);
表示覆盖旧值,不是创建模式.

添加数据putIfAbsent(K key, V value)(实现Map接口方法)中调用putVal(hash(key), key, value, true, true);
表示不覆盖旧值,不是创建模式.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /*
    1. 表为空,初始化表
    */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /*
    2. 定位的位置为空,直接在此位置插入
    */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    /*
    3. 定义的位置有节点了,下面要分情况处理
    */
    else {
        Node<K,V> e; K k;
        // 情况1,当前定位的节点是链表的第一个节点,获取此节点.
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 情况2,当前定位的节点是红黑树节点,使用`putTreeVal`去红黑树中找到我们的节点.
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 情况3,当前定位的节点不是第一个节点,需要进行遍历查找我们想要的节点.
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // (1)找到链表的尾端还没找到,直接构造一个新节点,进行尾插入.
                    // 插入之后,链表长度>=8的时候,链表转化为红黑树
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // (2)找到我们要插入的节点,跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 我们获取的那个节点不为空,返回旧值.
        // 如果旧值不为空,或入参onlyIfAbsent为false,替换新值.
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//LinkedHashMap会用到
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);//LinkedHashMap会用到
    return null;
}

删

删除指定key节点

public V remove(Object key) {
    Node<K,V> e;
    // 找到要删除的数据,删除并返回value,找不到返回null
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/*
matchValue 如果为true，则仅在值相等时删除
movable 如果为false，则在删除时不移动其他节点

remove(Object key): 找到key就删除,并移动其他节点.
remove(Object key, Object value): 匹配key,并匹配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 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        /*
        步骤1, 找到我们需要的节点
        */
        
        // 1.1 定位的链表头就是我们需要的数据,获取此节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 1.2 链表头不是我们要的数据,链的下一个节点有数据,继续往下找,
        //     在找之前,先判断是链表还是红黑树
        else if ((e = p.next) != null) {
            // 1. 如果链表头是红黑树节点,使用红黑树查找法,找到并返回,获取此节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 2. 否则为链表,循环往下找,找到并返回.
            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);
            }
        }
        
        /*
        步骤2, 把我们找到的节点进行删除
        */
        
        // 找到了节点,并确定与我们要找节点的value匹配或设置不匹配value,就进行删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //(1) 找到的是红黑树节点,进行红黑树删除操作 
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //(2) 找到的是头节点,把定位的节点指向链表头节点的下一个节点.
            else if (node == p)
                tab[index] = node.next;
            //(3) 因为p=e,然后e=e.next=node,
            //    所以p.next原本指向node,现在指向node的下一个节点,
            //    从而实现断开链接
            else
                p.next = node.next;
            
            // 结构改变,结构记录数+1
            // 大小-1
            // 返回删除的节点
            ++modCount;
            --size;
            afterNodeRemoval(node);// LinkedHashMap会用到
            return node;
        }
    }
    /*
    除以上情况,则返回null
    */
    return null;
}

删除指定key,value节点

@Override// 实现了Map接口
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

清空数据

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

改

修改指定key节点的value

@Override// 实现Map接口方法
public V replace(K key, V value) {
    Node<K,V> e;
    /*
    1. 如果找到,替换新值,返回旧值,
    2. 找不到返回null
    */
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);// LinkedHashMap会用到
        return oldValue;
    }
    return null;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /*
    1. 表中有数据,并且定位节点有数据,找到节点进行返回
    */
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 情况1,当前定位的节点是链表的第一个节点,获取此节点.
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 情况2,链表的第一个节点是红黑树节点,获取此红黑树节点.
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 情况3,依次遍历节点,找到进行返回.
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    /*
    2. 以上不满足,返回空
    */
    return null;
}

修改指定key,value节点的value

@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    /*
    和删除方法的差不多,匹配key也要匹配value才进行删除替换操作,
    注意它返回布尔值,替换成功返回true,否则false
    */
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

查

根据key获取value

public V get(Object key) {
    Node<K,V> e;
    // 1. 获取节点为空,返回空
    // 2. 获取不为空,直接返回节点的值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

(重要)entrySet获取所有key和value

HashMap的entrySet与keySet区别?源码分析

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

keySet获取所有key

同上

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

values获取所有value

同上

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

其他方法

size返回集合大小

1
2
3

public int size() {
    return size;
}

isEmpty检查是否为空

1
2
3

public boolean isEmpty() {
    return size == 0;
}

containsKey是否含有某个key

1
2
3

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

containsValue是否含有某个value

从Node数组0,依次往后找,找到链表,再循环链表,直到找到value进行返回true.

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

LinkedHashMap

在上面讲解到HashMap时,部分用到了LinkedHashMap的方法,
添加数据时用到:afterNodeAccess(e); afterNodeInsertion(evict);
删除数据时用到:afterNodeRemoval(node);
替换数据时用到:afterNodeAccess(e);

这三个方法也是LinkedHashMap与HashMap的区别所在,我们下面来往下看 ->

extends,implements关系

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

可以看出LinkedHashMap继承了HashMap,也就是它可以使用或重写HashMap中的方法,并可以使用HashMap中属性.

属性

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

final boolean accessOrder;

可以看出,这同LinkedList似的,由原本HashMap数组+单向链表+红黑树维护,变成了双向链表维护.

内部类Entry

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

可以看出,它继承HashMap的Node节点,但是它多出了两个属性before after
其中before表示上一个节点,after表示下一个节点.

构造方法

LinkedHashMap()

public LinkedHashMap() {
    super();
    accessOrder = false;
}

LinkedHashMap(int initialCapacity)

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

LinkedHashMap(int initialCapacity, float loadFactor)

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)

除了这个可以指定内部的顺序,其他的都不可以指定,
accessOrder = true按照访问顺序来排序
accessOrder = false默认插入顺序来排序

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

LinkedHashMap(Map<? extends K, ? extends V> m)

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

与HashMap的不同点

newNode(int hash, K key, V value, Node<K,V> e)

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 进行将节点进行尾插入
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    /*
    1. 当前节点设为尾节点
    */
    tail = p;
    /*
    2. 当前是第一个插入的节点,设为头节点
    */
    if (last == null)
        head = p;
    /*
    3. 不是第一个插入的节点,进行尾插入.
       当前节点的上一个节点指向原尾节点,
       将原本尾节点的下一个节点指向当前节点
    */
    else {
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess(Node<K,V> e)

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    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;
    }
}

进来的情况:不是尾节点,并且是访问顺序来排序.
假设有四个节点a,b,c,d
情况1:get(a):排序之后b,c,d,a
情况2:get(b):排序之后a,c,d,b
情况3:get(c):同上,排序之后a,b,d,c
情况4:get(d):是尾节点,不会进行排序
总结：访问谁，把谁断开进行尾插。
在这里插入图片描述

afterNodeInsertion(boolean evict)

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

因为removeEldestEntry(first)会返回false,所以此方法暂无意义,
这里盲猜应该是继承LinkedHashMap的类会用到此方法.

afterNodeRemoval(Node<K,V> e)

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    /* 1. 节点前后断开 */
    p.before = p.after = null;
    
    /*
    2. 如果节点的before为null,说明头节点,
       如果是头节点,把后节点设为头节点(老大断开了,老二就变为老大了),
       不是头节点,把前节点的after指向后节点.
    */
    if (b == null)
        head = a;
    else
        b.after = a;
    
    /*
    3. 同上,是尾节点,把为节点指向前节点,
       不是尾节点,把后节点的before指向前节点.
    */
    if (a == null)
        tail = b;
    else
        a.before = b;
}

看了上面注释,总结一下:就是把访问的那个节点断开进行尾插,把断开处前后相连,如果是头节点或尾节点再对head和tail的指向做处理.

插入

这个在HashMap分析时已经讲到,这里主要讲不同的地方.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ... ...
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 不同点1. 创建Node之后会对节点进行尾插入
        tab[i] = newNode(hash, key, value, null);
    else {
        ... ...
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 找到节点,进行访问排序,抽出来,放入尾部.
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    // 这里LinkedHashMap调用此方法无意义,应该是对LinkedHashMap子类使用到.
    afterNodeInsertion(evict);
    return null;
}

删除

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 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        ... ...
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            ... ...
            ++modCount;
            --size;
            // 找到节点进行删除之后,对此节点前后断开,
            // 如果是头,尾节点再把head,tail指向别的节点或null.
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

替换

public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        // 替换值之后,进行访问排序,把节点放入尾部.
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

获取

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

循环方式不同

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

都是由head也就是第一个节点,开始往后循环,直到循环到尾节点.
也就是说默认循环的顺序与插入的顺序有关,
如果指定了访问顺序为true,就与访问顺序有关,上面我们说到了,访问节点会把要访问的节点放入尾部.
entrySet() keySet() values()也是一样.

下面entrySet的foreach方法

public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

HashTable

因为HashTable很少用,这里做个简单讲解,
它是1.0出来的,HashMap是1.2出来的,就是因为它效率低.
如果真想用线程安全的,使用ConcurrentHashMap效果更好.
为什么很少用,查看下面继承,实现关系中Dictionary的注释

extends,implements关系

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    
 * <strong>NOTE: This class is obsolete.  New implementations should
 * implement the Map interface, rather than extending this class.</strong>
 * 注:这个类已经过时了。新的实现应该实现Map接口，而不是扩展这个类。
 */
public abstract class Dictionary<K,V> {

可以看出连父类的源码都清除的写出了,类已经过时了.

构造方法

Hashtable()

1
2
3

public Hashtable() {
    this(11, 0.75f);
}

我们可以看出,默认容量是11,负载因子是0.75

Hashtable(int initialCapacity)

1
2
3

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

Hashtable(int initialCapacity, float loadFactor)

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

这里可以看出初始化了负载因子,表和阈值.
阈值=容量*负载因子,默认阈值就是11*0.75=8.25,也就是8.

Hashtable(Map<? extends K, ? extends V> t)

public Hashtable(Map<? extends K, ? extends V> t) {
    // 当前二倍数量和11取最大值.
    this(Math.max(2*t.size(), 11), 0.75f);
    // 进行添加
    putAll(t);
}

public synchronized int size() {
    // 返回数据的大小,注意这个是synchronized的.
    return count;
}

调用构造函数进行初始化,再进putAll方法,把所有数据重新插入.

public synchronized void putAll(Map<? extends K, ? extends V> t) {
    for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
        // 
        put(e.getKey(), e.getValue());
}

通过t.entrySet()先获取原Map的所有节点,再依次进行插入,可以看出此方法也是同步方法.
其中的put方法我们继续往下看 ->

put添加

public synchronized V put(K key, V value) {
    // 插入value不允许为空
    if (value == null) {
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 0x7FFFFFFF 也就是Integer.MAX_VALUE=31个1
    // 定位也是对数组长度取余.
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 定位不为空,判断是否为当前数据,
    // 如果不是当前数据,继续往下找next的指向,
    // 找到自己替换,返回旧值.
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 定位为空,可以插入,进入addEntry方法插入,并返回null
    addEntry(hash, key, value, index);
    return null;
}

可以看出,HashTable是不可以插入null的值的,
再把key的hashcode与数组长度进行取余,注意的是这里的长度可不是2的平方数,
取余之后,进行定位,
1.定位有数据,就一直往下找,找定位头节点的next执行,直到找到相同的key,替换并返回旧值.
2.如果定位无数据,直接进入addEntry方法,并返回null.(可以猜出addEntry方法就是扩容和插入的方法)

addEntry链表头插入

private void addEntry(int hash, K key, V value, int index) {
    // 结构变化,记录数+1
    modCount++;

    Entry<?,?> tab[] = table;
    // 大于等于阈值,进行扩容,并重新定位数据.
    if (count >= threshold) {
        rehash();

        tab = table;
        hash = key.hashCode();
        // 重新定位
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 注意这里新建的这个节点的next指针指向了原位置的数据.
    // 也就是在头部插入,
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

如果大于等于阈值,就进行扩容,进行rehash方法,在下面讲到.
rehash之后,对table数组重新赋值,重新定位.
获取新定位的数据,这里进行的是单向链表头插入,

rehash扩容

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 新容量 = 原容量*2 + 1 ;
    int newCapacity = (oldCapacity << 1) + 1;
    // 扩容后>最大值,设置新容量为MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8;
    // 使下次扩容原容量=MAX_ARRAY_SIZE时,直接进行返回.
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    /*
    把原数据重新定位,添加到新的数组中.
    */
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            // 0x7FFFFFFF == Integer.MAX_VALUE
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            // 这里进行的是单向链表的头插入,
            // 把next指向原位置的数据,把新定位的节点指向当前节点.
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

注意这里扩容是新容量 = 原容量*2 + 1 ;,新的容量最大只能为MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8;
把数据重新定位到新的数组中去.(在重新定位的时候,要注意是这里是头插入).

获取数据

获取数据是怎样的呢?

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 0x7FFFFFFF == Integer.MAX_VALUE
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

看得出来,和HashMap是方法差不多的,只不过方法都加了synchronized同步.

特点总结

所有的方法都是synchronized同步的
初始化容量是11,容量不是2的平方数
扩容为新容量 = 原容量*2 + 1 ;,容量最大为Integer.MAX_VALUE - 8
插入是不能插入key或value为null的值
插入是头插入,没有红黑树,只有数组+单向链表
循环也是从下标0开始循环,如果是链表,就循环链表,直到循环到最后

TreeMap

看之前做好心理准备,内容较多,并且需要你有HashMap和红黑树作为基础.
这个是基于红黑树实现NavigableMap接口的Map,所以查看此篇文章之前应该先对红黑树有个认识.
对于红黑树的简单理解可以查看红黑树
这个不细讲,主要理解有哪些不同点.

extends,implements关系

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

public abstract class AbstractMap<K,V> implements Map<K,V> {

public interface NavigableMap<K,V> extends SortedMap<K,V> {

public interface SortedMap<K,V> extends Map<K,V> {

由继承和实现关系就可以看出,它可以指定排序的方式.

属性

// 标记颜色
private static final boolean RED   = false;
private static final boolean BLACK = true;
// 红黑树的根节点
private transient Entry<K,V> root;
/*用于在此树映射中维护顺序的比较器,如果是null就按key的自然顺序排序*/
private final Comparator<? super K> comparator;
private transient int modCount = 0;
private transient int size = 0;

// 迭代对象`class EntrySet extends AbstractSet<Map.Entry<K,V>> `
private transient EntrySet entrySet;
// 迭代对象`static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {`
private transient KeySet<K> navigableKeySet;
// 不太懂,根据意思是使Map降序
private transient NavigableMap<K,V> descendingMap;

构造方法

TreeMap()

1
2
3

public TreeMap() {
    comparator = null;
}

comparator = null;,默认按照key的自然顺序进行排序

TreeMap(Comparator<? super K> comparator)

1
2
3

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

指定比较器,也就是相当于指定了排序方式.

TreeMap(Map<? extends K, ? extends V> m)

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

把普通的Map数据转换为红黑树结构的TreeMap

TreeMap(SortedMap<K, ? extends V> m)

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

把排序的SortMap数据转换为红黑树的TreeMap,并把比较器设置为SortedMap的比较器.

内部类Entry

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;

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    public K getKey() { return key; }

    public V getValue() { return value; }

    /* 设置新值,返回旧值 */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) { ... }

    public int hashCode() { ... }

    public String toString() { return key + "=" + value; }
}

可以看出,内部有左右父指针,保存了k,v的值.其颜色默认为黑色.
在设置值setValue时,设置新值,返回旧值.

增

在讲添加方法之前,要讲到比较器,因为由比较器来实现红黑树的,
比较器是比较插入数据的key与根节点的key值,哪个大,哪个小,

<0左插入
>0右插入
=0直接插入(返回旧值)

put(K key, V value)

public V put(K key, V value) {
    Entry<K,V> t = root;
    /*
    1. 如果没有根节点,也就是插入的是第一个数据.
    */
    if (t == null) {
        
        // 这样做是为了检测key是否为null
        // 如果key为null,抛NullPointerException异常
        // 这个比较的方法在下面讲到.
        compare(key, key); 

        // 创建新节点,设为根节点.默认颜色黑色.
        // 大小=1,结构变化数+1,返回null
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    /*
    2. 指定了比较器,使用指定比较器进行插入
    */
    if (cpr != null) {
        /*
        这个是正常的二叉树的插入方法.
        首先把要插入的key与根节点的key比较:
        (具体怎么比较由比较器进行定义)
            1. 小于0,左插入,找到要插入的位置的父节点,用parent记录.
            2. 大于0,右插入
            3. 等于0,直接设置value,返回旧的value,
               这在讲Entry内部类讲到.
        */
        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);
    }
    /*
    3. 未指定比较器,也是默认选项.
    */
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            // 如果key是String类型,就调用String类型的compareTo方法进行比较,
            // 插入的具体原理上面已经提到.
            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);
    }
    /*
    4. 如果找不到我们要插入的key,就在此创建一个新节点,
       把新节点的parent指向上面我们获取的parent节点.
       如果比较小于0,把左指针指向当前节点,否则使用右指针指向.
    */
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    /*
    5. 最重要的一步,也就是进行插入之后的调整(变色,左旋,右旋),
       使插入的二叉树变为我们真正所需要的红黑树.下面讲到
    */
    fixAfterInsertion(e);
    // 大小+1,结构变化数+1,返回null(因为是新节点)
    size++;
    modCount++;
    return null;
}

compare(Object k1, Object k2)

final int compare(Object k1, Object k2) {
    /*
    如果指定了比较器,就使用比较器的compare方法进行比较,
    默认使用key的比较器进行比较,如果key是String,
    就会调用下面String类的compareTo方法进行比较.
    */
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

compareTo(String anotherString)

// Math类中的方法,取最小int值
public static int min(int a, int b) {
    return (a <= b) ? a : b;
}

// String类中的方法
public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    // 获取字符串对象的char数组
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    // 循环次数lim为最小长度
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            // 注意这一步的两个char是可以相减的,
            // 关于char对应的int值参照下图.
            return c1 - c2;
        }
        k++;
    }
    // 循环内容相同时,
    // 例如"abcdefg".compareTo("abcd");//返回 7-4=3
    return len1 - len2;
}

都在注释上了,如果看不懂,就打断点,走两次这个方法就知道了.
char对应的int值,参考下图.

ASCII码表_char对应int值

在这里插入图片描述

fixAfterInsertion(Entry<K,V> x)

调整位置,查看红黑树

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

设置颜色,获取左右父节点

// 给节点设置颜色
private static <K,V> void setColor(Entry<K,V> p, boolean c) {if (p != null)p.color = c;}
// 获取左,右,父节点,为空返回null
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {return (p == null) ? null: p.left;}
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {return (p == null) ? null: p.right;}
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {return (p == null ? null: p.parent);}

左旋

查看红黑树

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

右旋

查看红黑树

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

其内容参考红黑树原理 ,
这个调整的方法我看了一下,和我理解的红黑树是完全一样的,和讲解中的也是一样的,
如果想搞懂其为什么,可以查看上面红黑树原理文章.对比着目录旋转和颜色变换规则来查看此方法.

查

get(Object key)

public V get(Object key) {
    /*
    根据key获取节点,
    节点为空返回null,不为空返回节点的值
    */
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

getEntry(Object key)

// 获取节点数据,和执行put方法插入时候差不多,
final Entry<K,V> getEntry(Object key) {
    /*
    1. 指定了比较器,使用比较器进行插入
    */
    if (comparator != null)
        return getEntryUsingComparator(key);
    /*
    2. key为空抛异常
    */
    if (key == null)
        throw new NullPointerException();
    /*
    3. 使用默认key类型的compareTo方法进行比较.
       例如key为String类型,就调用String类中的compareTo方法
    */
    @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;
}

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

getFirstEntry()

获取key值最小的节点

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

getLastEntry()

获取key值最大的节点

final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

predecessor(Entry<K,V> t)

如果使比较器按照key的值,从小到大排序.
那么这个方法就是获取指定节点的前一个节点,
如果是头节点(key最小),则返回null.

如果看了之后,可以对比着这张图来看.
在这里插入图片描述

static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    /*
    1. 节点为null,则返回null
    */
    if (t == null)
        return null;
    /*
    2. 左下不为空,找到左下最右下不为null的节点.
    */
    else if (t.left != null) {
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    /*
    3. 左下为空,只能往上找.(下面听不懂的,可以多画图尝试.)
       假设此节点有一个右上节点,这两个节点连线,
       此节点上方第一个不在这条线上的节点,进行返回.
    */
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

successor(Entry<K,V> t)

道理同上,获取后一个节点,如果是尾节点(key最大),返回null.

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

getLowerEntry(K key)

同predecessor方法,不同的是,它是根据key来查找到比key的值前面的那个节点.
如果你不能正确理解,可以尝试对比下面这张图:
if(key=19) -> return 13那个节点.
if(key=35) -> return 30那个节点.
if(key=12,根节点) -> return 7那个节点.
if(key=1) -> return null.
在这里插入图片描述

final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

getHigherEntry(K key)

道理同上.它是根据key来查找到比key的值后面的那个节点.

final Entry<K,V> getHigherEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

getFloorEntry(K key)

获取与指定key对应的节点,
如果没有这样的节点存在,返回小于指定key的最大key的节点,
若最小key还大于指定的key,就返回null(也就是找不到比指定key更小的节点了)

对比下图,
if(key=13) -> return 13那个节点.
if(key=15) -> return 13那个节点.
if(key=8) -> return 7那个节点.
if(key=50) -> return 35那个节点.
if(key=0) -> return null.
在这里插入图片描述

final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;

    }
    return null;
}

getCeilingEntry(K key)

获取与指定key对应的节点,
如果没有这样的节点存在,返回大于指定key的最小key的节点,
若最大key还小于指定的key,就返回null(也就是找不到比指定key更大的节点了)

对比下图,
if(key=13) -> return 13那个节点.
if(key=15) -> return 19那个节点.
if(key=8) -> return 12那个节点.
if(key=50) -> return null.
if(key=0) -> return 1那个节点.
在这里插入图片描述

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

删

clear()

清空数据

public void clear() {
    modCount++;
    size = 0;
    root = null;
}

remove(Object key)

public V remove(Object key) {
    /* 1. 根据key获取节点,在上面`查`已经讲到 */
    Entry<K,V> p = getEntry(key);
    /* 2. 如果节点为空,返回空 */
    if (p == null)
        return null;

    /* 3. 不为空,就删除并返回value */
    V oldValue = p.value;
    /*此方法是删除节点,并调整树并重新达到平衡;*/
    deleteEntry(p);
    return oldValue;
}

deleteEntry(Entry<K,V> p)

// 下面是主要讲思路,不讲解`fixAfterDeletion`方法调整位置.
// 如果你理解了之前的`fixAfterInsertion`方法,这个也同理可得.
private void deleteEntry(Entry<K,V> p) {
    /*
    0. 先结构记录数+1,节点数量-1
    */
    modCount++;
    size--;

    /*
    1. 如果有两个不为空的子节点,获取后继节点,
       把后继节点的值赋值给要删除的节点,
       再把p指向后继节点,下面再做处理.
    */
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    /*
    2. (1)如果p是后继节点,也就是走了上面一步,这里的replacement=p.right;
       (2)如果p不是后继节点,p还是传入的节点,p要是只有一个子节点,
          replacement就是它的那个子节点,如果没有字节点,就指向null.
    */
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    /*
    3. 把p节点的父节点与replacement进行连接,并把p节点断开,调整位置.
       这里p若为后继节点,我们可知后继节点的key,value已经赋给了要删除的节点.
    */
    if (replacement != null) {
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        p.left = p.right = p.parent = null;

        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    /*
    4. 若删除的是根节点,根节点没有孩子,直接把根节点设为null即可.
    */
    } else if (p.parent == null) {
        root = null;
    /*
    5. 不管p是否为后继节点,若p没有孩子,就先调整位置,再进行连接.
    */
    } else {
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

pollFirstEntry()

找到key值最小的节点,并删除.
返回删除的节点数据,节点中只包含key,value.没有其他属性.

public Map.Entry<K,V> pollFirstEntry() {
    Entry<K,V> p = getFirstEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

pollLastEntry()

同上,不同的是删除最后一个.

public Map.Entry<K,V> pollLastEntry() {
    Entry<K,V> p = getLastEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

改

replace(K key, V value)

根据key找到节点,替换值,返回旧值.
找不到节点返回null.

public V replace(K key, V value) {
    Entry<K,V> p = getEntry(key);
    if (p!=null) {
        V oldValue = p.value;
        p.value = value;
        return oldValue;
    }
    return null;
}

replace(K key, V oldValue, V newValue)

同上,不同的是匹配key的同时,value也要匹配.
修改成功返回true,否则false.

public boolean replace(K key, V oldValue, V newValue) {
    Entry<K,V> p = getEntry(key);
    if (p!=null && Objects.equals(oldValue, p.value)) {
        p.value = newValue;
        return true;
    }
    return false;
}

循环

entrySet()

看这个之前,你最好能够理解HashMap的entrySet与keySet区别?源码分析
这里主要讲一下不同点.

// TreeMap的全局变量,其中EntrySet是TreeMap内部类
private transient EntrySet entrySet;

public Set<Map.Entry<K,V>> entrySet() {
    EntrySet es = entrySet;
    return (es != null) ? es : (entrySet = new EntrySet());
}

内部类EntrySet

class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        /* 看得出来,同HashMap,创建一个迭代器对象,
        这里多了个传入参数,key值最小的节点.*/
        return new EntryIterator(getFirstEntry());
    }

    public boolean contains(Object o) { ... }

    public boolean remove(Object o) { ... }

    public int size() { return TreeMap.this.size(); }

    public void clear() { TreeMap.this.clear(); }

    public Spliterator<Map.Entry<K,V>> spliterator() { ... }
}

内部类EntryIterator

final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
    /* 调用父类`PrivateEntryIterator`的构造方法 */
    EntryIterator(Entry<K,V> first) { super(first); }
    /* 获取下一个节点. */
    public Map.Entry<K,V> next() { return nextEntry(); }
}

内部类PrivateEntryIterator

abstract class PrivateEntryIterator<T> implements Iterator<T> {
    Entry<K,V> next;
    Entry<K,V> lastReturned;
    int expectedModCount;

    /* 初始化,传入第一个节点,下次循环的指针指向第一个节点. */
    PrivateEntryIterator(Entry<K,V> first) {
        expectedModCount = modCount;
        lastReturned = null;
        next = first;
    }

    public final boolean hasNext() { return next != null; }

    final Entry<K,V> nextEntry() {
        Entry<K,V> e = next;
        /* 无元素异常 */
        if (e == null)
            throw new NoSuchElementException();
        /* 并发修改异常 */
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        /* 获取后继节点,在目录`查`中讲到. */
        next = successor(e);
        lastReturned = e;
        return e;
    }

    /* 字面意思,是前一个节点. */
    final Entry<K,V> prevEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        /* 获取前一个节点 */
        next = predecessor(e);
        lastReturned = e;
        return e;
    }

    public void remove() { ... }
}

可以看出,它的循环也是同key值的顺序排列的,默认是从小到大的顺序排列,先访问到最小key的节点.
所以它不同于HashMap,它遍历是有序的,HashMap是无需的.

keySet()

这个稍微有点不同,它可以根据比较器排序后的Map遍历.

1	public Set<K> keySet() { return navigableKeySet(); }

navigableKeySet()

private transient KeySet<K> navigableKeySet;

public NavigableSet<K> navigableKeySet() {
    KeySet<K> nks = navigableKeySet;
    return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}

内部类KeySet

static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
    private final NavigableMap<E, ?> m;
    KeySet(NavigableMap<E,?> map) { m = map; }

    /* 调用`keyIterator()`方法,那么这个方法肯定是用来返回迭代器的. */
    public Iterator<E> iterator() {
        /* 默认遍历 */
        if (m instanceof TreeMap)
            return ((TreeMap<E,?>)m).keyIterator();
        /* 如果指定了比较器,调用NavigableSubMap排序过的Map进行遍历 */
        else
            return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
    }

    public Iterator<E> descendingIterator() {
        if (m instanceof TreeMap)
            return ((TreeMap<E,?>)m).descendingKeyIterator();
        else
            return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
    }

    public int size() { return m.size(); }
    public boolean isEmpty() { return m.isEmpty(); }
    public boolean contains(Object o) { return m.containsKey(o); }
    public void clear() { m.clear(); }
    ... ...
}

keyIterator()

1
2
3

Iterator<K> keyIterator() {
    return new KeyIterator(getFirstEntry());
}

内部类KeyIterator

final class KeyIterator extends PrivateEntryIterator<K> {
    KeyIterator(Entry<K,V> first) { super(first); }
    /* 返回后继节点的key值 */
    public K next() { return nextEntry().key; }
}

values()

1	public V next() { return nextEntry().value; }

同上,只不过next()是获取下一个节点的value属性.

HashSet

经过上面的分析,我们终于可以分析Set类型的集合了,
其实我们在分析HashMap的时候,就知道的差不多了,我们再次重新认识一下它.

extends,implements关系

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

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {

public abstract class AbstractCollection<E> implements Collection<E> {

public interface Set<E> extends Collection<E> {

public interface Collection<E> extends Iterable<E> {

public interface Iterable<T> {

我们可以看到 HashSet是实现Set接口的,这个毋庸置疑.
而Set接口是继承Collection(集合)接口的.
Collection继承Iterable接口,才可以使迭代成为可能.

基本属性

1
2
3

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

可以看出,它实质上就是保存在HashMap中的key值,
还有一个不可改变的Object对象.

add(E e)

1
2
3

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

可以看出,HashSet插入往HashMap中插入数据的,只不过插入的value是不可变的成员变量PRESENT.
添加的key不存在返回true,存在返回false.

iterator()

1
2
3

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

size()

1
2
3

public int size() {
    return map.size();
}

contains(Object o)

1
2
3

public boolean contains(Object o) {
    return map.containsKey(o);
}

remove(Object o)

1
2
3

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

LinkedHashSet

通过了HashSet的讲解,看得出来了解Set的本质,就是需要了解Map.
LinkedHashSet也不例外,下面我们来看一下.

extends,implements关系

1
2
3

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

看得出来,它正如LinkedHashMap继承HashMap一样,

不同点

/* 父类HashSet的方法 */
/* 这里第三个参数是用来区分创建LinkedHashMap的,并无使用 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

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

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

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

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

@Override
public Spliterator<E> spliterator() {
    return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}

看得出来,其本质就是LinkedHashMap,这里就不做过多阐述.
默认容量和负载因子与HashMap一样,分别是16 0.75f

TreeSet

通过我们对HashSet与LinkedHashSet的了解,我们知道了其本质就是HashMap与LinkedHashMap的key.

extends,implements关系

1
2
3

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

属性

1
2
3

private transient NavigableMap<E,Object> m;

private static final Object PRESENT = new Object();

其原理同HashSet,下面写出add添加代码,不做过多阐述.

add(E e)

1
2
3

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