3.集合框架

3.1认识集合

集合是一种容器，用来装数据的，类似于数组，但集合的大小可变，开发中也非常常用。

3.1.1集合体系结构

Collection单列集合

Collection代表单列集合，每个元素（数据）只包含一个值。

Map双列集合

Map代表双列集合，每个元素包含两个值（键值对）

3.2Collection的功能

为什么先学Collection的常用方法？

Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

3.2.1Collection的基本功能

3.2.2Collection的遍历

①迭代器遍历

迭代器是用来遍历集合的专用方式（数组没有迭代器），在Java中迭代器的代表是Iterator

②增强for循环遍历

for(元素的数据类型 变量名:数组或集合){


}

增强for循环可以用来遍历集合或数组。
增强for遍历集合，本质就是迭代器遍历集合的简化写法。

③Lambda表达式

得益于JDK8开始的新技术Lambda表达式，提供了一种更简单、更直接的方式来遍历集合。

3.2.3三种遍历方式的区别

认识并发修改异常问题

遍历集合的同时又存在增删集合元素的行为时可能出现业务异常，这种现象被称之为并发修改异常问题。

需求

现在加入购物车中存储了如下这些商品：Java入门，宁夏枸杞，黑枸杞，人字拖，特级枸杞，枸杞子。现在用户不想买枸杞了，选择了批量删除。

分析

后台使用ArrayList集合表示购物车，存储这些商品名。
遍历集合中每个数据，只要这个数据包含了‘枸杞’则删除它。
输出集合看是否已经成功删除全部枸杞数据。

我们现在按照分析开始尝试编写代码。

我们发现边遍历边删出现了并发修改一场的问题，那么我们如何处理呢？

解决方案1：i–

解决方案2：倒着遍历（前提是支持索引）

解决方案3：迭代器遍历删除（只能用迭代器自己的方法it.remove删除）

这里直接告诉大家，增强for和Lambda表达式都没有办法解决并发修改删除异常问题。

大家可以仿照前面的增强for和Lambda去写一下试试。

都会抛异常。

结论

增强for和Lambda只适合做遍历，不适合做遍历并删除。
如果集合支持索引，可以使用for循环遍历，每删除数据后做i–，或者可以倒着遍历。
可以使用迭代器遍历，并用迭代器提供的删除方法删除数据。

3.3List集合

3.3.1List的特点、特有功能

List集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection的功能List也都继承了。

List集合支持的遍历方式

for循环（因为List集合有索引）
迭代器
增强for循环
Lambda表达式

3.3.2ArrayList底层原理（说白了为了面试）

ArrayList是底层是基于数组存储数据结构的。

数组的特点：

查询速度快（注意：是根据索引查询数据快）：查询数据通过地址值和索引定位，查询任意数据耗时相同。

查询数据时是这样的，我们是已知数组内第一个数据的地址的，我们可以根据索引，比如我们要查第五个数据，直接在第一个数据的起始地址上加五个数据的单位长度就ok了，所以查任意数据都是起始地址加单位长度，所以快。

增删数据效率低：可能需要把后面很多数据进行前移。

我们会涉及增加数组长度，扩容，或者删除数据，数据前移，所以会导致增删数据效率低。

我们现在看一下源码。

关于扩容的代码，我们可以一步步看grow()的源码，里面包含了很多逻辑，我们只需要知道，最开始创建是new了一个空数组，只有在第一次添加数据时才开始扩容为一个大小为10的数组。如果size已经为10，我们要添加第11个数据，我们要继续进行扩容，那么接下来扩容是扩容为多大？有一个有限增长的参数值：最小容量减小容量，也就是5个。新容量就是15个，所以每次扩容是原来的1.5倍。

3.3.3LinkedList底层原理（说白了为了面试）

LinkedList是底层是基于链表存储数据结构的。

链表的特点

链表中的数据是一个一个独立的结点组成的，结点在内存中是不连续的，每个结点都包含数据值和下一个结点的地址。

链表的特点1：查询慢，无论查询哪个数据都要从头开始找。（只能顺藤摸瓜，一个接一个往下找。）
链表的特点2：链表增删相对快。（比如在BD之间增加数据C，我们只需要随便在内存里找个位置，让C的地址指向D，再让B的地址指向C，不会像数组一样需要迁移别人的数据，删除也是同理，只需要改指针的指向就ok了，不需要挪数据。）
以上特点是单向链表，但实际上java中的LinkedList是基于双链表实现的。

双链表就是又包含上一个数据的地址，也包含下一个数据的地址，包含头结点和尾结点，但缺点就是占内存占的更大。

对首尾元素进行增删改查的速度是极快的。

我们进入Node类

LinkedList新增了：很多首尾操作的特有方法。

包括头插尾插，获取头结点数据，获取尾结点数据，删除头结点数据，删除尾结点数据。

LinkedList的应用场景之一：可以用来设计队列。

简单介绍一下，队列就是先进先出，后进后出（这些链表、队列、栈等一系列都是数据结构的相关知识，如果有需要可以自行查看数据结构的相关内容。）

因为队列只是在首尾增删数据，所以用LinkedList实现很适合。

LinkedList的应用场景之二：可以用来设计栈。

栈就是先进后出，后进先出，就是一端封闭，一端开口。（手枪弹夹）

压/进栈（push）

弹/出栈（pop）

因为栈也只是在首尾增删数据，所以用LinkedList实现很适合。

我们也可以直接写push，pop，因为java也知道LinkedList可以做栈，但是我们点进去一看源码，就是套了层皮，实际都是一样的。（装饰）

3.4Set集合

3.4.1set集合的特点

