关于程序员:讲讲Java的集合

40次阅读

共计 20571 个字符，预计需要花费 52 分钟才能阅读完成。

前言

大部分编程语言都提供了数组来保留对象，数组是十分重要的数据结构之一。然而数组在初始化时就曾经定义了数组长度，不可变，应用起来颇为麻烦。因而，Java 在 JDK 1.2 版本中增加了汇合框架，用来保留和操纵对象。

Java 中的容器采纳的是 “ 持有对象 ”（holding objects）的思维，次要由继承 Collection 与 Map 两个接口来实现的。上面咱们来看一下这两种容器：

  1. 汇合（Collection）：它次要是寄存着对象的汇合。次要是寄存繁多元素。
  2. 映射（Map）：它次要是寄存着对于 “ 键值对 ” 的关系映射表，次要是寄存 key-value 键值对的。

Collection

Collection 接口为主接口，上面还细分为 List、Set 与 Queue 这三个接口，这三个接口都是继承于 Collection，但要实现的性能却不一样。List 次要是存储元素时，要放弃插入的程序；Set 次要是不蕴含反复元素；Queue 依照排序规定来确定对象产生的程序（通常与它们被插入的程序雷同）。

但因为它们继承于 Collection 接口，因而，它们都具备一些雷同的操作：

public interface Collection<E> extends Iterable<E> {int size();    // 汇合的大小
    boolean isEmpty();    // 判断汇合是否为空
    boolean contains(Object o);    // 判断汇合中是否存在该元素
    Iterator<E> iterator();    // 迭代器，用于遍历汇合应用
    Object[] toArray();    // 将汇合转换成数组
    <T> T[] toArray(T[] a);    // 将汇合转换成指定类型的数组
    boolean add(E e);    // 将元素增加到汇合中
    boolean remove(Object o);    // 将元素从汇合中删除
    boolean containsAll(Collection<?> c);    // 该汇合是否蕴含了汇合 c
    boolean addAll(Collection<? extends E> c);    // 将汇合 c 的元素都加到该汇合中
    boolean removeAll(Collection<?> c);    // 将汇合 c 与该汇合雷同的元素都删除
    boolean retainAll(Collection<?> c);    // 去两个汇合的交加并保留在该汇合中，如果不存在雷同元素，则该汇合为空
    void clear();    // 革除该汇合中元素
    boolean equals(Object o);    // 用于判断两汇合是否相等
    int hashCode();    // 获取 hash 值}

在 Java 8 中，接口还增加了默认办法：

// Java 8 新增加的默认办法
default boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {if (filter.test(each.next())) {each.remove();
            removed = true;
        }
    }
    return removed;
}
// 将汇合转换为流
default Stream<E> stream() {return StreamSupport.stream(spliterator(), false);
}
// 将汇合转换为并行流
default Stream<E> parallelStream() {return StreamSupport.stream(spliterator(), true);
}

以上就是 Collection 的 API 了。子类继承后，这些办法也都继承了，然而子类能够用不同的数据结构来实现。

Iterator & Iterable

Iterator 是 Java 中的迭代器，可能让实现了该接口的类进行迭代遍历，咱们来看一下 Iterator 接口：

