集合

集合框架

早在 Java 2 中之前，Java 就提供了特设类。比如：Dictionary, Vector, Stack, 和 Properties 这些类用来存储和操作对象组。
虽然这些类都非常有用，但是它们缺少一个核心的，统一的主题。由于这个原因，使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。

集合框架被设计成要满足以下几个目标。

• 该框架必须是高性能的。基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
• 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
• 对一个集合的扩展和适应必须是简单的。

集合类的两大基本接口就是Collection和Map。

Collection接口

这个接口有两个基本方法：

public interface Collection<E>{
    boolean add(E element);
    Iterator<E> iterator();
    //...
}

add()方法用于向集合中添加元素，如果添加元素确实改变了集合就返回true，没有就返回false。
iterator()方法用于返回一个实现了Iterator接口的对象。这个可以使用这个迭代器对象依次访问集合中的元素。

List

List是一个有序集合（ordered collection）。元素会增加到容器中的特定位置。可以采用两种方式访问元素：迭代器，随机访问（random access）。

List接口定义了多个用于随机访问的方法：

void add(int index, E element);
void remove(int index);
E get(int index);
E set(int index, E element);

链表 LinkedList

interface LinkedList<E>{
    LinkedList();
   LinkedList(Collection<? extends E> elements);
   void addFirst(E element);
   void addLast(E element);
   E getFirst();
   E getLast();
   E removeFirst();
   E removeLast();
   //...
}

LinkedList是一种可以在任何位置进行高效地插入和删除操作地有序序列，是一个继承于AbstractSequentialList的双向链表。

链表是一个有序集合，每个对象地位置十分重要。LinkedList.add方法将对象添加到链表地尾部，但是我们常常需要将元素添加到链表中间。因此，我们需要利用描述集合中位置的迭代器来添加元素，但是Iterator接口中没有add方法，因此，集合类库提供了子接口 ListIterator 。

对于链表，我们可以使用ListIterator类从前后两个方向遍历链表中的元素，并可以添加、删除元素。

对于链表，它不支持快速随机访问。如果要查看链表中的某个元素必须从头开始按顺序遍历，没有捷径。因此在程序需要采用整数索引访问元素时，一般不建议选用链表。
但是LinkedList类还是提供了一个用来访问某个特定元素的get方法，但是这个方法效率不高，下面这种做法是错误的，效率极低：

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

数组列表 ArrayList

ArrayList类实现了List接口，应该是大家第一次接触集合类的入门类了，大家应该都非常熟悉了。ArrayList封装了一个动态再分配的对象数组，可以用get和set方法随机地访问每个元素。

Set

set是没有重复元素的元素集合。该集合中没有特有的方法，直接继承自Collection。

set的add方法首先在集中查找要添加的对象，如果不存在，就将这个对象添加进去。

HashSet

HashSet类实现了基于散列表的集。可以用add方法添加元素。contains方法已被重新定义，用来快速地查看是否某个元素已经出现在集中。它只在某个桶中查找元素，而不必查看集合中的所有元素。

散列集迭代器将依次访问所有的桶。由于散列将元素分散在表的各个位置上，所以访问它们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用HashSet。

由于Set集合是不能存入重复元素的集合。那么HashSet也是具备这一特性的。HashSet如何检查重复？HashSet会通过元素的hashcode（）和equals方法进行判断元素师否重复。

当你试图把对象加入HashSet时，HashSet会使用对象的hashCode来判断对象加入的位置。同时也会与其他已经加入的对象的hashCode进行比较，如果没有相等的hashCode，HashSet就会假设对象没有重复出现。

简单一句话，如果对象的hashCode值是不同的，那么HashSet会认为对象是不可能相等的。

因此我们自定义类的时候需要重写hashCode，来确保对象具有相同的hashCode值。

注意：HashSet集合在判断元素是否相同先判断hashCode方法，如果相同才会判断equals。如果不相同，是不会调用equals方法的。
**

TreeSet

