汇合体系图

Java 的汇合能够分为两类：单列汇合和双列汇合。
单列汇合：存储值（value）。
双列汇合：存储键值对 （key-value）。

单列汇合体系图（罕用）

双列汇合体系图（罕用）

单列汇合

Collection

Collection 接口特点

  • 单列汇合。
  • 存储的元素可能是有序（List 的实现类），也可能是无序（Set 的实现类）。

  • 存储的元素可能能够反复（List 的实现类），也可能不能够反复（Set 的实现类）。

    Collection 接口遍历形式

    实现 Collection 接口的类，有两种遍历形式：

    形式一：应用 Iterator 接口

    迭代器的执行原理：

迭代器罕用办法：

// 判断这次迭代是否还有下一个元素boolean hasNext();// 返回迭代的下一个元素（指针挪动到下一个元素，返回上一个元素），如果没有下一个元素，会报异样 NoSuchElementExceptionE next();// 删除迭代器的这个元素，必须先调用 next()，才能够调用 remove()，否则会抛出异样 IllegalStateExceptionremove()

迭代器应用示例：

       Collection<Integer> collection = new ArrayList<>();        for (int i = 0; i < 100; i++) {            collection.add(i);        }        Iterator<Integer> iterator = collection.iterator();        while (iterator.hasNext()) {            Integer i = iterator.next();            System.out.println(i);        }
形式二：加强 for 循环（应用 iterator 的简化版）

示例程序：

        Collection<Integer> collection = new ArrayList<>();        for (int i = 0; i < 100; i++) {            collection.add(i);        }        // 加强 for 循环，底层也是迭代器        // 快捷方式，大写 I        for(Integer i : collection) {            System.out.println(i);        }

底层原理：

加强 for 循环，其实底层也是 iterator。应用 idea 的 debug 性能打个断点测试下：

在循环入口打断点：

在 ArrayList 的 iterator() 办法的实现打上断点：

运行程序，发现程序会到 ArrayList 的 iterator 办法。

看下 ArrayList 的外部类 Itr 类，其实是 Iterator 接口的实现类：

private class Itr implements Iterator<E>

所以加强 for 循环其实就是 Iterator 的简化版。

List 接口

接口特点

• 有序
• 可反复
• 反对应用索引取出，索引从 0 开始。

List 的三种循环形式

List 的三种循环形式：
• 迭代器模式
• 加强 for 循环
• 一般 for 循环

Collection 的两种循环形式

List 实现 Collection 接口，间接实现 Iterable 接口，天然能够应用 Collection 的两种循环形式。

一般 for 循环

因为 List 的实现类外部都能够用索引，所以能够应用一般 for 循环。

         List<Integer> list = new ArrayList<>();        for (int i = 0; i < 10; i++) {            list.add(i);        }        // 一般 for 循环        for (int i = 0; i < list.size(); i++) {            // 通过索引取值            System.out.println(list.get(i));        }

ArrayList

ArrayList 的特点

  • 能够寄存 null 值。
  • 能够寄存反复值。
  • 线程不平安，在多线程环境下不举荐应用。它和 Vector 相似，但 Vector 是线程平安的。

ArrayList 的扩容机制

ArrayList 外部存放数据的是一个 Object 数组。

从 ArrayList 的构造方法说起：

  • 无参结构：默认容量是 0（一个定义好的空 Object 数组），应用 add 办法后，容量为 10，当容量有余时，扩充容量为原来的 1.5 倍。
  • 指定容量的构造函数：容量为指定的容量，容量有余时，间接扩充为原来的 1.5 倍左右（偶数是 1.5 倍，奇数是 1.5 倍左右）。

