Lazy loaded image
编程
📕Day16-集合collection框架(list,set)
字数 5965阅读时长≈ 15 分钟
2019-1-27
2025-8-13
type
status
date
slug
summary
tags
category
icon
password

数据结构分类

notion image
  • Collection接口: 存储的是单列的数据
      • List接口: 存储的元素是有序的
      • ArrayList:
      • LinkedList:
      • Vector:
      Set接口: 存储的元素是无序且不重复的
      • HashSet:
      • LinkedHashSet:
      • TreeSet:
Map接口:存储的元素是双列的数据 Key-Value形式存储的数据
  • HashMap:
  • LinkedHashMap:
  • TreeMap:

集合和数组存储数据概述

集合、数组都是对多个数据进行存储操作的结构，简称Java容器。 说明：此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储（.txt,.jpg,.avi，数据库中)

数组存储的特点

一旦初始化以后，其长度就确定了。 数组一旦定义好，其元素的类型也就确定了。我们也就只能操作指定类型的数据了。
比如：String[] arr;int[] arr1;Object[] arr2;
弊端：
  1. 一旦初始化以后，其长度就不可修改。
  1. 数组中提供的方法非常限，对于添加、删除、插入数据等操作，非常不便，同时效率不高。
  1. 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
  1. 数组存储数据的特点：有序、可重复。对于无序、不可重复的需求，不能满足(集合正是解决了数组的弊端)

Collection接口

该接口中没有提供通过下标操作元素的方法
List接口和Set接口都继承自 Collection接口，Collection接口里定义的方法，List和Set的实现类都可以调用
Collection接口的常用方法:
add(Object obj) addAll(Collection coll) size() isEmpty() clear(); contains(Object obj) containsAll(Collection coll) remove(Object obj)
removeAll(Collection coll) retainsAll(Collection coll) equals(Object obj); hasCode() toArray() iterator();
💡
其中retain方法可以看做是remove方法的反向操作，一个是只保留，一个是移除
向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals()

Collection集合和数组间的转化

Iterator迭代器和foreach循环

遍历Collection的两种方式：
  1. 使用迭代器Iterator （定义在java.utils包下）
  1. foreach循环（或增强for循环）
Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。
GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。
notion image
Remove的使用
如果要使用Iteratror中的remove()方法，如果在还未调用next()或在上一次调用next方法之后已经调用了next方法，再调用都会报IllegalStateException
迭代器 的Remove()方法和集合直接调用Remove的方法不同，要求参数也不同
使用迭代器删除元素时，必须用迭代器的remove方法进行元素删除，不能使用List的remove方法删除，因为前者会保证方法中的modCount以及expectedModCount值一致，但是后者只是自增了modCount，没有调整expectedModCount，会导致错误 增强for循环不能对元素进行增删操作，如果有必须使用循环删除元素的需求，更推荐用 fori 循环+list列表的方式删除

List接口

list存储的是有序、可重复的数据
该接口在其“父接口”Collection的基础上新增了很多通过下标来操作元素的方法，比如：
  1. 增 add(E e) /
  1. 删 remove(E e) / remove(int index)
  1. 改 set(int index,E e)
  1. 查 get(int index) / indexOf(E e) / lastIndexOf(E e):
  1. 插 add(int index,E e)
  1. 长度 size()
  1. 遍历Iterator迭代器方式、增强for循环、普通的循环
常用使用类
Collection接口：单列集合，用来存储一个一个的对象
  • List接口：存储有序的、可重复的数据。 -->“动态”数组,替换原的数组
    • ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
    • LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储
    • Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存
notion image
以上练习题，updateList方法执行的是删除列表中索引为2的元素，故删除的是数字3。list中存的数据其实是自动装箱后基本包装类数据，add没有重载方法，添加的是对象，但是remove既可以删除对象，又可以删除索引，这里删除的是索引。如果要删除元素2，则list.remove（）方法里需要删除的是一堆Interger类型的对象，即List.remove(new Integer(2))
要点：区分List中的remove(int index)和remove(Object obj)方法

泛型Generic