TreeSet树集，与散列集十分类似，不过，它比散列集有所改进。树集是一个有序集合，可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动地按照排序后地顺序呈现。排序是用树结构完成的（当前实现使用的是红黑树）。

将一个元素添加到树中要比添加到散列表中慢，但是，与检查数组或链表中的重复元素相比还是快很多。如果树中包含了n个元素，查找新元素的正确位置平均需要log2 n次比较。

如果不需要对数据进行排序，就没有必要付出排序的开销。更重要的是，对于某些数据来说，对其排序要比散列函数更加困难。散列函数只是将对象适当地打乱存放，而比较却要精准地判别每个对象。

LinkedHashSet

LinkedHashSet 首先我们需要知道的是它是一个 Set 的实现，所以它其中存的肯定不是键值对，而是值。此实现与 HashSet 的不同之处在于，LinkedHashSet 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

对于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。
LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

Queue

Queue用于模拟队列这种数据结构。队列通常是指“先进先出（FIFO）”的容器。队列的头部保存在队列中存放时间最长的元素，尾部保存存放时间最短的元素。新元素插入到队列的尾部，取出元素会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

public interface Queue<E> extends Collection<E> {
    //将指定元素插入到队列的尾部
    void add(E e);
    //获取队列头部的元素，但是不删除该元素
    E element();
    //将指定的元素插入此队列的尾部。当使用容量有限的队列时，此方法通常比add(Object e)有效
    boolean offer(E e);
    //返回队列头部的元素，但是不删除该元素。如果队列为空，则返回null
    E peek();
    //返回队列头部的元素，并删除该元素。如果队列为空，则返回null
    E poll();
    //获取队列头部的元素，并删除该元素
    E remove();
}

PriorityQueue

优先级队列（priority queue）是Queue的一个实现类。它里面的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。也就是说，无论何时调用remove方法，总会获得当前优先级队列中最小的元素。

优先级队列使用了一个优雅且高效的数据结构，称为堆（heap）。堆是一个可以自我调整的二叉树，对树进行添加和删除操作，可以让最小的元素移动到根，而不必花费时间对元素进行排序。

使用优先级队列的典型示例是任务调度。每一个任何有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，都将优先级最高的任务从队列中删除。

Map

Java类库里提供了个Map接口。映射（map）用来存放键/值对，是通过指定某个键的信息，查找与之对应的值的一种数据结构。

public interface Map<K,V> {
    //返回此映射中的键-值映射关系数。
    int size();
    //如果此映射未包含键-值映射关系，则返回 true。
    boolean isEmpty();
    //如果此映射包含指定键的映射关系，则返回 true。
    boolean containsKey(Object key);
    //如果此映射将一个或多个键映射到指定值，则返回 true。
    boolean containsValue(Object value);
    //返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。
    V get(Object key);
    //将指定的值与此映射中的指定键关联（可选操作）。
    V put(K key, V value);
    //如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。
    V remove(Object key);
    //从指定映射中将所有映射关系复制到此映射中（可选操作）。
    void putAll(Map<? extends K, ? extends V> m);
    // 从此映射中移除所有映射关系（可选操作）。
    void clear();
    //返回此映射中包含的键的 Set 视图。
    Set<K> keySet();
    //返回此映射中包含的值的 Collection 视图。
    Collection<V> values();
    //返回此映射中包含的映射关系的 Set 视图。
    Set<Map.Entry<K, V>> entrySet();
    //...
}

HashMap

概述

Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。

简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。

特别地，HashMap最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，HashMap 是 Map 的一个非同步的实现。

接口和父类

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

• 实现了Map接口，Map 接口定义了键值映射规则；
• 实现了Cloneable接口，表示该对象能被克隆；
• 实现了Serializable接口，表示该对象能被序列化；
• 继承了AbstractMap类，AbstractMap提供了 Map 的基本实现

属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}

• loadFactor加载因子

loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

• threshold

threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

• Node节点类源码

// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
       final K key;//键
       V value;//值
       // 指向下一个节点
       Node<K,V> next;
       //构造器
       Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        // 重写hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写 equals() 方法
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
}

