12.1 Java集合框架概述

集合、数组都是对多个数据进行存储操作的结构，简称Java容器。
一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊端，而Java集合就像一种容器，可以动态地把多个对象的引用放入容器中。
说明：此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储。
数组在内存存储方面的特点：
- 数组初始化以后，长度就确定了。
- 数组声明的类型，就决定了进行元素初始化时的类型。
数组在存储数据方面的弊端：
- 数组初始化以后，长度就不可变了，不便于扩展。
- 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数。
- 数组存储的数据是有序的、可以重复的。存储数据的特点单一。
Java集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的关联数组。

图片说明

Java集合可分为Collection和Map两种体系：
- Collection接口：单列数据，定义了存取一组对象的方法的集合。
  - List：元素有序、可重复的集合。
    - ArrayList、LinkedList、Vector
  - Set：元素无序、不可重复的集合。
    - HashSet、LinkedHashSet、TreeSet
- Map接口：双列数据，保存具有映射关系“key-value”对的集合。
  - HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

12.2 Collection接口方法

    package java.util;

    import java.util.function.IntFunction;
    import java.util.function.Predicate;
    import java.util.stream.Stream;
    import java.util.stream.StreamSupport;

    public interface Collection<E> extends Iterable<E> {
            // Query Operations    
        int size();
        boolean isEmpty();   
        boolean contains(Object o);
        Iterator<E> iterator();
        Object[] toArray();
        <T> T[] toArray(T[] a);
        default <T> T[] toArray(IntFunction<T[]> generator) {
            return toArray(generator.apply(0));
        }

            // Modification Operations
        boolean add(E e);
        boolean remove(Object o);

            // Bulk Operations
        boolean containsAll(Collection<?> c);
        boolean addAll(Collection<? extends E> c);
        boolean removeAll(Collection<?> c);
        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;
        }
        boolean retainAll(Collection<?> c);
        void clear();

        // Comparison and hashing
        boolean equals(Object o);
        int hashCode();
        @Override
        default Spliterator<E> spliterator() {
            return Spliterators.spliterator(this, 0);
        }
        default Stream<E> stream() {
            return StreamSupport.stream(spliterator(), false);
        }
        default Stream<E> parallelStream() {
            return StreamSupport.stream(spliterator(), true);
        }
    }

boolean add(E e)：将元素e添加到集合中。
int size()：获取添加的元素的个数。
boolean addAll(Collection<? extends E> c)：将集合c中的元素添加到当前集合中。
void clear()：清空集合中的元素。
boolean isEmpty()：判断当前集合是否为空。
boolean contains(Object obj)：判断当前集合中是否包含obj（通过equals()方法进行判断）。
boolean containsAll(Collection<?> c)：判断集合c中的所有元素是否都存在与当前集合中（通过equals()方法进行判断）。
boolean remove(Object o)：从当前集合中移除o元素（通过equals()方法进行判断）。
boolean removeAll(Collection<?> c)：差集，从当前集合中移除集合c中所有的元素（通过equals()方法进行判断）。
boolean retainAll(Collection<?> c)：交集，获取当前集合与集合c的交集，并返回给当前集合。
boolean equals(Object o)：判断当前集合与形参集合是否相同。
int hashCode()：返回当前对象的哈希值。
default <t> T[] toArray(IntFunction<T[]> generator)：集合 —> 数组。</t>
- （扩展）数组 —> 集合：调用Arrays类的静态方法asList()。

Iterator<e> iterator()：返回Iterator接口的实例，用于遍历集合元素。</e>

import org.junit.jupiter.api.Test;

import java.util.*;

