代码链接：https://download.csdn.net/download/qq_52354698/86401303?spm=1001.2014.3001.5501

1. 集合的理解和好处

数组

1. 长度开始时必须指定，且指定后不能更改
2. 保存的必须为同一类型的元素
3. 使用数组进行增加、删除元素比较麻烦

集合

1. 可以动态保存任意多个对象，使用比较方便
2. 提供了一系列方便的操作对象的代码：add、remove、set、get
3. 使用集合添加、删除元素比较简单

2. 集合的框架体系

单例集合

双例集合

3. Collection 接口和常用方法

1. Collection 接口实现类的特点

1. Collection 实现子类可以存放多个元素，每个元素可以是 Object
2. 有些 Collection 的实现类，可以存放重复的元素，有些不可以
3. 有些 Collection 的实现类，有些是有序的List，有些不是有序Set
4. Collection 接口没有直接的实现子类，是勇哥它的子接口 Set 和 List 来实现的

    public static void main(String[] args) {

        List list = new ArrayList<>();
//        add:添加单个元素
        list.add("jack");
        list.add(10);
        list.add(true);
        System.out.println(list);
//        remove:删除指定元素
        list.remove(0);//删除第一个元素，索引
        System.out.println(list);
        list.remove(true);
        System.out.println(list);
//        contains:查找元素是否存在
        System.out.println(list.contains("jack"));
//        size:获取元素个数
        System.out.println(list.size());
//        isEmpty:判断是否为空
        System.out.println(list.isEmpty());
//        clear:清空
        list.clear();
        System.out.println(list);
//        addAll:添加多个元素
        ArrayList list1 = new ArrayList<>();
        list1.add("红楼梦");
        list1.add("三国演义");
        list.addAll(list1);
        System.out.println(list);
//        containsAll:查找多个元素是否都存在
        System.out.println(list.containsAll(list1));
//        removerAll:删除多个元素
        list.removeAll(list1);
        System.out.println(list);

    }

2. Collection 接口遍历元素方式1-使用 Iterator（迭代器）

1. 基本介绍

1. Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。
2. 所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用于返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器。
3. Iterator 的结构。
4. Iterator 仅用于遍历集合，Iterator 本身并不存放对象。

2. 迭代器的执行原理