源码剖析（Java 11）

    // 外部存储数据的是一个 Object 数组    transient Object[] elementData;    // 无参结构    public ArrayList() {        // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组：private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};        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);        }    }    // 扩容    private void add(E e, Object[] elementData, int s) {        if (s == elementData.length)            // 触发扩容，数组不够用时扩容            elementData = grow();        elementData[s] = e;        size = s + 1;    }    private static final int DEFAULT_CAPACITY = 10;    // 真正拿到扩容后容量的办法    private int newCapacity(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        // >> 相当于 / 2，所以理论扩容时 1.5 倍左右。        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity <= 0) {            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)                // 第一次调用 add 实际上取得的新容量是 DEFAULT_CAPACITY = 10                return Math.max(DEFAULT_CAPACITY, minCapacity);            if (minCapacity < 0) // overflow                throw new OutOfMemoryError();            return minCapacity;        }        return (newCapacity - MAX_ARRAY_SIZE <= 0)            ? newCapacity            : hugeCapacity(minCapacity);    }

总结

ArrayList 特点：

  • ArrayList 底层数据结构是数组。
  • 能够存储 null 值。
  • 是线程不平安的。

ArrayList 的扩容机制：

  • 应用无参结构，默认容量为 0，第一次 add，会将容量扩为 10。当容量再有余时，会扩容为原来的 1.5 倍左右。

  • 应用指定容量的构造方法，容量为指定容量，当容量有余时，会扩容为原来的 1.5 倍左右。
    （为什么是 1.5 倍左右：因为数组容量是整数，在右移时，如果是奇数，就不是 1.5 倍，而是 1.5 倍左右了。）

    Vector

    Vector 特点

  • 能够存储 null
  • 线程同步 synchronized （是线程平安的）,每个办法都同步，效率低于 ArrayList

Vector 源码剖析（Java 11）

Vector 底层数据结构是一个 Object 数组。

 protected Object[] elementData;

还是来看构造方法：

  • 无参构造方法：默认容量是 10。扩容减少为原来的 2 倍。
  • 指定容量的构造方法：容量为指定容量。扩容减少为原来的 2 倍。
    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;    }

扩容机制：
最外围的代码如下：

        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                                         capacityIncrement : oldCapacity);

capacityIncrement 是Vector 的属性，不指定值时为 0。所以下面的代码能够被了解为：

        int oldCapacity = elementData.length;        // 扩容为原来的 2 倍        int newCapacity = oldCapacity + oldCapacity;

总结

Vector 特点：

  • 底层构造是 Object 数组。
  • 能够存储 null。
  • 是线程同步的，线程平安。

扩容机制：在应用无参结构后，容量为 10。当容量有余时，会扩容为原来的 2 倍。

LinkedList

LinkedList 特点

  • 底层是双向链接，增加和删除操作快。查问会效率低些（源码中做了优化，索引<长度一半 从头开始遍历，索引>=长度一半 从开端开始遍历）
  • 非线程平安

LinkedList 源码剖析（Java 11）

它的底层是双向链接，有一个头节点 first 指向链表第一个节点，有一个尾节点 last 指向链表最初一个节点。size 变量用来保护链表的长度

    transient int size = 0;    transient Node<E> first;    transient Node<E> last;
构造方法

无参结构：

    public LinkedList() {    }

是一个空办法体，实际上就是将 first、last 设为 null，size = 0。

减少

减少的逻辑理论是在 linkLast 这个办法中：

    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);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;        size++;        modCount++;    }

新增的图解示意：

删除