• 树节点源码

//红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父
        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);
        }
        // 返回根节点
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
       }

构造器

HashMap()
**

    /**
     *initialCapacity为默认16，loadFactor为0.75f
     */
    public HashMap() {
        //负载因子:用于衡量的是一个散列表的空间的使用程度
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        //其他值全为默认
    }

HashMap(int initialCapacity, float loadFactor)

    /**
     *initialCapacity和loadFactor由用户指定的构造器
     *initialCapacity必须合法且不能超过最大容量1<<30，即2^30=1073741824
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //输入的初始容量不合法时抛异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //输入的初始容量大于最大容量时置为最大容量  1 << 30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //负载因子必须合法
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动扩容操作
        this.threshold = tableSizeFor(initialCapacity);
    }

HashMap(int initialCapacity)

/**
 *构造指定初始容量，调用上面的构造函数
 */
public HashMap(int initialCapacity) {
    // 直接调用上述构造函数
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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

//该构造函数意在构造一个与指定 Map 具有相同映射的 HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
 }

putMapEntries方法

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put方法和putVal方法

**
HashMap只提供了put用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。

对putVal方法添加元素的分析如下：

• 如果定位到的数组位置没有元素 就直接插入。
• 如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不相同，就判断p是否是一个树节点，如果是就调用e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

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) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; 
        K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // hash值不相等，即key不相等；为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 否则为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

这是JDK 1.8的一个新特性，它在HashMap里使用了红黑树这种数据结构。

而在JDK 1.7里，实现数据插入的方式是定位到数组的位置，如果该位置没有元素则插入数据，如果有元素，则遍历该头结点的链表，用key作对比，如果重复，则覆盖，如果没有，则使用头插法插入元素。

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 数组元素相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一个节点
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else { 
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

数据结构

HashMap底层使用的就是哈希表这种数据结构，它使用最经典的拉链法，也就是链表数组来实现。至于哈希表就不多说了，可以跳转哈希表看具体实现。

在HashMap里，定义了一个table数组，而这个table数组就是哈希表里的链表数组，initialCapacity参数就是数组的长度，也叫做桶的个数。

在这个HashMap类中，每次构造这个类，都会初始化一个Node类型的table数组。

TreeMap

树映射（TreeMap），实现了Map接口，能够把它保存的记录根据键(key)排序,默认是按升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。TreeMap不允许key的值为null。非同步的。

TreeMap用键的整体顺序对元素进行排序，并将其组织成搜索树。

WeekHashMap

弱散列映射（WeekHashMap）实现了Map接口，基于hash-table实现，在这种Map中，key的类型是WeakReference。如果对应的key被回收，则这个key指向的对象会被从Map容器中移除。

WeakHashMap跟普通的HashMap不同，WeakHashMap的行为一定程度上基于垃圾收集器的行为，因此一些Map数据结构对应的常识在WeakHashMap上会失效——size()方法的返回值会随着程序的运行变小，isEmpty()方法的返回值会从false变成true等等。

WeakHashMap使用弱引用保存键。WeakReference对象将引用保存到另外一个对象中，在这里，就是散列键。WeakHashMap将周期性地检查队列，以便找出新添加地弱引用。一个弱引用进入队列意味着这个键不再被他人使用，并且已经被收集起来。于是，WeakHashMap将删除对应的条目。

LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。

LinkedHashMap 是 Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

IdentityHashMap

标识散列映射(IdentityHashMap)类有特殊作用，它的键的散列值不是用hashCode函数计算的，而是用System.identityHashCode方法计算的。这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式。而且，在对两个对象进行比较时，IdentityHashMap类使用==，而不使用equals。

也就是说，不同的键对象，即使内容相同，也被视为是不同的对象。在实现对象遍历算法时，这个类非常有用，可以用来跟踪每个对象的遍历状况。

更新映射项

处理映射时的一个难点就是更新映射项。正常情况下，可以得到与一个键相关联的原值，完成更新，再放回去。但有一种情况：

//使用映射统计一个单词出现的次数。当看到一个单词(word)时，我们将计数器加1
counts.put("word", counts.get("word") + 1);

这样是可以的，但是第一次看到word时，map里没有该键，于是get会返回null，出现NullPointerException异常。

以下有三种补救方法：

//第一种办法
counts.put("word",counts.getOrDefault(word,0) + 1);

//第二种方法。只有当键原先存在时才会放入一个值
counts.putIfAbsent(word,0);
counts.put("word", counts.get("word") + 1);

//第三种，把word与1关联，否则使用Integer::sum函数组合原值和1（也就是求和）
counts.merge(word,1,Integer::sum);

映射视图

集合框架不认为映射本身是一个集合。（其他数据结构框架认为映射是一个键/值对集合，或者是由键索引的值集合。）不过，可以得到映射的视图（view）——这是实现了Collection接口或某个子接口的对象。

有三种视图：键集、值集合（不是一个集）、键/值对集。

键和键/值对可以构成一个集，因为映射中一个键只能有一个副本。

public interface Map<K,V> {

    //...

    interface Entry<K,V> {

        //返回键集视图
        Set<K> ketSet();
        //返回值集合视图
        Collection<V> values();
        //返回键/值对集
        Set<Map.Entry<K,V>> entrySet();

        //...
    }
}

如果在键集视图上调用迭代器的remove方法，实际上会从映射中删除这个键和与它关联的值。不过，不能向键集视图增加元素。另外，如果增加一个键而没有同时增加值也是没有意义的。如果视图调用add方法，它会抛出一个UnsupportedOperationException。

迭代器 Iterator

public interface Iterator<E>{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action);
}