public class CollectionTest {
    /**
     * Collection接口方法：
     *      向Collection中添加的对象必须重写equals()方法。
     */
    @Test
    public void test() {
        Collection collection = new ArrayList();
        // boolean add(E e)：将元素e添加到集合中。
        String str = "AA";
        collection.add(str);
        collection.add("BB");
        collection.add(123);
        collection.add(new Date());

        // int size()：获取添加的元素的个数。
        System.out.println(collection.size());  // 4
        System.out.println("*********************");

        // boolean addAll(Collection<? extends E> c)：将集合c中的元素添加到当前集合中
        Collection collection1 = new ArrayList();
        collection1.add(456);
        collection1.add("CC");
        collection.addAll(collection1);
        System.out.println(collection.size());   // 6
        System.out.println(collection);     //[AA, BB, 123, Tue Feb 25 14:34:00 CST 2020, 456, CC]
        System.out.println("**************************");

        // boolean contains(Object obj)：判断当前集合中是否包含obj（通过equals()方法进行判断）
        System.out.println(collection.contains("AA"));  // true
        System.out.println(collection.contains(str));  // true
        System.out.println(collection.contains(new String("AA")));  // true
        System.out.println("*************************");

        // boolean containsAll(Collection<?> c)：判断集合c中的所有元素是否都存在与当前集合中（通过equals()方法进行判断）。
        System.out.println(collection.containsAll(collection1));    // true
        System.out.println("*****************************");

        // boolean remove(Object o)：从当前集合中移除o元素（通过equals()方法进行判断）。
        boolean remove = collection.remove(123);
        System.out.println(remove);     // true
        System.out.println(collection); // [AA, BB, Tue Feb 25 16:05:14 CST 2020, 456, CC]
        System.out.println("************************");

        // boolean removeAll(Collection<?> c)：从当前集合中移除集合c中的所有元素（通过equals()方法进行判断）
        Collection collection2 = Arrays.asList(123,456);
        collection.removeAll(collection2);
        System.out.println(collection);     // [AA, BB, Tue Feb 25 16:08:31 CST 2020, CC]
        System.out.println("*********************");

        // boolean retainAll(Collection<?> c)：交集，获取当前集合与集合c的交集，并返回给当前集合。
        Collection collection3 = Arrays.asList("AA", "BB", "CC", "DD");
        collection.retainAll(collection3);
        System.out.println(collection);     // [AA, BB, CC]
        System.out.println("*******************");

        // boolean equals(Object o)：判断当前集合与形参集合是否相同。
        Collection collection4 = Arrays.asList("AA", "BB", "CC");
        System.out.println(collection.equals(collection4));     // true
        Collection collection5 = Arrays.asList("AA", "CC", "BB");
        System.out.println(collection.equals(collection5));     // false
        System.out.println("********************");

        // int hashCode()：返回当前对象的哈希值。
        System.out.println(collection.hashCode());      // 2096287
        System.out.println("**************************");

        // default <T> T[] toArray(IntFunction<T[]> generator)：集合 ---> 数组。
        Object[] objects = collection.toArray();
        System.out.println(Arrays.toString(objects));   // [AA, BB, CC]
        System.out.println("****************");

        // 扩展：数组 ---> 集合：调用Arrays类的静态方法asList()。
        List<String> list = Arrays.asList(new String[]{"A", "B"});
        System.out.println(list);   // [A, B]
        System.out.println("*********************");

        // Iterator<E> iterator()：返回Iterator接口的实例，用于遍历集合元素。
        Iterator iterator = collection.iterator();

        // void clear()：清空集合中的元素
        collection.clear();

        // boolean isEmpty()：判断当前集合是否为空。
        System.out.println(collection.isEmpty());   // true
    }
}

注意：向Collection中添加的对象的类必须重写equals()方法。

12.3 Iterator迭代器接口

    package java.util;

    import java.util.function.Consumer;

    public interface Iterator<E> {

        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }
    }

Iterator对象称为迭代器（设计模式的一种），主要用于遍历Collection集合中的元素。
GOF给迭代器模式的定义为：提供一种方法访问一个容器（Container）对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。

package java.lang;

import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;

public interface Iterable<T> {

    Iterator<T> iterator();

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

}

Iterator仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象，则必须有一个被迭代的集合。
集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
Iterator内部定义了remove()，可以在遍历的时候，删除集合中的元素。此方法不同于集合中的remove()方法。

如果还未调用next()或在上一次调用next()方法之后已经调用了remove()方法，再调用remove()都会报java.lang.IllegalStateException异常。

import org.junit.jupiter.api.Test;

import java.util.*;

public class CollectionTest {
    @Test
    public void test() {
        Collection collection = new ArrayList();
        collection.add(1);
        collection.add(2);
        collection.add(3);
        collection.add(4);
        collection.add(5);
        Iterator iterator = collection.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());    // 1 2 3 4 5
            iterator.remove();
        }
        System.out.println(collection);     // []
    }
}

扩展：增强for循环（foreach）

JDK5.0新增了foreach循环，用于遍历集合、数组。

import org.junit.jupiter.api.Test;

import java.util.*;

public class CollectionTest {
    @Test
    public void test() {
        Collection collection = new ArrayList();
        collection.add(1);
        collection.add(2);
        collection.add(3);
        collection.add(4);
        collection.add(5);
        for (Object item : collection) {
            System.out.println(item);
        }
        int[] arr = new int[]{6, 7, 8, 9, 10};
        for (int item : arr) {
            System.out.println(item);   // 6 7 8 9 10
        }
    }
}

练习题

import org.junit.jupiter.api.Test;

import java.util.*;

public class CollectionTest {
    @Test
    public void test() {
        String[] arr = new String[]{"A","A","A"};
        for (String item : arr) {
            item = "B";
        }
        for (String item : arr) {
            System.out.println(item);   // A A A
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "B";
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]); // B B B
        }
    }
}