public interface Iterator<E> {boolean hasNext();    // 判断是否还存在下一个对象
    E next();    // 返回汇合中的下一个对象，并将拜访指针向前挪动一位
    default void remove() {    // 删除操作
        throw new UnsupportedOperationException("remove");
    }
    // JDK 1.8
    default void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

而咱们接下来要学习的 Collection 接口继承了 Iterable 接口，该接口中的 iterator() 办法可能产生 Iterator 对象，来对汇合进行迭代遍历：

public interface Iterable<T> {Iterator<T> iterator();
    // JDK 1.8
    default void forEach(Consumer<? super T> action) {Objects.requireNonNull(action);
        for (T t : this) {action.accept(t);
        }
    }
    default Spliterator<T> spliterator() {return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Iterable 接口提供了一个获取 Iterator 对象的办法，所以实现了 Iterable 接口的汇合仍旧能够应用 迭代器 遍历和操作汇合中的对象。

咱们应用一下实现了Iterable 接口的汇合应用 Iterator 迭代器进行遍历：

LinkedList<String> list = new LinkedList<>();
list.add("Feb");
list.add(null);
list.add("Jan");
list.add("Mar");
System.out.println(Arrays.toString(list.toArray()));
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {String it = iterator.next();
    if (it == null) iterator.remove();}
System.out.println(Arrays.toString(list.toArray()));
/**
 * 输入后果：* [Feb, null, Jan, Mar]
 * [Feb, Jan, Mar]
 */

而这样子比拟麻烦，在 JDK 1.8 之后，就提供了 for-each 办法来遍历实现了 Iterable 接口的对象，它是 Java 中的一种 语法糖。如下所示：

for (String s : list) {System.out.println(s);
}

ListIterator 存在于 List 汇合之中，是一个性能比 Iterator 更弱小的迭代器。

public interface ListIterator<E> extends Iterator<E> {boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();    // 
    void remove();    // 移除以后索引地位的元素
    void set(E e);    // 设置以后索引的元素
    void add(E e);    // 在以后索引地位增加元素
}

从下面的办法中就能够理解到，ListIterator 是一个双向挪动，并依据迭代器中指向以后地位的元素产生指向前一个和后一个元素的索引 index。

public static void main(String[] args) {List<String> list = new ArrayList<>();
    list.add("Jan");
    list.add(null);
    list.add("Feb");
    list.add("Mar");
    System.out.println("迭代之前的汇合 =" + Arrays.toString(list.toArray()));
    System.out.println("向后遍历");
    ListIterator<String> iterator = list.listIterator();
    while (iterator.hasNext()) {System.out.println("以后元素：" + iterator.next() + "的后一个索引：" + iterator.nextIndex());
    }
    System.out.println("向前遍历");
    while (iterator.hasPrevious()) {String pre = iterator.previous();
        System.out.println("以后元素：" + pre + " 的前一个索引“);
        if (null == pre) iterator.set("Aug");
    }
    System.out.println("迭代之后的元素 =" + Arrays.toString(list.toArray()));
}
/**
 * 输入后果：* 迭代之前的汇合 =[Jan, null, Feb, Mar]
 * 向后遍历
 * 以后元素：Jan 的后一个索引：1
 * 以后元素：null 的后一个索引：2
 * 以后元素：Feb 的后一个索引：3
 * 以后元素：Mar 的后一个索引：4
 * 向前遍历
 * 以后元素：Mar 的前一个索引：2
 * 以后元素：Feb 的前一个索引：1
 * 以后元素：null 的前一个索引：0
 * 以后元素：Jan 的前一个索引：-1
 * 迭代之后的元素 =[Jan, Aug, Feb, Mar]
 */

fail-fast

fail-fast 是 Java 汇合中的一种谬误检测机制，当多个线程对局部汇合进行构造上的扭转的操作时，有何能会产生 fail-fast 机制，这个时候会抛出 ConcurrentModificationException 异样。

最简略的例子就是在应用 for-each 语法进行遍历时进行删除操作：

List<String> list = new ArrayList<>();
list.add("Jan");
list.add(null);
list.add("Feb");
list.add("Mar");
System.out.println(Arrays.toString(list.toArray()));
for (String s : list) {if (s == null) list.remove(s);
}
System.out.println(Arrays.toString(list.toArray()));

这样在运行时会报错：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
    at xxx.xxx.Xxxx.java:22)

咱们都晓得 for-each 只是一种 语法糖，自身还是 Iterator 操作，咱们看下面报错中的源码：

public E next() {checkForComodification();
    ... 省略...
}

在 Iterator 的 next 操作时，会对该操作进行查看：

final void checkForComodification() {if (modCount != expectedModCount)
        throw new ConcurrentModificationException();}

而 modCount 的值，会在咱们调用 remove 操作时进行批改：

public E remove(int index) {Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}
private void fastRemove(Object[] es, int i) {
    modCount++;    // 在进行删除是会对 modCount 进行 ++ 操作
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

使得 modCount 与 expectedModCount 的值不能相等，因而抛出 java.util.ConcurrentModificationException 异样，终止遍历。

而如果想要解决上述的问题，咱们给出两个计划：

应用 Iterator 操作进行删除或者 JDK 1.8 新增的 removeIf 默认办法。

Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {String s = iterator.next();
        if (s == null) iterator.remove();}
// 或者
list.removeIf(Objects::isNull);

还能够应用 CopyOnWriteArrayList 并发容器来替换 ArrayList。

上面咱们看一下继承了 Collection 接口的三大子接口。

List

List 接口扩大自 Collection 接口，其特点是有序、能够反复。

List 次要新增了以下办法：

// 在某个地位上将汇合 c 增加到该汇合中
boolean addAll(int index, Collection<? extends E> c);
// 通过下标获取元素
E get(int index);
// 通过下标设置元素
E set(int index, E element);
// 通过下标增加元素
void add(int index, E element);
// 通过下标移除元素
E remove(int index);
// 返回该元素的下标地位
int indexOf(Object o);
// 返回该元素的最初遇到的地位
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);

咱们罕用的 List 类次要是 ArrayList 和 LinkedList。

ArrayList

ArrayList 的底层采纳数组来进行对象的存储：

transient Object[] elementData;

又因为实现 RandomAccess 接口，因而在查找的时候十分快。

而在增加一个元素的时候因为是增加在尾部 elementData[size++] = e，因而程序增加时十分的快。

而 ArrayList 在删除元素的时候，会应用 System.arraycopy进行一次复制操作。

System.arraycopy(elementData, index+1, elementData, index, numMoved)

如果复制的元素过多，则会十分损耗性能。

LinkedList

LinkedList 的底层应用双向链表实现对象的存储。程序存取，容许存储任何对象（包含 null）。LinkedList 同时还实现了 Deque 接口，该接口是继承于 Queue，因而该类能够当做队列应用。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 指向第一个结点的指针
    transient Node<E> first;
    // 指向最初一个结点的指针
    transient Node<E> last;
    ... 省略...
}

因为 LinkedList 实现了 Deque 接口，因而它的操作是双向的，例如如下办法，能够抉择增加头部还是尾部的操作。

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

LinkedList 中以 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;
    }
}

