关于java:Java集合知识点总结和重点源码分析

汇合体系图

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

单列汇合体系图（罕用）

双列汇合体系图（罕用）

单列汇合

Collection

Collection 接口特点

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

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

  Collection 接口遍历形式

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

  形式一：应用 Iterator 接口

  迭代器的执行原理：

迭代器罕用办法：

// 判断这次迭代是否还有下一个元素
boolean hasNext();

// 返回迭代的下一个元素（指针挪动到下一个元素，返回上一个元素），如果没有下一个元素，会报异样 NoSuchElementException
E next();

// 删除迭代器的这个元素，必须先调用 next()，才能够调用 remove()，否则会抛出异样 IllegalStateException
remove()

迭代器应用示例：

       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 的区别：

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）。