12.4 Collection子接口：List

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组。
List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
JDK API中List接口（JDK1.2）的实现类常用的有：
- ArrayList（JDK1.2）：List接口的主要实现类；线程不安全，效率高；底层使用Object[] elementData存储。
- LinkedList（JDK1.2）：底层使用双向链表存储；对于频繁的插入、删除操作，使用此类效率比ArrayList效率高。
- Vector（JDK1.0）：List接口的古老实现类，线程安全，效率低；底层使用Object[] elementData存储。

1、ArrayList、LinkedList、Vector三者的异同？

同：都实现了List接口。存储数据的特点相同：存储有序的、可重复的数据。
不同：
- ArrayList（JDK1.2）：List接口的主要实现类；线程不安全，效率高；底层使用Object[] elementData存储。
- LinkedList（JDK1.2）：底层使用双向链表存储；对于频繁的插入、删除操作，使用此类效率比ArrayList效率高。
- Vector（JDK1.0）：List接口的古老实现类，线程安全，效率低；底层使用Object[] elementData存储。

2、ArrayList源码分析（部分）

图片说明

    package java.util;

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        private static final long serialVersionUID = 8683452581122892189L;  // 序列化ID

        private static final int DEFAULT_CAPACITY = 10; // 默认初始化容量

        private static final Object[] EMPTY_ELEMENTDATA = {};   // 空对象共享的数组

        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};   // 默认容量的对象共享的数组

        transient Object[] elementData; // 存放元素的数组

        private int size;   // 元素个数

        // 构造器
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
            }
        }
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // defend against c.toArray (incorrectly) not returning Object[]
                // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

        /**
         * 缩容
         */
        public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

        /**
         * 扩容
         */
        public void ensureCapacity(int minCapacity) {
            if (minCapacity > elementData.length
                && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                     && minCapacity <= DEFAULT_CAPACITY)) {
                modCount++;
                grow(minCapacity);
            }
        }

        /**
         * 最大容量
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

        /**
         * 扩容
         */
        private Object[] grow(int minCapacity) {
            return elementData = Arrays.copyOf(elementData,
                                               newCapacity(minCapacity));
        }
        private Object[] grow() {
            return grow(size + 1);
        }

        /**
         * 添加数据
         */
        private void add(E e, Object[] elementData, int s) {
            if (s == elementData.length)
                elementData = grow();
            elementData[s] = e;
            size = s + 1;
        }
        public boolean add(E e) {
            modCount++;
            add(e, elementData, size);
            return true;
        }
        public void add(int index, E element) {
            rangeCheckForAdd(index);
            modCount++;
            final int s;
            Object[] elementData;
            if ((s = size) == (elementData = this.elementData).length)
                elementData = grow();
            System.arraycopy(elementData, index,
                             elementData, index + 1,
                             s - index);
            elementData[index] = element;
            size = s + 1;
        }

        /**
         * 移除数据
         */
        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;
        }
        public boolean remove(Object o) {
            final Object[] es = elementData;
            final int size = this.size;
            int i = 0;
            found: {
                if (o == null) {
                    for (; i < size; i++)
                        if (es[i] == null)
                            break found;
                } else {
                    for (; i < size; i++)
                        if (o.equals(es[i]))
                            break found;
                }
                return false;
            }
            fastRemove(es, i);
            return true;
        }

        public void clear() {
            modCount++;
            final Object[] es = elementData;
            for (int to = size, i = size = 0; i < to; i++)
                es[i] = null;
        }     
        /**
         * 迭代器
         */
        public ListIterator<E> listIterator(int index) {
            rangeCheckForAdd(index);
            return new ListItr(index);
        }

        public ListIterator<E> listIterator() {
            return new ListItr(0);
        }

        public Iterator<E> iterator() {
            return new Itr();
        }

        /**
         * An optimized version of AbstractList.Itr 迭代器的底层实现一
         */
        private class Itr implements Iterator<E> {
            int cursor;       // index of next element to return
            int lastRet = -1; // index of last element returned; -1 if no such
            int expectedModCount = modCount;

            // prevent creating a synthetic constructor
            Itr() {}

            public boolean hasNext() {
                return cursor != size;
            }

            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }

            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    ArrayList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                final int size = ArrayList.this.size;
                int i = cursor;
                if (i < size) {
                    final Object[] es = elementData;
                    if (i >= es.length)
                        throw new ConcurrentModificationException();
                    for (; i < size && modCount == expectedModCount; i++)
                        action.accept(elementAt(es, i));
                    // update once at end to reduce heap write traffic
                    cursor = i;
                    lastRet = i - 1;
                    checkForComodification();
                }
            }

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

        /**
         * An optimized version of AbstractList.ListItr 迭代器的底层实现二
         */
        private class ListItr extends Itr implements ListIterator<E> {
            ListItr(int index) {
                super();
                cursor = index;
            }

            public boolean hasPrevious() {
                return cursor != 0;
            }

            public int nextIndex() {
                return cursor;
            }

            public int previousIndex() {
                return cursor - 1;
            }

            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[lastRet = i];
            }

            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    ArrayList.this.set(lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void add(E e) {
                checkForComodification();
                try {
                    int i = cursor;
                    ArrayList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    }

3、LinkedList源码分析（部分）

图片说明

    package java.util;

    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        transient int size = 0;     // 元素数量
        transient Node<E> first;    // 头结点
        transient Node<E> last;     // 尾节点
        public LinkedList() {       // 无参构造器，默认初始化size=0，first=null，last=null
        }
        // 其他构造器
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
        // 添加元素
        private void linkFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
        // 获取元素
        public E getFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
        // 移除元素
        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }

        // 清除元素
        public void clear() {
            // Clearing all of the links between nodes is "unnecessary", but:
            // - helps a generational GC if the discarded nodes inhabit
            //   more than one generation
            // - is sure to free memory even if there is a reachable Iterator
            for (Node<E> x = first; x != null; ) {
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            first = last = null;
            size = 0;
            modCount++;
        }
        // 双向链表底层实现
        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;
            }
        }
    }