咱们由上源码中，晓得了 LinkedList 的数据结构，因而，要应用 LinkedList 进行增删改查，都会从头开始遍历进行查找，不像 ArrayList 能够随机拜访。然而，在进行插入和删除的操作时，比 ArrayList 快，只须要将指针指向你所须要的元素即可。

Vector

Vector 的数据结构与 ArrayList 类似，都是应用数组 Object[] elementData 来进行数据的存储，但会应用 synchronized 关键字加锁进行同步：

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

add 办法就是用 synchronized 关键字加锁，其它如 get、remove 等办法都有加锁。因而，Vector 应用 synchronized 关键字来保障线程平安，但这样的效率较低，曾经不太倡议应用。

咱们个别举荐应用 ArrayList 来代替 Vector 来实现性能。

Stack

Stack 继承于 Vector，它是一个后入先出的容器，就是一直将元素压入（push）Stack中，而弹出（pop）元素必然是最初压入Stack 中的元素。

Stack 实现的有这几种办法：

// 将元素键入栈中
public E push(E item) {}
// 将元素从栈顶中弹出
public synchronized E pop() {}
// 去除栈顶的元素但不弹出
public synchronized E peek() {}
// 判断栈是否为空
public boolean empty() {}
// 返回对象离栈顶的间隔
public synchronized int search(Object o) {}

