(java) 集合体系

标签：体系 java 接口索引 println 集合 new 节点

集合

在这里插入图片描述
集合的体系

整个集合体系最大的就是单列集合Collection和双列集合（键值对）Map
Collection接口下由两个子接口，分别为Set接口和List接口
List系列集合：添加的元素是有序、可重复、有索引，例如ArrayList
Set系列的集合：添加的元素是大部分无序、不重复、无索引

（一）单列集合Collection

对于collection接口来说，其实现类能够使用的公共性方法

add
remove
size
contains
iterator(包含hasNext和next，以及其自己的remove方法)
forEach/增强For

集合的遍历：

Iterator迭代器
特点：通过hasNext和next方法，来构建循环体系，hasNext表示是否有下一个，返回布尔值，next可以直接获取到下一个元素，返回拿到的元素，可以使用迭代器自己的remove方法，避免并发修改异常。

      //用法
      public static void main(String[] args) {
              Collection coll = new ArrayList<String>();
              coll.add("AAA");
              coll.add("BBB");
              coll.add("CCC");
              coll.add("DDD");
              Iterator<String> it =coll.iterator();
              while (it.hasNext()){
                  System.out.println(it.next());
              }
          }//main
//此处解释以下为什么 Iterator<String> it =coll.iterator();
//迭代器本来就是方法，但我们需要用迭代器内的方法，对于接口想要用
//方法，只能用其实现类

增强for
缺点：因为底层是迭代器，所以在遍历时，不能使集合的方式对其进行增删，再加上没有迭代器对象，也无法删除
forEach
缺点：因为其底层也是迭代器，所以增强for的缺点其也存在，再加上由于是匿名内部类, 访问外部类的局部变量的时候, 会被final修饰, 我们不能对其修改!!!

     //此处的coll是一个集合
     coll.forEach(new Consumer() {
          @Override
     public void accept(Object o) {
         System.out.println(o);
           }
     });
    coll.forEach(System.out::println);
   coll.forEach(str -> System.out.println(str));
   //使用lamada表达式简化

此处没有普通fori循环的原因就是，Collection还包含着Set，Set内的数据没有索引

并发修改异常(面试经典题目)

概念：因为我们在使用以迭代器为底层的循环体系时，使用集合的方法删除或增加元素，导致循环体系的索引迁移，cursor没有经过调整，导致了并发修改异常。
深层逻辑：使用了一个modCount的变量, 记录外部类集合增删的次数，创建迭代器的时候会使用expectedModCount记录这个初始的modCount的值, 一旦我们采用外部类集合的增删方法, 就会导致modCount的值发生变化, 但是迭代器的expectedModCount的值没有变化, 而modCount的值和expectedModCount的值进行比较, 如果不相等, 就会报并发修改异常!!!
迭代器使用自己的remove方法，为什么就不会产生并发修改异常?
答：删除了元素, 回退了指针, 而且同步了modCount和expectedModCount的值。

1. List 接口

LinkedList与ArrayList同属于List接口，而以下方法独属于List，且List的循环还需要包含普通fori，因为其都包含索引。