通过反复调用next()方法，可以逐个访问集合中的每个元素。但是，如果到达了集合的末尾，next方法将抛出一个NoSuchElementException。因此，想要查看集合中的所有元素，就要利用hasNext()方法：

//正确的使用迭代器姿势
Collection<String> c = ...;
Iterator<String> iterator = c.iterator();
while(iterator.hasNext()){
    String element = iter.next();
}

需要注意，与数组或其他语言的迭代器不一样的是，Java中迭代器应该被认为是位于两个元素之间。一开始迭代器是指向第一个元素之前，在调用了next()方法之后，迭代器便越过了第一个元素，也就是指向了第一个元素和第二个元素之间，并返回了刚刚越过的元素的引用（第一个元素），以此类推。因此，查找一个元素的唯一方法是调用next()；

更重要的是，对next方法和remove方法的调用具有互相依赖性。也就是说，在调用每次remove方法之前，都必须调用next方法，否则是不合法的。如果不这样做，会抛出一个IllegalStateException异常。

//以下是合法的
iterator.next();
iterator.remove();

//这是不合法的
iterator.remove();
iterator.remove();

//这也不行，每次都要调用
iterator.next();
iterator.remove();
iterator.remove();

ListIterator

ListIterator接口是Iterator一个子接口。它定义了一个用于在迭代器位置前面增加一个元素的方法add。

interface ListIterator<E> extends Iterator<E>{
    void add(E element);

    //下面两个方法用于反向遍历链表
    E previous();
    boolean hasPrevious();

    //...
}

和Collection.add不同，该接口的方法不返回boolean类型的值，它假定添加操作总会改变链表。

另外，previous()方法和next()方法一样，返回越过的对象。不过privious()是往前走的，next()是往后走的。

视图与包装器

视图的概念

java中的视图（views），可以说其实就是一个具有限制的集合对象，只不过这里的不是集合对象，而是一个视图对象。例如：这里有一个Test类：

Test[] tests = new Test[10];
List<Test> testList = Arrays.asList(tests);

这里的testList是一个视图对象，具有访问数组元素set，get的方法。但是如果调用改变数组的方法就会抛出异常。所以可以说视图对象可以说是具有限制的集合对象。
利用java类库中的方法我们可以获得不可更改视图，子视图等等，这些视图对于原对象具有不同的操作权限。