4、Vector源码分析（部分）

图片说明

    package java.util;
    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
            protected Object[] elementData;
            public Vector(int initialCapacity) {
            this(initialCapacity, 0);
        }
            public synchronized void addElement(E obj) {
            modCount++;
            add(obj, elementData, elementCount);
        }
            private void add(E e, Object[] elementData, int s) {
            if (s == elementData.length)
                elementData = grow();
            elementData[s] = e;
            elementCount = s + 1;
        }
            private Object[] grow() {
            return grow(elementCount + 1);
        }
            private Object[] grow(int minCapacity) {
            return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
        }

5、List接口方法

List除了从Collection集合继承的方法外，List集合里添加了一些根据索引来操作集合元素的方法。
void add(int index, Object ele)：在index位置插入ele元素。
boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来。
Object get(int index)：获取指定index位置的元素。
int indexOf(object obj)：返回obj在集合中首次出现的位置。
int lastIndexOf(Object obj）：返回obj在当前集合中末次出现的位置。
Object remove(int index)：移除指定index位置的元素，并返回此元素。
Object set(int index, Object ele)：设置指定index位置的元素为ele。

List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合。

import org.junit.jupiter.api.Test;

import java.util.*;

public class ListTest {
    @Test
    public void test() {
        ArrayList list = new ArrayList();
        list.add(123);
        list.add(456);
        list.add("AA");
        list.add(new Date());
        list.add(456);
        System.out.println(list);

        list.add(1, "BB");
        System.out.println(list);

        List<Integer> integers = Arrays.asList(1, 2, 3);
        list.addAll(integers);
        System.out.println(list);

        System.out.println(list.get(0));

        System.out.println(list.indexOf(456));

        System.out.println(list.lastIndexOf(456));

        Object remove = list.remove(1);
        System.out.println(remove);
        System.out.println(list);

        list.set(0, "CC");
        System.out.println(list);

        List list1 = list.subList(1, 4);
        System.out.println(list1);
        System.out.println(list);

        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

        for (Object item : list) {
            System.out.print(item + " ");
        }
        System.out.println();

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

    }

}

总结（常用方法）：
- 增：add(Object obj)
- 删：remove(Object obj)、remove(int index)
- 改：set(int index, Object obj)
- 查：get(int index)
- 插：add(int index, Object obj)
- 长度：size()
- 遍历：iterator()、增强for循环、for循环

6、练习

    import org.junit.jupiter.api.Test;

    import java.util.*;

    public class ListTest {
        @Test
        public void test() {
            ArrayList list = new ArrayList();
            list.add(1);
            list.add(2);
            list.add(3);
           updateList(list);
            System.out.println(list);   //[1, 2]
        }
        private static void updateList(List list) {
            list.remove(2);
    //        list.remove(new Integer(2));  [1, 3]
        }
    }

12.5 Collection子接口：Set

图片说明

Set接口是Collection的子接口，Set接口没有提供额外的方法。
Set接口存储无序的、不可重复的数据。
以HashSet为例说明：
- 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
- 不可重复性：保证添加的元素按照equals()判断时，不能返回true，即：相同的元素只能添加一个。
Set集合不允许包含相同的元素，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失败。

Set判断两个对象是否相同不是使用“==”运算符，而是根据equals()方法。

package java.util;

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

12.5.1 HashSet

图片说明

HashSet是Set接口的典型实现，大多数时候使用Set集合时都使用这个实现类。
HashSet底层（用HashMap存储）：数组+链表。
HashSet按Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
HashSet具有以下特点：
- 不能保证元素的排列顺序。
- HashSet是线程不安全的。
- 集合元素可以是null。
HashSet集合判断两个元素相等的标准：两个对象通过hashCode()方法比较相等，并且两个对象的equals()方法返回值也相等。
要求：对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode()方法，以实现对象相等规则。即：相等的对象必须具有相等的散列码。
重写hashCode()方法的基本原则：
- 在程序运行时，同一个对象多次调用hashCode()方法应该返回相同的值。
- 当两个对象的equals()方法比较返回true时，这两个对象的hashCode()方法的返回值也应相等。
- 对象中用作equals()方法比较的Field，都应该用来计算hashCode值。

添加元素的过程：

我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值；
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即：索引位置）；
判断数组此位置上是否已经有元素：
- 如果此位置没有其他元素，则元素a添加成功； —> 情况1
- 如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较元素a与元素b的哈希值；
  - 如果哈希值不相同，则元素a添加成功。 —> 情况2
  - 如果哈希值相同，进而需要调用元素a所在类的equals()方法：
    - equals()返回true，元素a添加失败；
    - equals()返回false，则元素a添加成功。 —> 情况2

对于添加成功的情况2和情况3而言：元素a与已经存在指定索引上数据以链表的方式存储。

JDK7：元素a放到数组中，指向原来的元素。

JDK8：原来的元素在数组中，指向元素a。

package java.util;

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
    public int size() {
        return map.size();
    }
    public boolean isEmpty() {
        return map.isEmpty();
    }
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    public void clear() {
        map.clear();
    }

}