Iterator iterator = coll.iterator();//获得一个集合的迭代器
//hasNext():判断是否还有下一个元素暖
while(iterator.hasNext()){
//next():1.下移 2.将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}

在调用iterator.next()方法之前必须要调用iterator.hasNext()进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。

3. Collection 接口遍历对象方式2-for循环增强

增强for循环，可以代替iterator迭代器，特点：增强for就是简化版的iterator，本质一样。只能用于遍历集合或数组。

for(元素类型 元素名 : 集合名或数组名){
	访问元素
}

4. List 接口和常用方法

1. 基本介绍

1. List 集合类中元素是有序（即添加顺序和取出顺序一致）、且可重复。
2. List 集合中的每个元素都有对应的顺序索引，即支持索引（从0开始）。
3. List 容器中的元素都对应一根 整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

2. 常用方法

    public static void main(String[] args) {

        List list = new ArrayList<>();
        list.add("小明");
        list.add("小红");
        list.add("小亮");
        System.out.println(list);
//        void add(int index, Object ele):在index位置插入ele元素
        list.add(1, "小王");
        System.out.println(list);
//        void addAll(int index, Collection eles):在index位置插入eles中所有元素
        List list1 = new ArrayList<>();
        list1.add("jack");
        list1.add("tom");
        list.addAll(1, list1);
        System.out.println(list);
//        Object get(int index):获取指定index位置的元素
        System.out.println(list.get(2));
//        int indexOf(Object obj):返回obj在集合中首次出现的位置
        System.out.println(list.indexOf("tom"));
//        int lastIndexOf(Object obj):返回obj在集合中末次出现的位置
        System.out.println(list.lastIndexOf("jack"));
//        Object remove(int index):溢出指定index位置的元素，并返回此元素
        list.remove(0);
        System.out.println(list);
//        Object set(int index, Object ele):设置指定index位置的元素为ele，相当于是替换
        list.set(1, "老王");
//        List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合（范围是前闭后开，toIndex位置的元素取不到）
        System.out.println(list.subList(0, 2));

    }

3. List的三种遍历方式

1. 使用 iterator
2. 使用增强 for
3. 使用普通 for

    public static void main(String[] args) {

        List list = new ArrayList<>();
        list.add("jack");
        list.add("tom");
        list.add("北京烤鸭");
        list.add("羊肉汤");

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

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

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

    }

5. ArrayList 底层结构和源码分析

1. 注意事项

1. 可以加入 null，并且多个。
2. ArrayList 是由数字来实现数据存储。
3. ArrayList 基本等同于 Vector，ArrayList 是线程不安全（但是执行效率高）。

2. 底层操作机制和源码分析

1. ArrayList 中维护了一个 Object 类型的数组 elementData。
2. 当创建 ArrayList 对象时，如果使用的是无参构造器，则初始 elementData 容量为 0，第一次添加，则扩容 elementData 为10，如果需要再次扩容，则扩容 elementData 为1.5倍。

创建了一个空的elementData数组={}

执行list.add
1. 先确定是否咬扩容
2. 然后再执行 赋值

该方法确定minCapacity
1. 第一次扩容为10

1. modCount++ 记录集合被修改的次数
2. 如果elementData的大小不够，就调用grow()去扩容

1. 真的扩容
2. 使用扩容机制来确定要扩容到多大
3. 第一次newCapacity = 10
4. 第二次及以后，按照1.5倍扩容
5. 扩容使用的是Arrays.copyof()

3. 如果使用的指定大小的构造器，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为1.5倍。

创建了一个指定大小elementData数组
this.elementData = new Object[capacity]

后续的操作基本类似，扩容时直接按照指定大小的1.5倍大小扩容

6. Vector 底层结构和源码分析

1. 基本介绍

1. Vector 类的定义说明

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

2. Vector 底层也是一个对象数组

protected Object[] elementData;

3. Vector 是线程同步的，即线程安全，Vector类的操作方法带有synchronized

2. Vector 和 ArrayList 的比较

3. 底层操作机制和源码分析

默认大小为10

添加数据到Vector中

确定是否需要扩容

如果需要的数组大小不够用，就扩容（两倍）

7. LinkedList 底层结构

1. 全面说明

1. LinkedList 底层实现了双向链表和双端队列特点。
2. 可以添加任意元素（元素可以重复），包括 null。
3. 线程不安全，没有实现同步。

2. 底层操作机制

1. LinkedList 底层维护了一个双向链表。
2. LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾结点。
3. 每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev 指向前一个，通过 next 指向后一个结点。最终实现双向链表。
4. 所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对效率比较高。

8. ArrayList 和 LinkedList 比较

如何选择ArrayList和LinkedList

1. 如果我们改查的操作多，选择ArrayList。
2. 如果我们增删的操作多，选择LinkedList。
3. 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList。
4. 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList，另一个模块是LinkedList，也就是说，要根据业务来进行选择。

9. Set 接口和常用方法

1. 基本介绍

1. 无序（添加和去除的顺序不一致），没有索引。
2. 不允许重复元素，所以最多包含一个null。
3. JDK API中Set接口实现的类有：
   

2. Set接口常用方法

和List接口一样，Set接口也是Collection的子接口，因此，常用方法和Collection接口一样。

3. Set接口的遍历方式

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口。

1. 可以使用迭代器
2. 增强for
3. 不能使用索引的方式来获取

    public static void main(String[] args) {

        Set set = new HashSet<>();
        set.add("john");
        set.add("lucy");
        set.add("jack");
        set.add(null);
        set.add(null);
        System.out.println(set);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }

        for (Object o : set) {
            System.out.println(o);
        }

    }

10. Set 接口实现类-HashSet

1. 全面说明

1. HashSet 实现了 Set 接口。
2. HashSet 实际上是 HashMap。
   
3. 可以存放 null 值，但是只能有一个 null。
4. HashSet 不保证元素是有序的，屈居于 hash 后，再确定索引的结果。（不保证存放元素的顺序和取出的顺序一致）
5. 不能有重复元素。

2. 案例分析