但因为 Stack 继承于 Vector，因而它也蕴含 Vector 中的全副 API。也因而不举荐应用它，咱们能够应用 Deque 接口来本人实现栈的性能。

线程平安

因为线程平安的 Vector 类曾经不举荐应用，但 ArrayList 或者 LinkedList 没有线程平安机制，咱们须要实现线程平安的话，就要应用 Collections 类的静态方法 synchronizedList() 获取线程平安的 List 或者应用 CopyOnWriteArrayList 实现线程平安的操作。

怎么确保一个汇合不能被批改？

能够应用 Collections.unmodifiableCollection(Collection c) 办法来创立一个只读汇合，这样扭转汇合的任何操作都会抛出 java.lang.UnsupportedOperationException 异样。

示例代码：

List<String> list = new ArrayList<>();
list.add("Jan");
Collection<String> clist = Collections.unmodifiableCollection(list);
clist.add("Feb");    // 运行时此处报错

Queue

Queue队列是先进先出的线性数据结构；咱们看一下 Queue 的接口：

public interface Queue<E> extends Collection<E> {boolean add(E e);    // 增加元素，失败会抛异样
    boolean offer(E e);    // 同上，返回值(会返回 false)
    E remove();    // 删除元素，失败会抛异样
    E poll();    // 同上，返回值(会返回 null)
    E element();    // 获取元素，失败会抛异样
    E peek();    // 同上，返回值(会返回 null)
}

咱们由上可知，Queue 接口是继承 Collection 的子接口，次要是增加了六个办法，能够分为两组，用于增删查。add/remove/element 为一组，它的状况是失败后抛出异样；offer/poll/peek 为一组，它的状况是失败后返回非凡的值（null 或 false）。在队列有界且无闲暇空间时才会使增加操作抛出异样或返回false。这种状况咱们应用 offer 这种来代替 add 这组操作。

在 JDK 中没有一个队列的实现仅仅实现了 Queue 接口。因为 Queue 只有根本的队列性能。因而，要扩大 Queue 接口。

PriorityQueue

PriorityQueue 是基于二叉堆实现的优先级队列，而堆是采纳数组实现的，并且能够指定 Comparator 比拟器，如果不传入 Comparator，则天然排序：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // 队列
    private final Comparator<? super E> comparator;    // 比拟器，用于确定优先级高下
    ... 省略...
}

上述的正文介绍的是 transient Object[] queue 存储的优先队列示意为一个均衡的二叉树并且队列与其子队列的地位。如果不传入 comparator，则会依照天然程序排序。