定义数组的时候，语法是 元素数据类型[] 数组名 定义 List时， List list = new ArrayList()，如果不使用泛型的话，无法指定List里存储的元素类型，换言之，list列表里可以添加任何类型的数据。
但是通常在实际业务需求中，我们需要往一个List里面添加同一类型数据，另外在数据操作中，同一个类型的数据更方便进行统一操作，因此我们引入了泛型的概念
泛型的使用: 就是规定 Set / List / Map 的元素类型 泛型只能使用引用数据类型，不能使用基本数据类型

泛型通配符

<?> 表示任意类型 <? extends Person >规定泛型的上限，可以传入Person以及Person的子类 <? super Person >规定泛型的下限，可以传入Person以及Person的父类

自定义泛型

杂记比较器

用来操作Object对象 数组对应的有一个 Arrays工具类，用来快速操作数组
Collection接口，表示单列集合 List和Set Collections工具类，用来快速的操作 List 和 Set

ArrayList和LinkedArrayList

List接口里有两个常用的实现类: ArrayList LinkedList
add(E e) / add(int i,E e) / remove(int index) / remove(E e)/get(int index) indexOf(E e) / lastIndexOf(E e) / size() / isEmpty() / clear() 只要和下标相关的方法，都是List特有的，Collection接口里没有的!

迭代器

iterator() 方法是 Collection接口里的方法，List和Set都能够调用的方法 可以用来对 List和Set里的元素进行遍历

增强for循环<?>

list无论是调用 add还是remove,只要对集合里的元素进行了增删操作，都会让modCount成员变量自增一次
增强for循环无法通过赋值操作能修改原有数据，是复制出了一个全新的数组，增强for循环的递增其实仍然调用了迭代器

List源码分析

  • ArrayList：底层使用的是数组结构，查询快，增删慢，开发中最常使用的集合。
    • 查询快是因为每个元素都有一个编号
    • 增删慢当数组满了以后，扩充时会将原来数组的内容整个复制，插入以及删除数据时，会影响到其他的元素
  • LinkedList: 底层使用的是双向链表结构，查询慢，增删快
    • 增删快：在插入和删除时，最多只会涉及到三个节点
    • 查询慢：元素没有编号，查询数据是通过 循环来实现
  • Vector: 实现和 ArrayList基本相同。
    • Vector是线程安全的,效率低，ArrayList是线程不安全,效率高类似StringBuilder和StringBuffer的区别
  • ArrayList和LinkedList的选择:
    • 如果是增删比较频繁的场景，推荐使用LinkedList;
    • 如果是查询比较频繁的场景，推荐使用ArrayList

ArrayList源码分析

  • 成员变量:
    • Object[] elementData: Object类型的数组 elementData,用来保存所有的数据
    • int size: 表示数组里已经存入的元素个
  • 成员常量:
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 如果不指定数组的长度，elementData默认是空数组
    • DEFAULT_CAPACITY = 10; 如果不指定数组的长度，当调用add方法添加元素时，elementData长度会被设置为10，回顾StringBuilder的初始长度是16
  • 构造方法:
    • ArrayList(): 空参的构造方法。会将 elementData数组设置为
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组
    • ArrayList(int capacity): 会将elementData数组创建，并指定长度
  • 常用方法:
    • add(E e): 判断 elementData是否是空数组，如果是空，让指定数组的长度为默认值 DEFAULT_CAPACITY，如果添加的元素个数超出了 elementData 数组的长度，会将 elementData 数组扩容为 原来的 1.5倍
    • add(int index,E e): 当插入元素时，影响到的元素会很多 [index,size()-1]都会受影响
💡
jdk 7情况下 ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData list.add(123);//elementData[0] = new Integer(123); ... list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。 默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。 结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity) 2.2 jdk 8中ArrayList的变化： ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没创建长度为10的数组list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData[0] ... 后续的添加和扩容操作与jdk 7 无异。 小结：jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象 的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

LikedArrayList源码

LinkedList底层使用的是双向链表,链表上存储的数据不再是元素，而是将元素包装成为了 Node类型的对象
构造方法：<待补充>
成员变量: Node<E> first: 表示链表的第一个元素 Node<E> last: 表示链表的最后一个元素 int size:链表上元素的个数