方法(涉及index）	解释说明：
void add(int index,E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

对于List接口的ArrayList和LinkedList，最好翻看其源码，观察其是怎么实现数组扩容、节点封装，以及实现一系列功能的。

1.1 ArrayList

ArrayList底层是基于数组来存储数据的。
其底层维护了一个长度位10的数组，来贮存数据，如果数据数量大于数组长度，则会触发1.5倍扩容。
其相较于数组的固定长度，大大遍历了我们的使用。
其引入了泛型的概念，限制一个集合只能存储一种数据类型，且集合要求只能存储引用数据类型，对于基础类型来说，存储其所对应的包装类。

1.2 linkedList

LinkedList底层是基于链表存储数据的
链表中的数据是一个一个独立的结点组成的，结点在内存中是不连续的，每个结点包含数据值以及上一个和下一个结点的地址（双向列表）。

LinkedList与ArrayList比速度（面试经典）：

对于ArrayList来说根据索引查询快，增删慢，对于LinkedList，查询慢，头尾增删快
解释二者慢的原因：

对于链表结构来说，其慢的原因一是因为需要找到具体位置，原因二是因为要new新的节点，其快是在头尾添加快
对于数组结构来说，其慢的原因就是当在中间位置插入内容时，需要后面全部迁移，导致时间变慢

2. Set接口

对于Set来说，因为没有自己的独有的成员方法，全部的方法来自于其父接口Collection。

对于Set父接口来说：

HashSet 无序，无索引，不能重复
linkedHashSet 有序，无索引，不能重复
TreeSet 自然排序/比较器排序，无索引，不能重复

2.1 HashSet

hash值（哈希值）：指通过存储真实地址所计算出来的伪地址。

JDK1.7之前，对于HashSet，其使用了数组+链表的方式进行存储数据，JDK1.8之后，其还引入了红黑树。

HashSet的优势：查询快尤其是在不知索引的情况下查询极快。

HashSet的存储步骤（面试黄金题目）：

求出元素的hash值
hash值与(数组长度-1)求**位&**运算得到其在数组中存储的索引
在数组中的索引位置查看有无节点：
1. 如果没有节点，则将该元素封装为节点，放在索引位置
2. 如果该位置有节点，则将该节点以及其后的全部节点的hash值与节点内容equals进行比较
  1. 如果发现hash值与节点内容全部相同，则认为是重复数据，就不会储存
  2. 如果遍历的该位置上的全部节点，发现没有重复，则采用尾插法将该节点放在索引位置，原来的头节点放在新节点之后。
对于hashSet的扩容，其有一个加载因子 loadFactor = 0.75; 当存储的数据个数 / hashSet数组长度 > loadFactor 时，直接给数组长度翻倍（初始长度为16），并且重新遍历数组中的每个元素，求取新的索引位置，将数据重新装填。
对于JDK1.8 后，加入红黑树，当有一条链上的节点>=8，且数组长度>=64，此时将该链表转换为红黑树模式
对于JDK1.8 后，加入红黑树，如果链上的节点<= 6，则又会由红黑树模式变为链式结构。

2.2 linkedHashSet

其实就是在HashSet的基础上添加了一条双向链表，其的元素储存和查询还是使用hash表的方式储存和查询，但是输出时通过这一条双向列表保证了可以有序输出

2.3 TreeSet

想要了解以红黑树为基础的TreeSet，可以先了解一下，红黑树是怎么来的？其演变过程是什么？

先补充小概念：

树根：树的根节点

树叶：树叶不存在分支

层数：树的层级

左子树，右子树：节点左边分支叫左子树，同理右边叫做右子树

二叉树→红黑树的演变（了解）：

二叉树：单出的进行二分储存，没有顺序，无法直接应用
排序二叉树：对于存储的数据进行比较，如果小，则放在左边，如果大，则放在右边，但是可能会造成层数过多，且没有办法对树根进行更改。
平衡二叉树：在排序树的基础之上，要求所有节点的左右子树相差不能超过1，如果超过1就会发生旋转逻辑，使得二叉树平衡
红黑树：在排序树的基础上，增加一套自己的逻辑，效果与平衡二叉树相似，红黑树原则（面试经典）：
1. 确定根和叶子都为黑色节点，默认新创建的都为红色节点
2. 两个红色节点不能相连
3. 每个节点到叶子的最短路径的黑色节点个数相同

TreeSet排序（重点）：

背景：因为其存储时会对数据进行比较存放，也就是说，也就是说，如果没有比较规则，没有办法使用TreeSet存储，其内存放必须要有自己的比较规则，帮我们来排序和去重

自然排序 comparable接口、重写compareTo方法，对于字符串、数字、原码内已经重写了方法，所有可以直接实现排序，对于自己类就需要考虑接口和重写了。
比较器排序(更推荐) comparator接口、重写compare方法，其优点：对比较的类没有侵入，无需在其类中插入接口和重写方法，且可以书写多套比较逻辑。

//以comparator接口为例
public static void main(String[] args) {
        TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        set.add(new Student("张三",8));
        set.add(new Student("张三",18));
        set.add(new Student("张三",18));
        System.out.println(set);//[Student{age=8, name='张三'}, Student{age=18, name='张三'}] 帮助我们实现了去重和排序
    }//main

排序补充：

使用TreeMap或者TreeSet进行排序时，我们可能会因为遇到一些特定的问题，这里总结：

升序/降序

int compare(Student o1,Srudent o2){}; 此时o1为新元素，o2为老元素，如果o1-o2,表示如果大于0，则应该把新元素放在老元素右边，其实就是升序，反过来就是降序
比较结果为小数

因为比较器比较结果要求为整数，如果为小数，则需要通过比较，返回整数，高司令为我们打了补丁，提供Double.compare(小数1，小数2);方法，如果结果大于0，则返回1，结果小于0，则返回-1。
遇到多条件的问题

遇到多条件，可以通过再比较方法中书写多套比较逻辑，拿着第一个返回的结果，如果比较结果为0，则拿着结果再次进行下一个条件验证，避免出现因为比较逻辑遗漏元素的情况。

（二）Map—双列集合

Map作为接口，其存储的数值都是以键值对形式存在，键Key以及值Value

对于双列集合，我们不应该陌生，因为我们之前看到的hashSet的源码中，最常见的就是map方法，其实对于部分单列集合来说，其就只使用了双列集合的键的部分，值的部分给了初值。

双列集合Map接口下面的实现类：

HashMap ：键部分为hashSet
LinkedHashMap：键部分为LinkedHashSet
TreeMap：键部分为TreeSet

其常用的方法：

put(K key,V value); 有则修改，无则创建
remove(K key);
get(K key);
size();
containsKey(K key); 返回值为布尔值
containsValue(V value); 返回值为布尔值

//案例：模拟随机投票，统计不同歌手获得的票数【歌手名单为数组】
  public static void main(String[] args) {
    String[] singerArr ={"许嵩","周杰伦","伍佰"};
        HashMap<String,Integer> hmp = new HashMap<>();
        Random r = new Random();
        for (int i = 0; i < 50; i++) {
            int num = r.nextInt(singerArr.length);
            String name = singerArr[num];
            if(!hmp.containsKey(name)){
                hmp.put(name,1);
            }else {
                hmp.put(name,hmp.get(name)+1);
            }
        }//for
        System.out.println(hmp);//{许嵩=16, 周杰伦=18, 伍佰=16}
    }//main

其遍历方式(重点)：

keySet+iterator :获取节点的键的HashSet,通过Map的get方法得到值进行拼接,迭代器作用在键上
entrySet ：获取节点的HashSet
forEach（方法名：BiConsumer）

//三种遍历方式展示
public static void main(String[] args) {
        HashMap<String, Integer> studentMap = new HashMap<>();
        studentMap.put("张三", 180);
        studentMap.put("李四", 175);
        studentMap.put("王五", 181);
        studentMap.put("钱四", 179);

        //遍历 Iterator + keySet
        Set<String> keys = studentMap.keySet();
        Iterator<String> it = keys.iterator();
        while (it.hasNext()){
            String key = it.next();
            Integer value = studentMap.get(key);
            System.out.println(key+"::"+value);

        }

        //遍历 entrySet 节点遍历

        Set<Map.Entry<String, Integer>> entries = studentMap.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key +"===="+value);
        }

        //forEach遍历
        studentMap.forEach(new BiConsumer<String, Integer>() {
            @Override
            public void accept(String s, Integer integer) {
                System.out.println(s +"----"+integer);
            }
        });
        
    }//main