public boolean offer(E e) {if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

咱们看一下它的增加元素的办法能够晓得，PriorityQueue 不是线程平安的，并且不反对 null。而如果想要线程平安，能够应用并发包下的 java.util.concurrent.PriorityBlockingQueue 类。

Deque

Deque 接口就是对 Queue 的扩大，Deque 是继承于 Queue 实现两端都能进出的双端队列。它的 API 中就有对 First 端和 Last 端的操作，add/remove/get 是一组操作，会抛异样；offer/poll/peek 是一组操作，它会在失败时返回值。

public interface Deque<E> extends Queue<E> {void addFirst(E e);    // 增加到头部，异样报错
    void addLast(E e);    // 增加到尾部，异样报错
    boolean offerFirst(E e);    // 增加到头部，失败返回 false。boolean offerLast(E e);        // 增加到尾部，失败返回 false。E removeFirst();    // 移除头部元素，异样报错
    E removeLast();        // 移除尾部元素，异样报错
    E pollFirst();        // 移除头部元素，失败返回 null。E pollLast();        // 移除尾部元素，失败返回 null。E getFirst();        // 获取头部元素，异样报错
    E getLast();        // 获取尾部元素，异样报错
    E peekFirst();        // 获取头部元素，失败返回 null。E peekLast();        // 获取尾部元素，失败返回 null。boolean add(E e);    // 增加元素，异样报错
    boolean offer(E e);    // 增加元素，失败返回 false。E remove();            // 移除元素，异样报错
    E poll();            // 移除元素，失败返回 false。E element();        // 获取元素，异样报错
    E peek();            // 获取元素，失败返回 null。void push(E e);        // 入栈
    E pop();            // 出栈
    boolean remove(Object o);    // 移除指定对象
    boolean contains(Object o);    // 判断元素是否存在
}

而在应用时，请抉择同一组进行应用。

实现 Deque 接口的次要有 ArrayDeque、LinkedList、PriorityQueue 和其它一些并发容器 ConcurrentLinkedDeque、LinkedBlockingDeque 等。

这里咱们只介绍 ArrayDeque 和 PriorityQueue。LinkedList 曾经在下面介绍过了。

ArrayDeque

ArrayDeque 是实现 Deque 接口的双端队列，它继承于 AbstractCollection，其底层还是基于 Collection 接口实现的汇合框架：

public class ArrayDeque<E> extends AbstractCollection<E>
    implements Deque<E>, Cloneable, Serializable {transient Object[] elements;    // 用于元素存储的队列是数组实现的
    transient int head;    // 头部索引
    transient int tail;    // 下一步要增加到尾部的索引(以后索引为 tail-1)
    ... 省略...
}

咱们看一下 ArrayDeque 实现的 addFirst 办法：

public void addFirst(E e) {if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();}

从 addFirst 中能够看出，它的操作不是线程平安的，且不能插入 null，而如果 head == tail，就会进行扩容。

而 LinkedList 也是实现了 Deque，不可避免的与 ArrayDeque 进行比拟。

ArrayDeque 底层是由数组进行实现的，而 LinkedList 底层是由循环链表来进行实现，链表在增加、删除办法的性能要高于数组构造，但查询方法数组构造要高于链表构造。但数组中元素不进行挪动，只在前面增加，效率也不差。

ArrayDeque 能够作为队列应用，也能够作为栈来应用。因而，咱们能够应用它来代替 Stack 实现栈性能。

Set

Set 接口扩大自 Collection 接口，其特点是不反复。

public interface Set<E> extends Collection<E> {int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

由 Set 接口与 Collection 进行比照，Set 具备与 Collection 齐全一样的接口，没有额定的性能。

Set的罕用的实现类有 HashSet、LinkedHashSet 与 TreeSet。

HashSet

从HashSet 的源码中可知，它的底层应用 HashMap 的 key 来存储元素，次要特点是无序的。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // 用于存储元素的映射表
    private transient HashMap<E,Object> map;
    // 用来寄存在映射表中的伪值
    private static final Object PRESENT = new Object();
    public HashSet() {map = new HashMap<>();
    }
    ... 省略...
    public boolean add(E e) {
        // 将值当作映射表的键来存储
        return map.put(e, PRESENT)==null;
    }
    ... 省略...
}

而从 add 办法可知，HashSet 是否线程平安由 HashMap 决定，而 HashMap 自身就不是线程平安的，因而 HashSet 也是线程不平安的。

LinkedHashSet

LinkedHashSet 自身继承 HashSet

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {public LinkedHashSet() {super(16, .75f, true);
    }
}

它会调用父类 HashSet 的构造方法：

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

有父类中的构造方法可知，HashMap 是由 LinkedHashMap 来实现的，而 LinkedHashMap 的底层应用的是 HashMap + 双向链表来实现，这样可能保留插入的程序。LinkedHashSet 也不是线程平安的。

TreeSet

TreeSet 底层是应用 TreeMap 来实现，数据结构是数组 + 红黑树，因而它存储的元素有序，能够自定义比拟器或应用自身比拟器实现天然排序。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    private transient NavigableMap<E,Object> m;    // 用来存储元素的映射表
    
    // 用来寄存在 Map 的伪值与 key 构建成键值对
    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {this.m = m;}
    public TreeSet() {this(new TreeMap<E,Object>());
    }
    ... 省略...
}