1. 执行 add 方法，会返回一个 boolean 值
2. 如果添加成功返回 true，否则返回 false
3. 可以通过 remove 删除元素

    public static void main(String[] args) {

        HashSet hashSet = new HashSet<>();
        System.out.println(hashSet.add("jack"));
        System.out.println(hashSet.add("john"));
        System.out.println(hashSet.add("john"));
        System.out.println(hashSet.add("king"));
        System.out.println(hashSet);
        hashSet.remove("john");
        System.out.println(hashSet);

    }

3. HashSet 底层机制说明

HashSet 底层是 HashMap，HashMap 底层是（数组+链表+红黑树）

1. HashSet 底层是 HashMap。
2. 添加一个元素时，先得到 hash 值会转换成->索引值。
3. 找到存储数据表 table，看这个索引位置是否已经存放元素。
4. 如果没有，直接加入。
5. 如果有，调用 equals 比较，如果相同，就放弃添加，如果不相同，则添加到最后。
6. 在 Java8 中，如果一条链表的元素个数超过 TREEEIFY_THRESHOLD （默认是8），并且 table 的大小 >= MIN_TREEIFY_CAPACITY（默认是64），就会进行树化（红黑树）。

执行 HashSet()

执行 add()

执行 put()，该方法会执行 hash(key) 来获取对应的hash值

执行 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 就是 HashMap 的一个数组，类型是 Node[]
        //if 语句表示如果当前 table 是 null，或者大小 = 0
        //就进行第一次扩容，到16个空间
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1)根据key，得到hash去计算该key应该存放在table表的哪个索引位置
        //并把这个位置的对象，赋给p
        //(2)判断p是否为null
        //(2.1)如果p为null，表示还没有存放元素，就创建一个Node
        //(2.2)如果p不为null，就放在该位置tabl[i] = newNode(hash, key, value, null)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
            //并且满足下面两个条件之一：
            //(1)准备加入的key和p指向的Node结点的key是同一个对象
            //(2)p指向Node结点的key的equals()和准备加入的key比较后相同
            //就不能加入
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判断p是不是一棵红黑树
            //如果是一棵红黑树，就调用putTreeVal，来进行添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //如果table对应索引位置，已经是一个链表，就是使用for循环比较
            //(1)依次和该链表的每一个元素比较后，都不相同，则加入到该链表的最后，注意：在把元素添加到链表后，立即判断该链表是否已经达到8个结点，就调用treeifBin()对当前这个链表进行树化(转换成红黑树)，注意：在转成红黑树时，还有进行一个判断如果该table数组的大小<MIN_TREEIFY_CAPACITY(64)
            //如果上面条件成立时，先对table扩容
            //如果上面条件不成立时，才进行转成红黑树
            //(2)依次和该链表的每一个元素比较时，如果有相同情况，就直接break
            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;
    }

1. HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor）是0.75 = 12
2. 如果table数组使用到了临界值12，就会扩容到162 = 32，新的临界值就是320.75 = 24，以此类推
3. 在Java8中，如果一条链表的元素个数到达TREEIF)THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树），否则仍然采用数组扩容机制

11. Set 接口实现类-LinkedHashSet

1. 全面说明

1. LinkedHashSet 是 HashSet 的子类。
2. LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个数组 + 双向链表。
3. LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
4. LinkedHashSet 不允许添加重复元素。

2. 底层机制示意图

1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致
2. LinkedHashSet 底层维护的是一个 LinkedHashMap （是 HashMap 的子类）
3. LinkedHashSet 底层结构（数组 table + 双向链表）
4. 添加第一次时，直接将数组 table 扩容到16，存放的节点类型是 LinkedHashMap$Entry
5. 数组是 HashMap$ Node[] 存放的元素/数据是 LinkedHashMap$Entry类型

12. Map 接口和常用方法

1. Map 接口实现类的特点

1. Map 与 Collection 并列存在。用于保存具有映射关系的数据（key-value）。
2. Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中。
3. Map 中的 可以 不允许重复，原因和 HashSet 一样，前面分析过源码。
4. Map 中的 value 可以重复。
5. Map 的 key 可以为 null，只能有一个，value 也可以为 null，可以有多个。
6. 常用 String 类做 Map 的 key。
7. Key 和 value 之间存在单向一度以关系，即通过指定的 key，总能找到对应的 value。
8. Map 存放数据的 key-value，是放在一个 Node 中的，有因为 Node 实现了 Entry 接口，有些书上也说一个 key-value 就是一个 Entry。