视图的应用

轻量级集合包装器

Arrays类的静态方法asList将返回一个包装了普通Java数组的List包装器。这个方法可以将数组传递给一个期望得到列表或集合参数的方法。

Card[] cardDeck = new Card[52];
//...
List<Card> cardList = Arrays.asList(cardDeck);

返回的对象不是ArrayList。它是一个视图对象，带有访问底层数组的get和set方法。改变数组大小的所有方法（例如，与迭代器相关的add和remove方法）都会抛出一个UnsupportedOperationException异常。

asList方法可以接收可变数目的参数。例如：

List<String> name = Arrays.asList("Amy","Bob","Carl");

这个方法调用

Collecitons.nCopies(n,anObject);

将返回一个实现了List接口的不可修改的对象，并给人一种包含n个元素，每个元素都像是一个anObject的错觉。
例如，下面的调用将创建一个包含100个字符串的List，每个串都被设置为“DEFAULT”：

List<String> settings = Collections.nCopies(100,"DEFAULT");

存储代价很小。这是视图技术的一种巧妙应用。

子范围

可以为很多集合建立子范围（subrange）视图。例如，假如有一个列表staff，想从中取出第10个~第19个元素。可以使用subList方法来获得一个列表的子范围视图。

List groups = staff.subList(10,20);

第一个索引包含在内，第二个索引则不包含在内。这与String类的subString操作中的参数情况相同。

可以将任何操作应用于子范围，并且能够自动地反映整个列表地情况。

不可修改的视图

Collections还有几个方法，用于产生集合的不可修改视图（unmodifiable views）。这些视图对现有集合增加了一个运行时的检查。如果发现试图对集合进行修改，就抛出一个异常，同时这个集合将保持未修改的状态。

不可修改视图并不是集合本身不可修改。仍然可以通过集合的原始引用对集合进行修改。并且仍然可以让集合的原始调用更改器方法。

由于视图只是包装了接口而不是实际的集合对象，所以只能访问接口中定义的方法。例如，LinkedList类有一些非常方便的方法，addFirst和addLast，它们都不是List接口的方法，不能通过不可修改视图进行访问。

同步视图

如果有多个线程访问集合，就必须确保集不会被意外地破坏。

例如，如果一个线程视图将元素添加到散列表中，同时另一个线程正在对散列表进行再散列，其结果将是灾难性的。

类库的设计者使用视图机制来确保常规集合的线程安全，而不是实现线程安全的集合类。将映射表转换成具有同步访问方法的Map后，get和put这类方法就会变成同步操作了，即在一个线程调用另一个方法之前，刚才的方法调用必须彻底完成，从而实现了线程安全。

受查视图

“受查”视图用来对泛型类型发生问题时提供调试支持。

例如：

ArrayList<String> strings = new ArrayList<>();
//仅仅警告
ArrayList rawList = strings;
//现在Strings里添加了Date对象
rawList.add(new Date());

这个错误的add命令在运行时检测不到。相反，只有在稍后的另一部分代码中调用get方法，并将结果转化为String时，这个类才会抛出异常。

受查视图可以探测到这类问题：

List<String> safeStrings = Collections.checkedList(strings,String.class);
ArrayList rawList = safeStrings;
//报错！
rawList.add(new Date());

受查视图受限于虚拟机可以运行的运行时检查。例如，对于ArrayList>，由于虚拟机有一个单独的“原始”Pair类，所以，无法阻止插入Pair。

集合与数组的转换

数组转集合

//用Arrays.asList包装器方法
String[] values = ...;
HashSet<String> staff = new HashSet<>(Arrays.asList(values));

集合转数组

集合转数组比较困难，但还是可以使用toArray方法

Object[] values = staff.toArray();

但是这样会得到一个对象数组，并且不能使用强制类型转换

String[] values = (String[])staff.toArray();   //Error！

但是我们可以这样做

String[] values = staff.toArray(new String[0]);

//甚至可以指定数组大小
String[] values = staff.toArray(new String[staff.size()]);