IT@程序员猿媛Java随笔-生活工作点滴

【Java 笔记】Java 集合相关整理

2019-08-12  本文已影响1人  58bc06151329

文前说明

作为码农中的一员，需要不断的学习，我工作之余将一些分析总结和学习笔记写成博客与大家一起交流，也希望采用这种方式记录自己的学习之旅。

本文仅供学习交流使用，侵权必删。
不用于商业目的，转载请注明出处。

1. 概述

2. 原理

2.1 Collection

方法 说明
int size() 返回此集合中的元素数量。
boolean isEmpty() 判断集合元素是否为空。
boolean contains(Object o) 判断此集合是否包含指定的元素，包含则返回 true，反之。
Iterator<E> iterator() 返回此集合中元素的迭代器，不保证元素返回的顺序（除非此集合是提供保证的某个类的实例）。
Object[] toArray() 将此集合中的元素转换成数组并返回该数组，该方法作为基于数组和集合之间的桥梁的 API。
<T> T[] toArray(T[] a) 返回指定类型数组。
boolean add(E e) 此集合添加指定元素。
boolean remove(Object o) 删除指定元素。
boolean containsAll(Collection<?> c) 判断是否包含特定集合，如果存在则返回 true，反之。
boolean addAll(Collection<? extends E> c) 添加指定集合。
boolean removeAll(Collection<?> c) 删除指定集合。
default boolean removeIf(Predicate<? super E> filter) 移除此集合中满足给定条件的所有元素。
boolean retainAll(Collection<?> c) 仅保留指定类型的集合。
void clear() 清空集合元素。
boolean equals(Object o) 将指定的对象与此集合进行相等比较。
int hashCode() 返回集合的哈希值，用于比较相等与否。

2.2 List

方法 说明
E get(int index) 返回指定位置的元素。
E set(int index, E element) 在指定位置将传入的元素替换当前 list 在此位置的元素。
void add(int index, E element) 在指定位置来将传入的元素添加在当前 list 里面。
E remove(int index) 将指定位置的元素移除。
方法 说明
int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引，或如果该列表不包含元素，则返回 -1。
int lastIndexOf(Object o) 返回此列表中指定元素的最后一个出现的索引，或如果该列表不包含元素，则返回 -1。
方法 说明
List<E> subList(int fromIndex, int toIndex) 返回一个列表，这个列表根据传入的开始地址和结束地址，然后在 list 里面截取。

2.3 Set

2.4 Map

2.5 ArrayList

//无参构造方法，ArrayList 的初始化长度为 10，这是一个静态常量
private static final int DEFAULT_CAPACITY = 10;
​
//空的对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
​
//保存 ArrayList 数据的对象数组缓冲区，elementData的初始容量为 10，大小会根据 ArrayList 容量的增长而动态的增长。
private transient Object[] elementData;
//集合的长度
private int size;

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 ArrayList() {
    this.elementData = EMPTY_ELEMENTDATA;
}

2.5.1 插入（add）

/** 在元素序列尾部插入 */
public boolean add(E e) {
    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将新元素插入序列尾部
    elementData[size++] = e;
    return true;
}

/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // 1. 检测是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index 及其之后的所有元素都向后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. 将新元素插入至 index 处
    elementData[index] = element;
    size++;
}

//判断是否出现下标是否越界
private void rangeCheckForAdd(int index) {
  //如果下标超过了集合的尺寸 或者 小于 0 就是越界  
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
尾部添加元素 指定位置插入元素 
//初始长度是 10，size 默认值 0，假定添加的是第一个元素，那么 minCapacity=1 这是最小容量 如果小于这个容量就会报错
//如果底层数组就是默认数组，那么选一个大的值，就是 10
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //调用另一个方法ensureExplicitCapacity
        ensureExplicitCapacity(minCapacity);
    }