2. Map 接口的常用方法

1. put ：添加
2. remover ：根据键删除映射关系
3. get ：根据键获取值
4. size ：获取元素个数
5. isEmpty ：判断个数是否为零
6. clear ：清除
7. containsKey ：查找键是否存在

3. Map 接口遍历方式

1. containKey：查找键是否存在
2. keySet：获取所有的键
3. entrySet：获取所有关系k-v
4. values：获取所有的值

        Set keyset = map.keySet();

        for (Object o : keyset) {
            System.out.println(map.get(o));
        }

        Iterator iterator = keyset.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(map.get(next));
        }

13. Map 接口实现类-HashMap

1. HashMap 底层机制及源码剖析

1. k-v 是一个 Node 实现了 Map。Entry<k,v>，查看 HashMap 的源码可以看到。
2. jdk7 的 hashmap 底层实现【数组+链表】，jdk8 底层【数组+链表+红黑树】

2. 扩容机制

1. HashMap 底层维护了 Node 类型的数组 table，默认为 null。
2. 当创建对象时，将加载因子（loadfactor）初始化为 0.75.
3. 当添加 key-value 时，通过 key 的哈希值得到在 tabvle 的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的 key 和准备加入的 key 是否相等，如果相等，则直接替换 value；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
4. 第一次添加，则需要扩容 table 容量为 16，临界值（threshold）为12（16*0.75）。
5. 以后再扩容，则需要扩容 table 容量为原来的2两倍（32），临界值为原来的2倍，即24，依次类推。
6. 在java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）。

14. Map 接口实现类-Hashtable

1. 基本介绍

1. 存放的元素是键值对：key-value
2. hashtable 的键和值都不能为null，否则会抛出NullPointerException
3. hashTable 使用方法基本上和 HashMap 一样
4. hashTable 是线程安全的，hashMap 是线程不安全的

2. HashTble 和 HashMap 对比

15. Map 接口实现类-Properties

1. 基本介绍

1. Properties 类继承自 Hashtable 类并且实现了 Map 接口，也是使用一种键值对的形式来保存数据。
2. 使用特点和 Hashtable 类似。
3. Properties 还可以用于从 xxx.properties 文件中，就艾滋啊数据到 Properties 类对象，并进行兑取和修改。
4. 说明：xxx.properties 文件通常作为配置文件。

16. 总结-开发中如何选择集合实现类（记住）

1. 先判断存储的类型（一组对象【单例】、一组键值对【双例】）

2. 一组对象【单例】：Collection 接口
   允许重复：List
   增删多：LinkedList【底层维护了一个双向链表】
   改查多：ArrayList【底层维护Object类型的可变数组】
   不允许重复：Set
   无序：HashSet【底层是HashMap，维护了一个哈希值，数组+俩表+红黑树】
   排序：TreeSet
   插入和取出顺序一致：LinkedHashSet【数组+双向链表】

3. 一组键值对【双例】：Map
   键无序：HashMap【哈希表：数组+链表+红黑树】
   键排序：TreeMap
   键插入和取出顺序一致：LinkedHashMap
   读取文件：Properties

17. Collections 工具类

1. 基本介绍

1. Collections 是一个操作 Set、List、Map 等集合的工具类。
2. Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作。

2. 排序操作（均为static方法）

1. reverse(List)：翻转List中元素的顺序
2. shuffle(List)：对List集合元素进行随机排序
3. sort(List)：根据元素的自然顺序队指定List集合元素按升序排序
4. sort(List,Comparator)：根据指定的Comparator产生的顺序队List集合元素进行排序
5. swap(List,int,int)：将指定List集合中的i处元素和j处元素进行交换

3. 查找、替换

1. Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
2. Object max(Collection,Comparator)：根据Comparator指定的顺序，返回给定集合中的最大元素
3. Object min(Collection)
4. Object min(Collection,Comparator)
5. int frequency(Collection,Object)：返回指定集合中指定元素的出现次数
6. void copy(List dest,List src)：将src中的内容复制到dest中
7. boolean replaceAll(List list,Object oldVal,Object newVal)：使用新值替换List对象的所有旧值