12.5.2 LinkedHashSet

图片说明

LinkedHashSet是HashSet的子类。
LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的（遍历器内部数据时，可以按照添加的顺序遍历）。
优点：对于频繁的遍历操作，性能高于HashSet。
LinkedHashSet插入性能略低于HashSet，但在迭代访问Set里的全部元素时有很好的性能。

LinkedHashSet不允许集合元素重复。

package java.util;

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

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

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }

}

12.5.3 TreeSet

图片说明

    package java.util;

    public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable {

        private transient NavigableMap<E,Object> m;
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();

        TreeSet(NavigableMap<E,Object> m) {
            this.m = m;
        }

        public TreeSet() {
            this(new TreeMap<>());
        }

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

        public TreeSet(Collection<? extends E> c) {
            this();
            addAll(c);
        }

        public TreeSet(SortedSet<E> s) {
            this(s.comparator());
            addAll(s);
        }    

        public Iterator<E> iterator() {
            return m.navigableKeySet().iterator();
        }

        public Iterator<E> descendingIterator() {
            return m.descendingKeySet().iterator();
        }

        public NavigableSet<E> descendingSet() {
            return new TreeSet<>(m.descendingMap());
        }

        public int size() {
            return m.size();
        }

        public boolean isEmpty() {
            return m.isEmpty();
        }

        public boolean contains(Object o) {
            return m.containsKey(o);
        }

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

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

        public void clear() {
            m.clear();
        }

        public  boolean addAll(Collection<? extends E> c) {
            // Use linear-time version if applicable
            if (m.size()==0 && c.size() > 0 &&
                c instanceof SortedSet &&
                m instanceof TreeMap) {
                SortedSet<? extends E> set = (SortedSet<? extends E>) c;
                TreeMap<E,Object> map = (TreeMap<E, Object>) m;
                Comparator<?> cc = set.comparator();
                Comparator<? super E> mc = map.comparator();
                if (cc==mc || (cc != null && cc.equals(mc))) {
                    map.addAllForTreeSet(set, PRESENT);
                    return true;
                }
            }
            return super.addAll(c);
        }

        private static final long serialVersionUID = -2479143000061671589L;
    }

TreeSet是SortedSet接口的实现类，可以按照添加对象的指定属性，进行排序。
向TreeSet中添加的数据，要求是相同类的对象。
自然排序：TreeSet根据compareTo()方法是否返回0判断元素是否相同，不再是equals()方法。
定制排序：TreeSet根据compare()方法是否返回0判断元素是否相同，不再是equals()方法。
TreeSet底层使用红黑树结构存储数据。
TreeSet两种排序方法：自然排序（Comparable）和定制排序（Comparator）。默认情况下，TreeSet采用自然排序。