​
    private void ensureExplicitCapacity(int minCapacity) {
        //记录修改的次数
        modCount++;
​
        // overflow-conscious code
        //如果传过来的值大于初始长度 执行 grow 方法（参数为传递的值）扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 //扩容
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新的容量是在原有的容量基础上 +50% 右移一位就是二分之一
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新容量小于最小容量，按照最小容量进行扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //调用工具类 Arrays 的 copyOf 方法扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
​
//Arrays
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
  T[] copy = ((Object)newType == (Object)Object[].class)
    ? (T[]) new Object[newLength]
    : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  System.arraycopy(original, 0, copy, 0,
                   Math.min(original.length, newLength));
  return copy;
}

2.5.2 删除（remove）

public E remove(int index) {
  //下标越界检查
  rangeCheck(index);
  //修改次数统计
  modCount++;
  //获取这个下标上的值
  E oldValue = elementData(index);
  //计算出需要移动的元素个数 （因为需要将后续元素左移一位，此处计算出来的是后续元素的位数）
  int numMoved = size - index - 1;
  //如果这个值大于 0，说明后续有元素需要左移，0 说明被移除的对象就是最后一位元素
  if (numMoved > 0)
    //所有元素左移一位  覆盖掉 index 位置上的元素
    System.arraycopy(elementData, index+1, elementData, index,numMoved);
  // 将最后一个元素赋值为 null  这样可以被 GC 回收
  elementData[--size] = null; // clear to let GC do its work
  //返回 index 位置上的元素
  return oldValue;
}
​
//移除特定元素
public boolean remove(Object o) {
  //如果元素是 null 遍历数组移除第一个 null
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        //遍历找到第一个 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) {
  modCount++;
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  elementData[--size] = null; // clear to let GC do its work
}
移除元素 
public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
}
缩容机制

2.5.3 遍历

for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

2.5.4 小结

JDK 1.7 相比于 JDK 1.6

//1.6，两个构造的区别很明显
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<String>(0); // la.elementData = new Object[0], la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<String>(); // lb.elementData = new Object[10], lb.elementData.length = 10
        lb.add("111"); // lb.elementDate.length = 10，这里没有进行扩容，后续再按照通用扩容策略执行扩容操作
    }
}
 
//1.7，两个构造在第一次进行添加时才有区别
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<>(0); // la.elementData = new Object[0], la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<>(); // lb.elementData = EMPTY_ELEMENTDATA, lb.elementData.length = 0
        lb.add("111"); // lb.elementDate.length = 10，这里一次性扩容了 10 个，后续再按照通用扩容策略执行扩容操作
    }
}

//1.8 同 1.7
public class TestArrayList {
    public static void main(String[] args) {
        List<String> la = new ArrayList<>(0); // la.elementData = EMPTY_ELEMENTDATA, la.elementData.length = 0
        la.add("111"); // la.elementDate.length = 1，这里一次性扩容了 1 个，后续再按照通用扩容策略执行扩容操作
 
        List<String> lb = new ArrayList<>(); // lb.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, lb.elementData.length = 0
        lb.add("111"); // lb.elementDate.length = 10，这里一次性扩容了 10 个，后续再按照通用扩容策略执行扩容操作
    }
}

JDK 1.8 相比于 JDK 1.7

// 1.7 跟 1.6 一样
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
}
 
// 1.8
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);
    }
}

// jdk 1.6
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
 
// jdk 1.7
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}
 
// jdk 1.8
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

List<String> list = Arrays.asList("abc");
// class java.util.Arrays$ArrayList
System.out.println(list.getClass());
// class [Ljava.lang.String;
Object[] objArray = list.toArray();
System.out.println(objArray.getClass());
objArray[0] = new Object(); // cause ArrayStoreException

ArrayList 和 Vector 的区别

2.6 Vector

// 保存Vector中数据的数组
protected Object[] elementData;

// 实际数据的数量
protected int elementCount;

// 容量增长系数
protected int capacityIncrement;

//指定数组的初始化大小，和增长系数。容量不能小于 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;
}

//指定容量，增长系数未 0
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//采用默认 容量 10 增长系数为 0
public Vector() {
    this(10);
}