（三） Collections 工具类

工具类都来自于java.utils之下，其私有构造器，全部方法都为静态方法，可以通过类名直接调用

sort方法：限定只有list实现类，排除set
addAll方法：给集合中快速添加元素，语法：addAll(Collection<? super T> c, T… elements) ，先添加集合元素，再添加可变参数。

//addAll方法
ArrayList<Integer> list = new ArrayList<>();
Collections.addAll(list,1,2,4,5,6,7,8);
System.out.println(list);//[1, 2, 4, 5, 6, 7, 8]

//针对于List的sort方法
LinkedList<Integer> list = new LinkedList<>();
Collections.addAll(list,1,4,2,6,4,2,2,5);//添加
Collections.sort(list);//排序
System.out.println(list);//[1, 2, 2, 2, 4, 4, 5, 6]

补充：可变参数

可变参数实际上就是通过其内将我们输入的内容包装为数组，满足我们对于确定数据类型相同，但是数量不同的数据要求。

格式：数据类型…数组名
缺点：只能方法中只能有一个可变参数，且可变参数必须在参数尾部

//小案例：写一个求和函数，可以实现多个整数相加求和，要求不能限制输入整数的个数
 public static int add(int... arr1) {
        int sum = 0;
        for (int num : arr1) {
            sum += num;
        }
        return sum;
    }
//psvm中
System.out.println(add(1,2,3));//6
System.out.println(add());//0
//此处可以看出，还能允许空参的存在，直接包装为空数组

标签：体系,java,接口,索引,println,集合,new,节点
From： https://blog.csdn.net/m0_56827189/article/details/145078044

集合

（一）单列集合Collection

1. List 接口

1.1 ArrayList

1.2 linkedList

2. Set接口

2.1 HashSet

2.2 linkedHashSet

2.3 TreeSet

排序补充：

（二）Map—双列集合

（三） Collections 工具类

补充：可变参数

相关文章

赞助商

阅读排行

(java) 集合体系

集合

（一） 单列集合Collection

1. List 接口

1.1 ArrayList

1.2 linkedList

2. Set接口

2.1 HashSet

2.2 linkedHashSet

2.3 TreeSet

排序补充：

（二）Map—双列集合

（三） Collections 工具类

补充：可变参数

相关文章

赞助商

阅读排行

（一）单列集合Collection