remove 实际上是删除链表第一个元素，理论的删除逻辑在办法 unlinkFirst 中

    public E remove() {        return removeFirst();    }    public E removeFirst() {        final Node<E> f = first;        if (f == null)            throw new NoSuchElementException();        return unlinkFirst(f);    }    private E unlinkFirst(Node<E> f) {        // assert f == first && f != null;        final E element = f.item;        final Node<E> next = f.next;        f.item = null;        f.next = null; // help GC        first = next;        if (next == null)            last = null;        else            next.prev = null;        size--;        modCount++;        return element;    }

删除的图解示意：

批改和查问

批改和查问放到一起是因为，批改其实就是先查问后批改，所以实际上次要的逻辑都在查问。查问实际上调用的办法是 node：

    Node<E> node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            // index 小于长度的一半时，应用头节点向后遍历查找数据            Node<E> x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            // index 大于等于长度的一半时，应用尾节点向前遍历查找数据            Node<E> x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }

ArrayList 和 LinkedList 的比照与应用场景

在单线程的前提下：

  • ArrayList 适宜查问多、增删少的情景。（业务场景大部分都是查问，所以应用 ArrayList 场景十分多）

  • LinkedList 适宜增删多、查问少的状况。

    总结

    LinkedList 底层数据结构是双向链表。
    新增和删除效率高，随机拜访效率低于 ArrayList。

    Set

    Set 接口的特点

  • 无序
  • 能够寄存 null 值
  • 不会寄存反复元素
        Set set = new HashSet();        set.add(null);        set.add("tom");        set.add("amy");        set.add("jerry");        set.add("amy");        // [null, tom, jerry, amy]        System.out.println(set);

Set 遍历

Set 继承 Collection，天然能够应用 Collection 的两种遍历形式：

        // 遍历形式        // Collection 的两种形式        Iterator iterator = set.iterator();        while (iterator.hasNext()) {            Object o =  iterator.next();            System.out.println("o = " + o);        }        System.out.println();        for (Object o : set) {            System.out.println("o = " + o);        }

总结

Set 接口的特点：无序、不反复、能够寄存 null（因为不反复所以只能放一个 null）

Set 遍历的两种形式：就是 Collection 的两种遍历形式（因为继承 Collection 接口），不能应用索引遍历（List 独有特点）

HashSet

HashSet 特点

HashSet 底层是应用 hashMap，是数组加链表的模式。

在新增时，会先用 key 的 hash 值来找到数组的索引。如果曾经有元素，那么须要判断是否相等，如果相等就不增加。如果相等，就在原来的元素前面追加新的元素。造成链表。当链表长度 >= 8 并且数组长度大于 64（默认值） 时，会树化。

HashSet 源码剖析（Java 8）

构造方法
    public HashSet() {        map = new HashMap<>();    }

能够看到构造方法其实是初始化一个 HashMap。

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

能够看到理论是 map（HashMap 对象） 调用 put 办法，value 是 PRESENT，而 PRESENT 是一个动态的、final Object 对象：

    private static final Object PRESENT = new Object();

所以实际上咱们须要看的是 HashMap 的 put 办法的实现：

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

首先会先对 key 进行 hash 计算，看一下 hash 计算是如何计算：

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

hash 计算形式：key 的 hashCode ^ key 的 hashCode 向右移位 16 位。（向右移位不容易让各个位为 0，更不便）

接下来就会调用 putVal：

    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 是一个 Node<K,V> 数组， n 也就是 数组长度        if ((tab = table) == null || (n = tab.length) == 0)            // 第一次会进入 resize() 办法，tab = 长度为 16 的数组            n = (tab = resize()).length;        // i = (n - 1) & hash，找到 key 对应的数组索引，赋值给 i, p 指向 table[i] 数组元素        if ((p = tab[i = (n - 1) & hash]) == null)            // 索引对应的元素为 null，阐明没节点，间接增加            tab[i] = newNode(hash, key, value, null);        else {            Node<K,V> e; K k;            // 尽管没有 if 中的内容，然而在判断时就执行 if 的条件，所以 p 在这处 指向 table[i] 数组元素            // p.hash == hash && ((k = p.key) == key，判断 key 和目前在这里的 key 否是同一个 key            // key != null && key.equals(k), 判断 key 和目前这里的 key 是否雷同            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                // 满足两者中其一的条件， e = p = table[i]                e = p;            else if (p instanceof TreeNode)                // 如果 p 是树节点，则采纳树的增加办法 putTreeVal                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);            else {                // p 不和数组key完全相同，并且是链表，通过遍历这个链表确认，新退出的元素(HashMap$Node)和链表中原来的元素不雷同,如果有雷同项会提前退出循环，没有则加新退出的追加到链表开端，并且追加后立刻判断链表长度是否 >= 8, 满足条件时会调用 treeifyBin 办法确认是否须要树化。当 table 长度 >= 64 时，会将链表转为树。                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        // TREEIFY_THRESHOLD 8                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        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)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        // 当 table 数组长度大于 threshold（容量 * 负载因子（0.75），就会触发扩容）        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }

其中在第一次增加元素时，会调用 resize() 办法，将 table 初始化为长度 16 的数组：

final Node<K,V>[] resize() {        Node<K,V>[] oldTab = table;        // oldCap 原来容量 = 0        int oldCap = (oldTab == null) ? 0 : oldTab.length;        // 不便查看，省略代码         else {               // zero initial threshold signifies using defaults            // 会进入这个 if-else 分支，DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16            // newThr = 16            newCap = DEFAULT_INITIAL_CAPACITY;            // DEFAULT_LOAD_FACTOR = 0.75，newThr = 12            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        //  threshold = newThr = 12        threshold = newThr;        // 初始化 table 数组，长度为 16        @SuppressWarnings({"rawtypes","unchecked"})        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];        table = newTab;        // 原来数组内容拷贝到新数组        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                // 不便查看，省略代码            }        }        return newTab;    }

treeifyBin 办法，要进行树化前会先判断 table 长度：

    final void treeifyBin(Node<K,V>[] tab, int hash) {        int n, index; Node<K,V> e;        // MIN_TREEIFY_CAPACITY = 64        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)            // table 有余 64 时会先扩容            resize();        else if ((e = tab[index = (n - 1) & hash]) != null) {            TreeNode<K,V> hd = null, tl = null;            do {                TreeNode<K,V> p = replacementTreeNode(e, null);                if (tl == null)                    hd = p;                else {                    p.prev = tl;                    tl.next = p;                }                tl = p;            } while ((e = e.next) != null);            if ((tab[index] = hd) != null)                hd.treeify(tab);        }    }

从新看下 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;            }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                // newCap 为原来两倍                // newThr 也为原来两倍                newThr = oldThr << 1; // double threshold        }        // 省略代码 ....        threshold = newThr;        // 创立新数组，并将旧数组内容拷贝到新数组，实现扩容        @SuppressWarnings({"rawtypes","unchecked"})        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];        table = newTab;        if (oldTab != null) {            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 { // preserve order                        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;                            }                            else {                                if (hiTail == null)                                    hiHead = e;                                else                                    hiTail.next = e;                                hiTail = e;                            }                        } while ((e = next) != null);                        if (loTail != null) {                            loTail.next = null;                            newTab[j] = loHead;                        }                        if (hiTail != null) {                            hiTail.next = null;                            newTab[j + oldCap] = hiHead;                        }                    }                }            }        }        return newTab;    }

总结

hashSet，底层实现是 hashMap，每次新增对象，就是往 hashMap 中放 key = 新增对象，value = 定义好的动态不变对象。

在新增元素时，会先依据 key 的 hash 值来找到数组索引，找到数组索引对应的那条链表，如果为 null 间接增加元素，如果不为 null 须要判断新增元素 key 和以前的是否是同一个对象或者完全相同。如果雷同，则不增加，否则将元素追加到这条链表的开端。

当一条链表长度 >=8 并且数组长度大于 64 时，会将这个链表转为红黑树。

触发扩容：第一次新增元素，会初始化 table 数组，容量会变为 16，临界值变为 12（16 * 0.75）。在整个 hashMap 中元素个数大于临界值时会进行扩容，每次扩容为原来的 2 倍。

LinkedHashSet

特点

继承 HashSet，有序不反复。

源码剖析 (Java 11)

底层应用的 LinkedHashMap，他的底层数据结构是 哈希表 + 双向链表。

每次创立新节点时，会保护这个双向链表：

    // 创立新节点的办法   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {        LinkedHashMap.Entry<K,V> p =            new LinkedHashMap.Entry<>(hash, key, value, e);        linkNodeLast(p);        return p;    }

LinkedHashMap.Entry 是这里的节点类，它继承于 HashMap 的外部类 Node，然而每个节点领有前后指针（before、after）。

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

在 newNode 中调用 linkNodeLast 来保护每个节点组成的双向链表：

    // 双向链表头节点    transient LinkedHashMap.Entry<K,V> head;    // 双向链表尾节点    transient LinkedHashMap.Entry<K,V> tail;   private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {        LinkedHashMap.Entry<K,V> last = tail;        tail = p;        if (last == null)            head = p;        else {            p.before = last;            last.after = p;        }    }

head 和 tail 别离指向头节点和尾节点，看代码能够看出这就是将节点增加到链表的操作。

总结

LinkedHashSet 继承 HashSet 实现 Set。它和 HashSet 的区别是它是有序不反复汇合。

底层应用的 LinkedHashMap，它的实现是哈希表 + 双向链表。通过双向链表来维持程序。

TreeSet

特点

  • 不能存 null。
  • 默认是依照 key 的类型的升序排序，如果须要其余排序规定，能够通过结构器传入 Comparator。
  • 传入 Comparator 时，只有他的办法 compareTo 返回 0，则新的值会被旧的值代替。

源码剖析（Java 11）

TreeSet 的底层实际上是应用的 TreeMap。它和 HashSet 的区别就在于，在批改汇合（增删）时，会依据 key 值排序。能够通过结构器传入 Comparator，传入 Comparator 时，只有compareTo 返回 0，新的值会被旧的值代替。

    public boolean add(E e) {        return m.put(e, PRESENT)==null;    }    public V put(K key, V value) {        Entry<K,V> t = root;        if (t == null) {            // 第一个节点时,compare 的作用只是为了检测 null 值            compare(key, key); // type (and possibly null) check            root = new Entry<>(key, value, null);            size = 1;            modCount++;            return null;        }        int cmp;        Entry<K,V> parent;        // split comparator and comparable paths        Comparator<? super K> cpr = comparator;        if (cpr != null) {            // 应用构造方法传入的结构器比拟            do {                parent = t;                cmp = cpr.compare(key, t.key);                if (cmp < 0)                    t = t.left;                else if (cmp > 0)                    t = t.right;                else                    // key 在对应的比拟规定下，如果雷同，会被批改。                    return t.setValue(value);            } while (t != null);        }        else {            // 应用 key 类型的结构器比拟            if (key == null)                // key 不能为 null，会报错                throw new NullPointerException();            @SuppressWarnings("unchecked")                Comparable<? super K> k = (Comparable<? super K>) key;            do {                parent = t;                cmp = k.compareTo(t.key);                if (cmp < 0)                    t = t.left;                else if (cmp > 0)                    t = t.right;                else                    return t.setValue(value);            } while (t != null);        }        Entry<K,V> e = new Entry<>(key, value, parent);        if (cmp < 0)            parent.left = e;        else            parent.right = e;        fixAfterInsertion(e);        size++;        modCount++;        return null;    }

总结

  • TreeSet 底层应用的是 TreeMap。
  • TreeSet 不能存 null。
  • 在批改汇合（增删）时，会依据 key 值排序。能够通过结构器传入 Comparator，传入 Comparator 时，只有compareTo 返回 0，新的值会被旧的值代替。

双列汇合

Map

特点

  • 双列汇合
  • 存储 k-v 键值对
  • key 不能反复

Map 遍历的 2 类 6 种形式

遍历 key-value：

  • 用 keySet 办法遍历（迭代器 + 加强 for 循环）
  • 用 entrySet 办法遍历（迭代器 + 加强 for 循环）

遍历 value：

  • 用 values 办法遍历（数组）
import java.util.*;public class MapFor {    public static void main(String[] args) {        Map<String, String> hashMap = new HashMap<>();        hashMap.put("zhangsan", "aaa");        hashMap.put("lisi", "bbb");        // 遍历 key-value        // 加强 for 循环        System.out.println("加强 for 循环");        Set<String> keySet = hashMap.keySet();        for (String key : keySet) {            System.out.println(key + "-" + hashMap.get(key));        }        // 迭代器        System.out.println("迭代器");        Iterator<String> iterator = keySet.iterator();        while (iterator.hasNext()) {            String key = iterator.next();            System.out.println(key + "-" + hashMap.get(key));        }        // entry        System.out.println("entry 加强 for 循环");        Set<Map.Entry<String, String>> entrySet = hashMap.entrySet();        for (Map.Entry<String, String> entry : entrySet) {            System.out.println(entry.getKey() + "-" + entry.getValue());        }        System.out.println("entry 迭代器");        Iterator<Map.Entry<String, String>> entryIterator = entrySet.iterator();        while (entryIterator.hasNext()) {            Map.Entry<String, String> entry = entryIterator.next();            System.out.println(entry.getKey() + "-" + entry.getValue());        }        // 遍历 value        // 加强 for 循环        Collection<String> values = hashMap.values();        for (String value : values) {            System.out.println(value);        }        Iterator<String> valueIterators = values.iterator();        while (valueIterators.hasNext()) {            String value = valueIterators.next();            System.out.println(value);        }    }}

HashMap

HashMap 特点

  • 寄存 key-value，key 是惟一的，雷同的 key 值，value 会笼罩上一次寄存的 value。
  • key 和 value 都能够为 null，然而一个 HashMap 只能有一个 null。不同的 key 能够有多个 null。
  • HashMap 设计者为了不便程序员遍历，将每个 k-v （HashMap$Node）放入 entrySet，外面寄存的类型是 Map$Entry 类型。Map$Entry 有 getKey、getValue 办法，不便遍历。
  • 非线程平安

源码剖析

能够看 HashSet 的源码剖析，HashSet 的源码剖析实际上就是再将 HashMap。

HashTable

特点

  • 存储 k-v
  • key 和 value 都不能够为 null

  • 线程平安

    HashTable 源码剖析

    底层是数组加链表。数组是：HashTable$Entry 数组。链表节点是 HashTable$Entry。

构造方法
    public Hashtable() {        this(11, 0.75f);    }    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。阈值 = 11 * 0.75 约等于 8

减少
    public synchronized V put(K key, V value) {        // Make sure the value is not null        if (value == null) {            throw new NullPointerException();        }        // Makes sure the key is not already in the hashtable.        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;    }

通过 (整数最大值 & key 的 hash) % 数组长度 获取下标

次要的减少逻辑在这个办法 addEntry 上：

      private void addEntry(int hash, K key, V value, int index) {        Entry<?,?> tab[] = table;        if (count >= threshold) {            // 元素数量大于阈值，会应用 rehash() 扩容            // Rehash the table if the threshold is exceeded            rehash();            tab = table;            hash = key.hashCode();            index = (hash & 0x7FFFFFFF) % tab.length;        }        // Creates the new entry.        @SuppressWarnings("unchecked")        Entry<K,V> e = (Entry<K,V>) tab[index];        tab[index] = new Entry<>(hash, key, value, e);        count++;        modCount++;    }
扩容机制

 rehash 办法

        int newCapacity = (oldCapacity << 1) + 1;

能够看到扩容为 2n + 1 倍。

总结

HashTable 和 HashMap 的区别：

 HashMapHashTable
k-v 能够为 null是否
底层数据结构jdk7：数组+链表
jdk8：数组+链表+红黑树		数组+链表
默认容量1611
加载因子0.750.75
扩容机制2n2n + 1
线程平安否是
找索引形式hash & (n - 1)(hash & 0x7FFFFFFF) % tab.length
阈值（触发扩容）>=12>=8
树化jdk8，table长度>=64，链表长度>=8无树化操作

LinkedHashMap

特点

  • 存储 k-v
  • 底层为 hash表 和双向链表

  • key 能够为 null

    源码剖析（Java 11）

    LinkedHashSet 底层就是用的 LinkedHashMap,间接看 LinkedHashSet 源码剖析就能够。

TreeMap

特点

  • 存 k-v
  • key 不能为 null，值能够为 null。
  • 默认是依照 key 的类型的升序排序，如果须要其余排序规定，能够通过结构器传入 Comparator。
  • 传入 Comparator 时，只有他的办法 compareTo 返回 0，则新的值会被旧的值代替

源码剖析（Java 11）

TreeSet 底层应用的就是 TreeMap，能够间接看 TreeSet 的源码剖析。

总结

汇合分为单列汇合和双列汇合。

单列汇合父接口：Collection。

双列汇合父接口：Map。

依照汇合体系图从上往下特点是会继承过去的，同级的能够比照记忆（比方 HashMap 和 HashTable）。