//使用另一个集合构造改集合
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray 可能（错误地）不返回 Object []
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

2.6.1 添加（add）

//指定位置插入元素
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                + " > " + elementCount);
    }
    //是否需要扩容
    ensureCapacityHelper(elementCount + 1);
    //通过 arraycopy方 法在插入位置向后移动以为，方便元素插入
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

//添加元素
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

//添加元素
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

//指定位置添加元素
public void add(int index, E element) {
    insertElementAt(element, index);
}

//Vectory 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //新的数组长度 = 旧数组长度 + 增长系数大于 0 加增长系数，否则 + 旧数组长度
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
            capacityIncrement : oldCapacity);
    //如果计算后还不够就 = 最小扩容数
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果大于最大扩容数
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //最大看扩容量为 Integer.MAX_VALUE
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.6.2 删除（remove）

//移除指定位置的元素
public synchronized void removeElementAt(int index) {
    modCount++;
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j 是删除元素在数组中的位置
    int j = elementCount - index - 1;
    if (j > 0) {
        //移动数组位置：新数组位置 = 原数组移除元素的后一位都通过 copy 向前移动一位
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    elementCount--;
    //copy 多出一位，设置为 null 让 GC 回收
    elementData[elementCount] = null; /* to let GC do its work */
}

//移除元素
public synchronized boolean removeElement(Object obj) {
    modCount++;
    //通过 indexOf 获取在数组中的位置
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

//删除当前数组中的所有元素
public synchronized void removeAllElements() {
    modCount++;
    //让 GC 回收
    for (int i = 0; i < elementCount; i++)
        elementData[i] = null;

    elementCount = 0;
}

//移除匹配元素
public boolean remove(Object o) {
    return removeElement(o);
}

//指定位置移除元素 并返回被移除的元素
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 void clear() {
    removeAllElements();
}

//移除 Vectory 中 fromIndex 到 toIndex 位置上的所有元素
protected synchronized void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = elementCount - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
            numMoved);

    // Let GC do its work
    int newElementCount = elementCount - (toIndex-fromIndex);
    while (elementCount != newElementCount)
        elementData[--elementCount] = null;
}

//移除当前所在光标的元素
public void remove() {
    if (lastRet == -1)
        throw new IllegalStateException();
    synchronized (Vector.this) {
        checkForComodification();
        Vector.this.remove(lastRet);
        expectedModCount = modCount;
    }
    cursor = lastRet;
    lastRet = -1;
}

@Override
@SuppressWarnings("unchecked")
public synchronized boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    final int size = elementCount;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // 移位幸存元素留在被移除元素留下的空间
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let GC do its work
        }
        elementCount = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

2.6.3 总结

public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

fail-fast

2.7 LinkedList

JDK 1.6 实现方式 JDK 1.7 之后实现方式 
transient int size = 0;//当前列表的元素个数
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;// 第一个元素
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;// 最后一个元素

public LinkedList() {}//无参构造函数
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//将c中的元素都添加到此列表中
}

Node 结点

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 Node<E> first;
transient Node<E> last;

2.7.1 添加（add）

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