Set系列集合特点：无序：添加数据的顺序和获取出的数据顺序不一致；不重复；无索引；
注意：Set要用到的常用方法，基本上就是Collection提供的，自己几乎没有额外新增一些常用功能。

HashSet

LinkedHashSet

TreeSet

3.4.2HashSet集合的底层原理

那么我们要先思考为什么往HashSet集合中存储数据是无序、无重复、无索引的？

我们首先需要了解哈希值

哈希值

就是一个int类型的随机值，Java中每个对象都有一个哈希值。
Java中的所有对象，都可以调用Object类提供的hashCode方法，返回该对象自己的哈希值。

对象哈希值的特点

同一个对象多次调用hashCode方法返回的哈希值是相同的。
不同的对象，他们的哈希值大概率不相等，但也有可能会相等（哈希碰撞）

（int（-21亿~21亿多），但是我们如果创建45亿个对象，一定会有3亿个对象相同。）

HashSet集合的底层原理是基于哈希表存储数据的。

哈希表

JDK8以前，哈希表=数组+链表
JDK8开始，哈希表=数组+链表+红黑树（JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树）
哈希表是一种增删改查数据，性能都比较好的数据结构

3.5Map集合

3.5.1Map集合概述

Map集合也被叫做“键值对”集合，格式：{key1=value1,key2=value2,key3=value3…}
Map集合的所有键是不允许重复的，但值可以重复，键和值是一一对应的，每一个键只能找到自己对应的值。

Map集合在什么业务场景下使用？

比如说购物车场景｛商品1=2，商品2=3，商品3=2，商品4=3｝
需要存储一一对应的数据时，就可以考虑使用Map集合来做。

Map集合的体系

接口：

Map<K,V>

实现类：

HashMap<K,V>→LinkedHashMap<K,V>
TreeMap

Map集合体系的特点

注意：Map系列集合的特点都是由键决定的，值只是一个附属品，值是不做要求的。

HashMap（由键决定特点）：无序、不重复、无索引（用的最多）
LinkedHashMap（由键决定特点）：由键决定的特点：有序、不重复、无索引
TreeMap（由键决定特点）：按照大小默认升序排序、不重复、无索引

HashMap（由键决定特点）

LinkedHashMap（由键决定特点）

3.5.2Map集合的常用方法

为什么要先学Map的常用方法？

Map是双列集合的祖宗，它的功能是全部双列集合都可以继承过来使用的。

//目标：搞清楚Map集合的常用方法
        Map<String,Integer> map = new HashMap<>();
        //put 加入数据
        map.put("小明",100);
        map.put("小红",90);
        map.put("小刚",80);
        //会把重复的，被覆盖的数据返回给你 ----80
        System.out.println(map.put("小刚", 88));
        map.put("紫霞",12);
        map.put(null,null);
        System.out.println(map);
        //写代码演示常用方法
        System.out.println(map.get("小红")); //根据键获取值


        System.out.println(map.containsKey("小明"));//判断是否包含某个键 true
        System.out.println(map.containsKey("小花"));//判断是否包含某个键 false


        System.out.println(map.containsValue(88));//判断是否包含某个值 true
        System.out.println(map.containsValue(99));//判断是否包含某个值 false


        System.out.println(map.isEmpty());//判断是否为空


        System.out.println(map.size());//获取键值对个数 4


        System.out.println(map.remove("小刚"));//删除键值对，返回被删除的值
        System.out.println(map);    //{小明=100, 小红=90, 紫霞=12, null=null}


        System.out.println(map.replace("紫霞", 13));//替换
        System.out.println(map);


        //获取所有的键放到一个Set集合中
        Set<String> keys = map.keySet();
        //遍历所有键
        keys.forEach(key-> System.out.println(key));


        //获取所有的值放到一个Collection集合中返回给我们
        Collection<Integer> values = map.values();
        //遍历所有值
        values.forEach(value-> System.out.println(value));
        
        map.clear();//清空Map集合

3.5.3Map集合的遍历方式

键找值：先获取Map集合全部的键，在通过遍历键来找值

Map<String,Integer> map = new HashMap<>();
        map.put("小明",100);
        map.put("小红",90);
        map.put("小刚",80);
        map.put("紫霞",12);
        map.put(null,null);
        System.out.println(map);


        //方案1.先获取Map集合全部的键，在通过遍历键来找值
        //1.先提取Map集合的全部键到一个Set集合中去
        Set<String> keys = map.keySet();
        System.out.println(keys);
        //2.遍历Set集合，得到每一个键
        for (String key : keys) {
            //3.通过键找到对应的值
            Integer value = map.get(key);
            System.out.println(key+"-->"+value);
        }

键值对：把“键值对”看成一个整体进行遍历（难度较大）

 //目标：掌握Map集合中遍历的方式。
        Map<String,Integer> map = new HashMap<>();
        map.put("小明",100);
        map.put("小红",90);
        map.put("小刚",80);
        map.put("紫霞",12);
        map.put(null,null);
        System.out.println(map);


        //方案2：键值对遍历，把“键值对”看成一个整体进行遍历（难度较大）
        // 1.把Map集合转换为Set集合
        Set<Map.Entry<String, Integer>> entries = map.entrySet(); //获取所有的键值对对象，把每一个键值对转化成一个Entry'对象。
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key+"-->"+value);
        }

Lambda：JDK1.8开始之后的新技术（非常的简单）

 //方案3：Lambda遍历
        //1.直接调用Map集合的foreach方法完成遍历
//        map.forEach(new BiConsumer<String, Integer>() {
//            @Override
//            public void accept(String s, Integer integer) {
//                System.out.println(s+"-->"+integer);
//            }
//        });
        //2.简化Lambda表达式
        map.forEach((k,v)-> System.out.println(k+"-->"+v));