练习1：

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class SetTest {
    @Test
    public void test1() {
        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        set.add(123);
        set.add(456);
//        set.add("AA"); 添加失败，不能添加不同类的对象
        set.add(789);
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");  //789 456 123
        }
    }

    @Test
    public void test2() {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(123);
        set.add(456);

//        set.add("AA"); 添加失败，不能添加不同类的对象
        set.add(789);
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");  //123 456 789 
        }
    }
}

练习2：

public class MyDate {
    private int year;
    private int month;
    private int day;

    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    public MyDate() {

    }

    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }

    public int getYear() {
        return year;
    }

    public void setYear(int year) {
        this.year = year;
    }

    public int getMonth() {
        return month;
    }

    public void setMonth(int month) {
        this.month = month;
    }

    public int getDay() {
        return day;
    }

    public void setDay(int day) {
        this.day = day;
    }

}
//+++++++++++++++++++++++++++++++
public class Employee implements Comparable<Employee> {
    private String name;
    private int age;
    private MyDate birthday;

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", birthday=" + birthday +
                '}';
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public MyDate getBirthday() {
        return birthday;
    }

    public void setBirthday(MyDate birthday) {
        this.birthday = birthday;
    }

    public Employee(String name, int age, MyDate birthday) {

        this.name = name;
        this.age = age;
        this.birthday = birthday;
    }

    public Employee() {

    }

    @Override
    public int compareTo(Employee o) {
        return this.name.compareTo(o.name);
    }

}
//+++++++++++++++++++++++++++++++++++++++++++
import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class EmployeeTest {
    /**
     * 自然排序
     */
    @Test
    public void test1() {
        TreeSet<Employee> employees = new TreeSet<>();
        Employee employee1 = new Employee("刘德华", 55, new MyDate(1965, 5, 4));
        Employee employee2 = new Employee("张学友", 43, new MyDate(1987, 5, 4));
        Employee employee3 = new Employee("郭富城", 44, new MyDate(1986, 5, 4));
        Employee employee4 = new Employee("黎明", 51, new MyDate(1954, 5, 4));
        Employee employee5 = new Employee("梁朝伟", 21, new MyDate(1978, 5, 4));
        employees.add(employee1);
        employees.add(employee2);
        employees.add(employee3);
        employees.add(employee4);
        employees.add(employee5);
        Iterator<Employee> iterator = employees.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next() + " ");
        }
    }

    /**
     * 定制排序
     */
    @Test
    public void test2() {
        TreeSet<Employee> employees = new TreeSet<>(new Comparator<Employee>() {
            @Override
            public int compare(Employee o1, Employee o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        Employee employee1 = new Employee("刘德华", 55, new MyDate(1965, 5, 4));
        Employee employee2 = new Employee("张学友", 43, new MyDate(1987, 5, 4));
        Employee employee3 = new Employee("郭富城", 44, new MyDate(1986, 5, 4));
        Employee employee4 = new Employee("黎明", 51, new MyDate(1954, 5, 4));
        Employee employee5 = new Employee("梁朝伟", 21, new MyDate(1978, 5, 4));
        employees.add(employee1);
        employees.add(employee2);
        employees.add(employee3);
        employees.add(employee4);
        employees.add(employee5);
        Iterator<Employee> iterator = employees.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next() + " ");
        }
    }

}

12.6 Map接口

12.6.1 Map体系概要

Map（JDK1.2）：双列数据，存储key-value对的数据。
- HashMap（JDK1.2）：Map的主要实现类；线程不安全，效率高；可以存储null的key和value；
  - LinkedHashMap（JDK1.4)：保证在遍历map元素时，可以按照添加的顺序实现遍历（原因：在原有的HashMap底层结构基础上，附加双向链表）。对于频繁的遍历操作，此类执行效率高于HashMap。
- TreeMap（JDK1.2）：保证按照添加的key-value进行排序，实现排序遍历。此时考虑key的自然排序或定制排序。底层使用红黑树。
- Hashtable（JDK1.0）：古老的实现类；线程安全，效率低；不能存储null的key和value；
  - Properties：常用来处理配置文件；key和value都是String类型。
HashMap的底层：数组+链表（JDK7及之前）；数组+链表+红黑树（JDK8）。
面试题：
1. HashMap的底层实现原理？
2. HashMap和Hashtable的异同？
3. CurrentHashMap与Hashtable的异同？

12.6.2 Map结构理解

Map中的key：无序的、不可重复的，使用Set存储所有的key。—>对于HashMap： key所在的类要重写equals()和hashCode()。对于TreeMap：key所在的类要重写compareTo()方法。
Map中的value：无序的、可重复的，使用Collection存储所有的value。—>value所在的类要重写equals()方法。
一个键值对：key-value构成了一个Entry对象。
Map中的entry：无序的、不可重复的，使用Set存储所有的entry。

12.6.3 HashMap底层原理

    HashMap map = new HashMap();