Vector源码

jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。，在扩容方面，默认扩容为原来的数组长度的2倍。Vector方法里采用了大量的同步代码块，相对ArrayList是效率低，安全性高的

Set接口

  1. 存储的元素是无序的,没有编号，不能通过下标来操作元素，不等于随机性，存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
  1. 存储的元素不允许重复(判断元素是否重复的依据)，保证添加的元素照equals()判断时，不能返回true。即：相同的元素只能添加一个。
Set在开发中的使用场景比较少，适用于无序以及不重复的数据组织场景。

元素添加过程（以hashSet为例）

我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置，判断数组此位置上是否已经元素：
  1. 如果此位置上没其他元素，则元素a添加成功。 $情况1
  1. 如果此位置上其他元素b(或以链表形式存在的多个元素，则比较元素a与元素b的hash值，如果是链表的话， 得逐个比，直到比完或者得出结论）：
    1. 如果hash值不相同，则元素a添加成功。 $情况2
    2. 如果hash值相同，进而需要调用元素a所在类的equals()方法：
        3. (1) equals()返回true，元素a添加失败 $情况3
        (2) equals()返回false，则元素a添加成功。
对于添加成功的情况2和情况3而言，元素a 与已经存在指定索引位置上数据以链表的方式存储。连接方向： jdk 7 :元素a放到数组中，指向原来的元素。 jdk 8 :原来的元素在数组中，指向元素a 总结：七上八下
notion image
Set接口中没有额外定义新的方法，用的都是Collection中声明过的方法。
💡
Collection接口的常用方法: add(Object obj) addAll(Collection coll) size() isEmpty() clear(); contains(Object obj) containsAll(Collection coll) remove(Object obj) removeAll(Collection coll) retainsAll(Collection coll) equals(Object obj); hasCode() toArray() iterator();

Set分类

Collection接口：单列集合，用来存储一个一个的对象
  • Set接口：存储无序的、不可重复的数据 -->高中讲的“集合”
    • HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
      • LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历
          • 在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。 对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
    • TreeSet：可以照添加对象的指定属性，进行排序。

HashSet

HashSet底层使用的是 HashMap（本质）
HashSet判断元素是否重复的依据:先判断哈希值是否相同，如果哈希值不同，直接存入; 如果哈希值相同，再调用equals方法判断，如果equals方法如果是true，认为是统一个元素，不再存入，反之存入。

HashSet/LinkedHashSet:

要求：向HashSet、LinkedHashSet中添加的数据，其所在的类一定要重写hashCode()和equals()，HashSet里如果没有重写hashCode，创建了两个参数一样的对象，这两个对象的哈希值还是不一定相同的，未重写的Object类HashCode可以看做是随机生成的。
重写两个方法时，对象中用作 equals() 方法比较的 Field，计算 hashCode 值时候也要用到这些字段，这样可以尽量减少HashCode值冲突的可能。
重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码。

LinkHashSet

LinkedHashset在继承原有的HashSet的基础上，每个数据还维护了两个引用，记录此数据的前后元素（在添加的元素上有额外提供了一对双向链表）
优点：对于频繁的遍历操作，LinkedHashSet的效率高于HashSet
notion image

TreeSet

向TreeSet中添加的数据，要求是相同类的对象
TreeSet里的元素会进行排序,排序的依据是什么? TreeSet里存储的元素，必须要实现Comparable接口 TreeSet里的元素在比较时，会将元素转换成为Comparable类型的对象，然后调用元素的compareTo方法，看结果是否为0，如果是0，认定为同一个元素，不存入。如果大于0，往后面排队，小于0往前面排。
存入的元素必须实现Comparable接口，可以考虑自然排序（重写compareTo）或者定制排序（实现comparable接口）
自然排序中，比较两个对象是否相同的标准是compareTo返回0，不再是equals()
TreeSet和后面的TreeMap都采用红黑树的存储结构， 特征是有序，查询速度比list快
 
上一篇
Day15-异常处理（try...catch,throw,throws）
下一篇
Day17-Map、IO流基础
目录