如果须要自定义排序，应用如下构造方法来传入一个 Comparator 比拟器：

public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

TreeSet 不能够存储 null，并且也不是线程平安的。因为 TreeSet 无反复且有序的特点，能够应用 TreeSet 实现学校的问题榜单性能。

class Student implements Comparable<Student> {
    String name;
    double totalScore;
    public Student(String name, double totalScore) {
        this.name = name;
        this.totalScore = totalScore;
     }
    @Override
    public int compareTo(Student o) {return Double.compare(o.totalScore, this.totalScore);
    }
    @Override
    public String toString() {return "Student{" + "姓名 ='" + name + '\'' + ", 总分 =" + totalScore + '}';
    }
}
public static void main(String[] args) {Set<Student> students = new TreeSet<>();
    students.add(new Student("小赵", 561.5));
    students.add(new Student("小钱", 342.5));
    students.add(new Student("小孙", 720));
    students.add(new Student("小李", 480));
    System.out.println(Arrays.toString(students.toArray()));
}
/**
 * 输入后果：* [Student{姓名 ='小孙', 总分 =720.0}, Student{姓名 ='小赵', 总分 =561.5}, Student{姓名 ='小李', 总分 =480.0}, Student{姓名 ='小钱', 总分 =342.5}]
 */

下面就是对 Collection 汇合的大体介绍，上面让咱们来理解 Map。

Map

Map是存储着由 key-value组成的对象的映射表，key 具备唯一性，咱们能够应用 key 来查找对应的 value。

上面看一下 Map 接口的定义：

public interface Map<K,V> {// 映射表大小(用于判断映射表中键值对的数量)
    int size();
    // 判断映射表是否为空
    boolean isEmpty();
    // 判断该映射表中是否蕴含指定的键 key
    boolean containsKey(Object key);
    // 判断该映射表中是否蕴含指定的值 value
    boolean containsValue(Object value);
    // 通过键 key，获取该映射表中对应的值
    V get(Object key);
    // 将 key-value 对应关系寄存在该映射表中
    V put(K key, V value);
    // 删除该映射表中对应的键 key 的映射关系
    V remove(Object key);
    // 将 m 映射表中的键值关系全副存入该映射表中
    void putAll(Map<? extends K, ? extends V> m);
    // 移除以后映射表中所有的映射关系
    void clear();
    // 将该映射表中所有的键组成汇合，并返回
    Set<K> keySet();
    // 将该映射表中所有的值组成汇合，并返回
    Collection<V> values();
    // 将该映射表中所有键值对组成汇合，并返回
    Set<Map.Entry<K, V>> entrySet();
    // Entry 接口代表 Map 中存储的键值关系
    interface Entry<K,V> {
        // 返回以后 entry 对应的键
        K getKey();
        // 返回以后 entry 对应的值
        V getValue();
        // 设置以后 entry 对应键的值
        V setValue(V value);
        // 判断以后 entry 与另一个是否相等
        boolean equals(Object o);
        // 获取以后 entry 的 hash 码
        int hashCode();}
    // 用于判断两个映射表是否相等
    boolean equals(Object o);
    // 获取映射表的 hash 码
    int hashCode();}

有以上的办法能够晓得一些 Map 提供的性能。而对于 Map 的实现会有两种不同的方向：

  • AbstractMap：应用抽象类来实现 Map 的一些通用性能，基本上实现的 Map 都要继承它，例如 HashMap。
  • SortedMap：这是对 Map 接口进行扩大的可排序的接口类，该接口中定义了 Comparator 对象，会依照它进行排序，例如 TreeMap。

上面介绍几个最罕用的实现类 HashMap、TreeMap、LinkedHashMap 和 ConcurrentHashMap。

HashMap

HashMap 是最罕用的一个 Map，它实现了 AbstractMap 类

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