void linkLast(E e) {
    final Node<E> l = last;//链表最后一个结点
    final Node<E> newNode = new Node<>(l, e, null);//建立结点对象，前一个（perv属性）是last，后一个（next属性）是null，中间item数据是输入的参数e
    last = newNode;
    if (l == null)
        first = newNode; //如果最后一个结点 为null表示链表为空，则添加数据时将新加的数据作为第一个结点
    else
        l.next = newNode; //如果链表不为空则将最后一个链表的next属性指向新添加的结点
    size++; //链表长度自增1
    modCount++;
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);//判断index是否越界，越界则抛出异常
    Object[] a = c.toArray();
    int numNew = a.length;//要插入的集合的长度
    if (numNew == 0)
        return false;
    Node<E> pred, succ;//声明pred和succ两个Node对象，用于标识要插入元素的前一个结点和最后一个结点
    if (index == size) { //如果size等于原数组长度则表示在结尾添加
        succ = null;
        pred = last;
    } else {
        succ = node(index);//index位置上的Node对象
        pred = succ.prev;
    }
    for (Object o : a) { //遍历要插入的集合
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode; //如果要插入的位置的前一个结点为null表示是第一个结点，则直接将newNode赋给第一个结点
        else
            pred.next = newNode; //将要插入的集合元素结点对象赋给此位置原结点对象的前一个对象的后一个，即更改前一个结点对象的next指针指到新插入的结点上
        pred = newNode;//更改指向后将新结点对象赋给pred作为下次循环中新插入结点的前一个对象结点，依次循环
    }
    //此时pred代表集合元素的插入完后的最后一个结点对象
    if (succ == null) { //结尾添加的话在添加完集合元素后将最后一个集合的结点对象pred作为last
        last = pred;
    } else {
        pred.next = succ;//将集合元素的最后一个结点对象的next指针指向原index位置上的Node对象
        succ.prev = pred;//将原index位置上的pred指针对象指向集合的最后一个对象
    }
    size += numNew;
    modCount++;
    return true;
}