在实例化以后，底层创建了长度是16的一维数组Entry[] table。
```
map.put(key1, value1);
```
首先，调用key1所在类的hashCode()方法，计算key1的哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
如果此位置上的数据为空，此时的key1-value1添加成功（情况一）；
如果此位置上的数据不为空（意味着此位置上存在一个或多个以链表形式存在的数据），比较key1和已经存在的一个或多个数据的哈希值：
- 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功（情况二）；
- 如果key1的哈希值与某个已经存在的数据的哈希值相同，继续比较：调用key1所在类的equals()方法，比较：
  - 如果equals()返回false：此时key1-value1添加成功（情况三）；
  - 如果equals()返回true：使用value1替换相同key的value值。
补充：关于情况二和情况三：此时key1-value1和原来的数据以链表的方式存储。
在不断的添加过程中，会涉及到扩容问题，默认的扩容方式：扩容为原来容量的2倍，并将原有的数据赋值过来。
JDK8相较于JDK7在底层实现方面的不同：
- new HashMap()：底层没有创建一个长度为16的数组。
- JDK8底层的数组是：Node[]，而非Entry[]。
- 首次调用put()方法时，底层创建长度为16的数组。
- JDK7底层结构只有：数组+链表。JDK8中底层结构：数组+链表+红黑树。
- 当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时，此时此索引位置上的所有数据改为使用红黑树存储。

部分源码：

package java.util;

public class HashMap<K,V> extends AbstractMap<K,V> 
                                                    implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

    static class Node<K,V> implements Map.Entry<K,V> {  // 存储结构：Entry底层实现
        final int 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; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

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

    /* ---------------- Fields -------------- */
    transient Node<K,V>[] table;                // 存放数据的数组
    transient Set<Map.Entry<K,V>> entrySet;     // 存放数据的entry
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;

    /* ---------------- Public operations -------------- */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                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;
                    }
                    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;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    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)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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) {
            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;
    }

}

12.6.4 LinkedHashMap底层原理

LinkedHashMap部分源码：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

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

12.6.5 Map常用方法

1、添加（修改）、删除

put()：将指定key-value添加到（或修改）当前map对象中。
putAll()：将形参map中的所有key-value对存放到当前map中。
remove()：移除指定key的key-value对，并返回value。
clear()：清空当前map中的所有数据。

2、查询

get()：获取指定key对应的value。
containsKey()：判断当前map中是否含有某个key。
containsValue()：判断当前map中是否含有某个value。
size()：返回当前map中元素的个数。
isEmpty()：判断当前map是否为空。
equals()：判断当前map是否与形参map相等。

3、遍历

entrySet()：返回entry的Set。
keySet()：返回key的Set。
values()：返回value的Collection。

4、代码案例

    import org.junit.jupiter.api.Test;

    import java.util.*;

    public class MapTest {
        @Test
        public void test() {
            Map<String, Integer> map = new HashMap<>();
            map.put("A", 1);
            map.put("B", 2);
            map.put("C", 3);
            map.put("D", 4);
            map.put("D", 4);
            System.out.println(map);    // {A=1, B=2, C=3, D=4}

            Map<String, Integer> map1 = new HashMap<>();
            map1.put("C", 33);
            map1.put("E", 5);
            map.putAll(map1);
            System.out.println(map);    // {A=1, B=2, C=33, D=4, E=5}

            Integer cc = map.remove("C");
            System.out.println(map);    // {A=1, B=2, D=4, E=5}
            System.out.println(cc);     // 33

            Integer a = map.get("A");
            System.out.println(map);    // {A=1, B=2, D=4, E=5}
            System.out.println(a);      // 0

            boolean a1 = map.containsKey("A");
            boolean b = map.containsValue(1);
            System.out.println(a1);
            System.out.println(b);

            System.out.println(map.size());
            System.out.println(map.isEmpty());
            System.out.println(map.equals(map1));

            Set<Map.Entry<String, Integer>> entries = map.entrySet();
            Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
            while (iterator.hasNext()) {
                Map.Entry<String, Integer> next = iterator.next();
                System.out.print(next.getKey() + "=" + next.getValue() + " ");  // A=1 B=2 D=4 E=5
            }
            System.out.println();
            for (Map.Entry<String, Integer> item : entries) {
                System.out.print(item.getKey() + "=" + item.getValue() + " ");  // A=1 B=2 D=4 E=5
            }
            System.out.println();

            Set<String> strings = map.keySet();
            for (String item : strings) {
                System.out.print(item);     //ABDE
            }
            System.out.println();
            for (String item : strings) {
                System.out.print(item + "=" + map.get(item) + " ");     //A=1 B=2 D=4 E=5 
            }
            System.out.println();
            Collection<Integer> values = map.values();
            for (Integer item : values) {
                System.out.print(item);     //12450
            }

            map.clear();
            System.out.println(map.size());     // 0
            System.out.println(map);        // {}
        }
    }