它通过计算 key 对象的 hash 值来决定在 Map 中的存储地位，不能保障插入的程序。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在 JDK 1.8 之前，底层采纳 数组 + 单链表 实现；JDK 1.8 之后应用 数组 + 单链表 + 红黑树 实现。产生 hash 抵触时，HashMap 会将具备雷同映射地址的元素连成一条链表，当链表长度大于 8 且数组长度大于 64 时，会将单链表转换成红黑树。

TreeMap

TreeMap 是具备排序功能的 Map，它实现了 NavigableMap 接口：

public interface NavigableMap<K,V> extends SortedMap<K,V> {... 省略...}

而 NavigableMap 是继承于 SortedMap 接口的扩大接口，能够接管一个 Comparator 进行自定义排序：

public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

而如果不传入 Comparator，默认会依照 key 天然排序，因而，key 是要实现了 Comparable 接口的对象，否则会在运行时抛出 java.lang.CassCastException 异样。

TreeMap 底层是采纳 数组 + 红黑树 来实现的数据结构，整个数据结构都放弃着有序的状态，并且不能够插入null 键，但能够有 null 值。

上面来举一个小例子：

class Student {
    String name;
    double totalScore;
    public Student(String name, double totalScore) {
            this.name = name;
            this.totalScore = totalScore;
        }
    @Override
    public String toString() {return "Student{" + "姓名 ='" + name + '\'' + ", 总分 =" + totalScore + '}';
    }
}
public static void main(String[] args) {TreeMap<Integer, Student> students = new TreeMap<>();
    students.put(2, new Student("小赵", 561.5));
    students.put(4, new Student("小钱", 342.5));
    students.put(1, new Student("小孙", 720));
    students.put(3, new Student("小李", 480));
    System.out.println(students);
}
/**
 * 输入后果：* {1=Student{姓名 ='小孙', 总分 =720.0}, 2=Student{姓名 ='小赵', 总分 =561.5}, 3=Student{姓名 ='小李', 总分 =480.0}, 4=Student{姓名 ='小钱', 总分 =342.5}}
 */

LinkedHashMap

LinkedHashMap 是在 HashMap 的根底上加上双向链表，用于保障元素的有序性。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    // 用于拜访链表的头部
    transient LinkedHashMap.Entry<K,V> head;
    // 用于拜访链表的尾部
    transient LinkedHashMap.Entry<K,V> tail;
    ... 省略...
}

来个小例子：

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("八月", 8);
map.put("十二月", 12);
map.put("二月", 2);
map.put("七月", 7);
System.out.println(map);
/**
 * 输入后果：* {八月 =8, 十二月 =12, 二月 =2, 七月 =7}
 */

能够看出，它输入后果与插入程序统一，是有序的。

IdentityHashMap

IdentityHashMap 继承于 AbstractMap 抽象类并实现了 Map 接口，它与 HashMap 的继承类与实现接口基本相同。

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable

然而 IdentityHashMap 应用 Object[] table 数组来存储元素，并且能够存储反复的 key，因为在 IdentityHashMap 中应用的是 item == k，要雷同的援用能力判断它俩雷同。

咱们看上面的例子：

IdentityHashMap<String, Integer> identityHashMap = new IdentityHashMap<>();
String jan1 = "Jan";
String jan2 = "Jan";
identityHashMap.put(jan1, 1);
identityHashMap.put(jan2, 1);
System.out.println(identityHashMap.get("Jan"));
System.out.println(identityHashMap);
/**
 * 输入后果：* 1
 * {Jan=1}
 */

这是因为 jan1 和 jan2 都只想常量池中的 Jan。而如果应用如下形式：

IdentityHashMap<String, Integer> identityHashMap = new IdentityHashMap<>();
String jan1 = "Jan";
String jan2 = new String("Jan");
identityHashMap.put(jan1, 1);
identityHashMap.put(jan2, 1);
System.out.println(identityHashMap.get("Jan"));
System.out.println(identityHashMap);
/**
 * 输入后果：* 1
 * {Jan=1, Jan=1}
 */