Node<E> node(int index) {
    if (index < (size >> 1)) { //判断index是否小于size的一半，如果小于则从头遍历结点，否则从结尾遍历结点
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next; //从first第一个结点开始，依次将后一个结点赋给x
        return x; //返回index位置上的Node对象，下同理
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.7.2 删除（remove）

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

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 {
        prev.next = next;//将传入的结点的下一个结点对象赋给其之前前一个结点的下一个结点对象，即将传入的结点对象跳过
        x.prev = null;//将传入对象的前一个结点对象置空使其前一个指针不指向任何元素
    }
    if (next == null) {
        last = prev;//如果next为null表示是最后一个元素，直接将pred结点赋给last
    } else {
        next.prev = prev;
        x.next = null;//将传入结点的后一个结点置空，使其后一个结点指针不指向任何元素
    }
    x.item = null;//将传入的结点对象上的对象置空，也就是整个Node对象中的属性都为空了，后面会被GC回收
    size--;
    modCount++;
    return element;
}

2.7.3 查询

public E get(int index) {
    checkElementIndex(index);//检查索引越界情况
    return node(index).item;//返回该index位置上的结点对象的item属性，即该位置上的实际值
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 视其与中值得差距，决定从前遍历还是从后遍历。
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 循环index次 迭代到所需要的元素
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        // 循环size-1-index次
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.7.4 小结

LinkedList 和 ArrayList 的区别

2.8 HashSet

private transient HashMap<E,Object> map;

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

/**
   * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
   * default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
      map = new HashMap<>();
}

2.8.1 构造函数

/**
 * 使用 HashMap 的默认容量大小 16 和默认加载因子 0.75 初始化 map，构造一个 HashSet
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * 构造一个指定 Collection 参数的 HashSet，这里不仅仅是 Set，只要实现 Collection 接口的容器都可以
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math. max((int) (c.size()/.75f) + 1, 16));
   // 使用Collection实现的Iterator迭代器，将集合c的元素一个个加入HashSet中
   addAll(c);
}

/**
 * 使用指定的初始容量大小和加载因子初始化map，构造一个HashSet
 */
public HashSet( int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * 使用指定的初始容量大小和默认的加载因子0.75初始化map，构造一个HashSet
 */
public HashSet( int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

/**
 * 不对外公开的一个构造方法（默认default修饰），底层构造的是LinkedHashMap，dummy只是一个标示参数，无具体意义
 */
HashSet( int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

2.8.2 添加（add）

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

addAll

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

2.8.3 删除（remove）

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

removeAll

public boolean removeAll(Collection<?> c) {
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

2.9 LinkedHashMap（JDK 1.7）

LinkedHashMap 中的 Entry 对象

Entry 的继承体系

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    ...
}

2.9.1 构造方法

//使用父类中的构造，初始化容量和加载因子，该初始化容量是指数组大小。
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//一个参数的构造
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//无参构造
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//接受map类型的值转换为LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
//参数accessOrder 是存储顺序，LinkedHashMap。
//true：指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 
//false：指定迭代的顺序是按照插入顺序迭代，通过插入元素的顺序来迭代所有元素
//其他三个构造方法默认使用插入顺序。
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

@Override
void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}
header 实例

2.9.2 链表的创建

void addEntry(int hash, K key, V value, int bucketIndex) {
    //调用create方法，将新元素以双向链表的的形式加入到映射中
    createEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed, else grow capacity if appropriate
    // 删除最近最少使用元素的策略定义  
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
    table[bucketIndex] = e;
    //将该结点插入到链表尾部
    e.addBefore(header);
    size++;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

增加第一个元素步骤

增加第一个元素

增加第二个元素步骤

增加第二个元素

2.9.3 元素的读取

/**
 * 通过key获取value，与HashMap的区别是：当LinkedHashMap按访问顺序排序的时候，会将访问的当前结点移到链表尾部(头结点的前一个结点)
 */
public V get(Object key) {
    // 调用父类HashMap的getEntry()方法，取得要查找的元素。  
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    // 记录访问顺序。
    e.recordAccess(this);
    return e.value;
}

/**
 * 在HashMap的put和get方法中，会调用该方法，在HashMap中该方法为空
 * 在LinkedHashMap中，当按访问顺序排序时，该方法会将当前结点插入到链表尾部(头结点的前一个结点)，否则不做任何事
 */
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //当LinkedHashMap按访问排序时
    if (lm.accessOrder) {
        lm.modCount++;
        //移除当前结点
        remove();
        //将当前结点插入到头结点前面
        addBefore(lm.header);
    }
}

/**
 * 移除结点，并修改前后引用
 */
private void remove() {
    before.after = after;
    after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

2.9.4 LRU

public class LRUCache extends LinkedHashMap
{
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

public LinkedHashMap(int initialCapacity,
         float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
accessOrder 值 说明
false 所有的 Entry 按照插入的顺序排列。
true 所有的 Entry 按照访问的顺序排列。
基于 accessOrder = true 的情况的执行过程

2.9.5 LinkedHashMap（JDK 1.8）

//LinkedHashMap
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
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}
LinkedHashMap 中的 Entry 对象

2.9.5.1 链表的创建

// HashMap 中实现
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// HashMap 中实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) {...}
    // 通过结点 hash 定位结点所在的桶位置，并检测桶中是否包含结点引用
    if ((p = tab[i = (n - 1) & hash]) == null) {...}
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) {...}
        else {
            // 遍历链表，并统计链表长度
            for (int binCount = 0; ; ++binCount) {
                // 未在单链表中找到要插入的结点，将新结点接在单链表的后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) {...}
                    break;
                }
                // 插入的结点已经存在于单链表中
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) {...}
            afterNodeAccess(e);    // 回调方法，后续说明
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) {...}
    afterNodeInsertion(evict);    // 回调方法，后续说明
    return null;
}

// HashMap 中实现
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap 中覆写
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);
    // 将 Entry 接在双向链表的尾部
    linkNodeLast(p);
    return p;
}

// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // last 为 null，表明链表还未建立
    if (last == null)
        head = p;
    else {
        // 将新结点 p 接在链表尾部
        p.before = last;
        last.after = p;
    }
}
HashMap 原始数据结构 LinkedHashMap 在上面结构的基础上，增加了一条双向链表

2.9.5.2 链表结点的删除

// HashMap 中实现
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

// HashMap 中实现
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;
        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) {...}
            else {
                // 遍历单链表，寻找要删除的结点，并赋值给 node 变量
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) {...}
            // 将要删除的结点从单链表中移除
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);    // 调用删除回调方法进行后续操作
            return node;
        }
    }
    return null;
}