5、常用方法

添加：put()
删除：remove()
修改：put()
查询：get()
长度：size()
遍历：entrySet()、keySet()、values()

12.6.6 TreeMap

向TreeMap中添加key-value，要求key必须是由同一个类创建的对象。

按照key进行排序：自然排序、定制排序。

import org.junit.jupiter.api.Test;

public class MapTest {
    @Test
    public void test() {
        // 自然排序：
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("C", 1);
        map.put("B", 2);
        map.put("A", 3);
        map.put("D", 4);
        System.out.println(map);    //{A=3, B=2, C=1, D=4}
        // 定制排序：
        TreeMap<String, Integer> map1 = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -o1.compareTo(o2);
            }
        });
        map1.put("C", 1);
        map1.put("B", 2);
        map1.put("A", 3);
        map1.put("D", 4);
        System.out.println(map1);   //{D=4, C=1, B=2, A=3}
    }
}

12.6.7 Properties

Properties类是Hashtable的子类，该对象用于处理属性文件。
由于属性文件里的key、value都是字符串来兴，所以Properties里的key和value都是字符串类型。

存取数据时，建议使用setProperty(String key, String value)方法和getProperty(String key)方法。

import org.junit.jupiter.api.Test;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;

public class MapTest {
    @Test
    public void test() throws IOException {
        Properties properties = new Properties();
        properties.load(new FileInputStream("jdbc.properties"));
        System.out.println(properties);     // {password=abc123, name=Tom}
        String name = properties.getProperty("name");
        String password = properties.getProperty("password");
    }
}
//+++++++++++++++++++++++++++jdbc.properties：
name=Tom
password=abc123

12.7 Collections工具类

Collections是一个操作Set、List和Map等集合的工具类。
Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
排序操作（均为static方法）：
- reverse(List)：反转List中元素的顺序。
- shuffle(List)：对List集合元素进行随机排序。
- sort(List)：根据元素的自然顺序对指定List集合元素按升序排序。
- sort(List, Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序。
- swap(List, int, int)：将指定List集合中的i处元素和j处元素进行交换。
查找、替换：
- max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素。
- max(Collection, Comparator)：根据Comparator指定的顺序，返回给定集合中的最大元素。
- min(Collection)
- min(Collection, Comparator)
- frequency(Collection, Object)：返回指定集合中元素的出现次数。
- copy(List dest, List src)：将src中的内容复制到dest中。
- replaceAll(List list, Object oldVal, Object newVal)：使用新值替换List对象的所有旧值。

同步化方法：

Collections类中提供给了多个synchronizedXxx()方法，该方法可以使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。

import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class CollectionsTest {
  @Test
  public void test() {
      List<Integer> list = new ArrayList();
      list.add(1);
      list.add(2);
      list.add(3);
      list.add(4);
      list.add(5);
      list.add(6);
      System.out.println(list);   //[1, 2, 3, 4, 5, 6]
      Collections.reverse(list);
      System.out.println(list);   //[6, 5, 4, 3, 2, 1]
      Collections.shuffle(list);
      System.out.println(list);   //[6, 3, 1, 5, 2, 4]
      Collections.swap(list, 0, 1);
      System.out.println(list);   //[2, 5, 6, 1, 3, 4]
//        java.lang.IndexOutOfBoundsException: Source does not fit in dest
//        List<Integer> dest = new ArrayList<>();
//        Collections.copy(dest, list);
      List dest = Arrays.asList(new Object[list.size()]);
      Collections.copy(dest, list);
      System.out.println(dest);   //[2, 5, 6, 1, 3, 4]
      List<Integer> safeList = Collections.synchronizedList(list);
  }
}

12 Java集合

12.1 Java集合框架概述

12.2 Collection接口方法

12.3 Iterator迭代器接口

扩展：增强for循环（foreach）

12.4 Collection子接口：List

1、ArrayList、LinkedList、Vector三者的异同？

2、ArrayList源码分析（部分）

3、LinkedList源码分析（部分）

4、Vector源码分析（部分）

5、List接口方法

6、练习

12.5 Collection子接口：Set

12.5.1 HashSet

12.5.2 LinkedHashSet

12.5.3 TreeSet

12.6 Map接口

12.6.1 Map体系概要

12.6.2 Map结构理解

12.6.3 HashMap底层原理

12.6.4 LinkedHashMap底层原理

12.6.5 Map常用方法

1、添加（修改）、删除

2、查询

3、遍历

4、代码案例

5、常用方法

12.6.6 TreeMap

12.6.7 Properties

12.7 Collections工具类