这阐明 jan2 是指向堆中的空间，new 进去的字符串对象。而如果应用 identityHashMap.get(new String("Jan")) 来获取值，就会输入 null，原理也是在堆中创立的新的字符串对象。

IdentityHashMap 也是 hash 存储，因而它无序，而且还不是线程平安的。

WeakHashMap

WeakHashMap 继承于 AbstractMap 抽象类并实现了 Map 接口，它也是基于 hash 实现的 Map，因而它与 HashMap 的大多数性能都雷同。

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>

然而在 WeakHashMap 中实现的 Entry 却不雷同：

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;
    Entry(Object key, V value,
        ReferenceQueue<Object> queue,
        int hash, Entry<K,V> next) {super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    ... 省略...
}

Entry 继承了 WeakReference，利用 WeakReference 的机制来实现不阻止 GC 回收Key，即每次 GC，都会将这个对象革除。

而WeakHashMap 中保护的 ReferenceQueue 的作用就是用来存储哪些 key 已被革除。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

在每次 put/size 等操作时，都会调用 expungeStaleEntries 办法，用来删除表中曾经被删除的 key 对应的 Entry，来达到同步的成果。

private void expungeStaleEntries() {for (Object x; (x = queue.poll()) != null; ) {synchronized (queue) {@SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) x;    // 队列中已被删除的 entry
            // 获取元素在 table 的索引
            int i = indexFor(e.hash, table.length);
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {    // 偏移链表
                Entry<K,V> next = p.next;
                if (p == e) {    // 如果链表中存在过期的 entry，咱们就要删除它
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // 咱们这里将置 null，来帮忙 GC
                    e.value = null; // Help GC
                    size--;    // 容器数量减一
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

WeakHashMap 通常作为缓存应用，实用于存储只需保留短暂工夫的键值对，它也是非线程平安的汇合。

Hashtable

Hashtable 也是实现了 Map 接口的类。底层应用 数组 + 链表 来实现。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {private transient Entry<?,?>[] table;
    ... 省略...
}

在进行 put/remove 等操作时，都会在办法上增加 synchronized 关键字来实现同步，比较简单粗犷。

public synchronized V put(K key, V value) {if (value == null) {throw new NullPointerException();
    }
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

这样的操作使得 Hashtable 是一个线程平安的 Map，但这样也使 Hashtable 的性能较差，与 Vector 差不多，因而会被淘汰。

而咱们想要应用线程平安的 Map，就能够应用 java.util.concurrent 包下的 ConcurrentHashMap 类。

总结

此文是对 Java 容器做一个较为整体的介绍，理解了每个容器的个性。咱们做一下总结：

  1. 以对象形式存储，应用的是实现 Collection 接口的实现类；以键值对形式存储，应用的是实现 Map 接口的实现类。
  2. 实现 List 接口的类都是有序并可反复存储的汇合，常见的有 ArrayList、LinkedList 和 Vector。
  3. 实现 Set 接口的类都存储的元素不可反复，常见的有 HashSet、LinkedHashSet和TreeSet。
  4. Queue 接口实现了队列的基本操作，而 Deque 定义双端队列的操作。
  5. 实现了 Map 接口的类有基于 hash 存储的 HashMap，能够排序的 TreeMap 和弱援用的 WeakHashMap。

而在抉择容器时，咱们通常都会将它们实现的数据结构，线程安全性，是否反复，有序，利用场景等进行比照，来抉择咱们要应用的容器。

更多内容请关注公众号「海人的博客」，回复「资源」即可取得收费学习资源！

正文完
程序员
发表至： 程序员
2020-12-15
 0
关于程序员:机器学习集成学习聚类分析降维学习
关于程序员:JavaScript隐式类型转换原理优先级规则及场景
关于程序员:客户服务高触达零代码从短信邮件跳转小程序客服
关于程序员:Sed-备忘清单开发速查表分享