// LinkedHashMap 中覆写
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将 p 结点的前驱后后继引用置空
    p.before = p.after = null;
    // b 为 null，表明 p 是头结点
    if (b == null)
        head = a;
    else
        b.after = a;
    // a 为 null，表明 p 是尾结点
    if (a == null)
        tail = b;
    else
        a.before = b;
}
待删除结点 3 从单链表中移除该结点 从双向链表中移除该结点

2.9.5.3 元素的读取

// LinkedHashMap 中覆写
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问结点移动到链表最后
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

// LinkedHashMap 中覆写
void afterNodeAccess(Node<K,V> e) { // move node to last
    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;
        // 如果 b 为 null，表明 p 为头结点
        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 接在链表的最后
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
假设访问键值为 3 的结点 键值为 3 的结点将会被移动到双向链表的最后位置，其前驱和后继也会跟着更新

2.9.5.4 LRU

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

2.10 LinkedHashSet

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

// 只传入容量, 装载因子默认为 0.75
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

// 使用默认容量 16, 默认装载因子 0.75
public LinkedHashSet() {
    super(16, .75f, true);
}

// 将集合 c 中的所有元素添加到 LinkedHashSet 中
// HashSet中使用的是Math.max((int) (c.size()/.75f) + 1, 16)
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);
}

2.11 TreeSet

//相同包下可以访问的构造方法，将指定的m赋值为m 
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
//无参构造方法，创建一个空的TreeMap对象，并调用上面的构造方法
public TreeSet() {
    this(new TreeMap<E,Object>());
}
//指定比较器，并用指定的比较器创建TreeMap对象
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
//将指定的集合C转化为TreeSet
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
//将SortedMap中的元素转化为TreeMap对象
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

//返回 m 包含的键值对的数量
public int size() {
    return m.size();
}

//是否为空
public boolean isEmpty() {
    return m.isEmpty();
}

//是否包含指定的key
public boolean contains(Object o) {
    return m.containsKey(o);
}

//添加元素，调用m.put方法实现
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

//删除方法，调用m.remove()方法实现
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

//清除集合
public void clear() {
    m.clear();
}

//将一个集合中的所有元素添加到TreeSet中
public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
        Comparator<? super E> mc = map.comparator();
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);
            return true;
        }
    }
    return super.addAll(c);
}

//返回子集合，通过 m.subMap()方法实现
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

//返回set的头部
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

//返回尾部
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

//返回子Set
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

//返回set的头部
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

//返回set的尾部
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}
//返回m使用的比较器
public Comparator<? super E> comparator() {
    return m.comparator();
}

//返回第一个元素
public E first() {
    return m.firstKey();
}
//返回最后一个元素
public E last() {
    return m.lastKey();
}

//返回set中小于e的最大的元素
public E lower(E e) {
    return m.lowerKey(e);
}

//返回set中小于/等于e的最大元素
public E floor(E e) {
    return m.floorKey(e);
}

//返回set中大于/等于e的最大元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}

//返回set中大于e的最小元素
public E higher(E e) {
    return m.higherKey(e);
}

//获取TreeSet中第一个元素，并从Set中删除该元素
public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

//获取TreeSet中最后一个元素，并从Set中删除该元素
public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

//克隆方法
public Object clone() {
    TreeSet<E> clone = null;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }

    clone.m = new TreeMap<>(m);
    return clone;
}

//将对象写入到输出流中。
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden stuff
    s.defaultWriteObject();

    // Write out Comparator
    s.writeObject(m.comparator());

    // Write out size
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    for (E e : m.keySet())
        s.writeObject(e);
}

//从输入流中读取对象的信息
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    s.defaultReadObject();

    // Read in Comparator
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    TreeMap<E,Object> tm;
    if (c==null)
        tm = new TreeMap<>();
    else
        tm = new TreeMap<>(c);
    m = tm;

    // Read in size
    int size = s.readInt();

    tm.readTreeSet(size, s, PRESENT);
}

参考资料

https://www.imooc.com/article/23044
https://segmentfault.com/a/1190000012964859
https://blog.csdn.net/shelleylittlehero/article/details/82954474

上一篇 下一篇

猜你喜欢

热点阅读