集和进阶（一）

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

集和体系结构

  • Collection代表单列集合，每个元素（数据）只包含一个值。
  • Map代表双列集合，每个元素包含两个值（键值对）。

Collection集和体系

Collection集和特点

  • List体系结合：添加的元素是有序、可重复、有索引。
    • ArrayList、LinekdList：有序、可重复、有索引。
  • Set系列集合:添加的元素是无序、不重复、无索引。
    • Hashset：无序、不重复、无索引。
    • LinkedHashset：有序、不重复、无索引。
    • Treeset：按照大小默认升序排序、不重复、无索引。

Collection的常用方法

  • Collection是单列集合的祖宗它规定的方法(功能)是全部单列集合都会继承的
方法 功能
1.public boolean add(E e) 添加元素，添加成功返回true。
2.public void clear() 清空集合的元素。
3.public boolean isEmpty() 判断集合是否为空，是空则返回true。
4.public int size() 获取集合的大小。
5.public boolean contains(Object obj) 判断集合中是否包含某个元素。
6.public boolean remove(E e) 删除某个元素:如果有多个重复元素默认删除前面的第一个!
7.public Object[] toArray() 把集合转换成数组。
8.public void addAll(E e) 把入参中的元素批量复制到调用方法的集和中。

Collection的遍历方式

迭代器

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

Collection集和获取迭代器方法

Iterator迭代器中的常用方法

增强for循环

增强for循环格式

1
2
3
4
5
6
7
8
9
10
for(元素数据类型 变量名:数组或集和){
    变量名……
}

//例如
Collection<String> c = new ArrayList<>;
……
for(Strign s:c){
    System.out.println(s);
}

  • 增强for可以用来遍历集合或者数组。

  • 增强for遍历集合，本质就是迭代器遍历集合的简化写法。

lambda表达式

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

需要使用Collection的如下方法来完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Collection<String> c = new ArrayList<>;

//最原始
c.forEach(new Consumer<String>()){
    @Override
    public void accept(String s){
        System.out.println(s);
    }
};

//lambda
c.forEach(s -> System.out.println(s))
    
//方法引用
c.forEach(System.out::println)
  • 集合中存储的是元素对象的地址。

List集和

List集和的特点、特有方法

特点

  • 有序：添加数据顺序和获取数据顺序一致、可重复、有索引
    • ArrayList：有序、可重复、有索引
    • LinkedList：有序、可重复、有索引

特有方法

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

遍历方式

List集和支持的遍历方式

  1. for循环（因为List集和有索引）
  2. 迭代器
  3. 增强for循环
  4. lambda表达式

ArrayList集和的底层原理及应用场景

  • ArrayList：有序、可重复、有索引

  • ArrayList集和是基于数组实现的

    • 数组的特点：空间上连续。
    • 根据索引查询的速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同。时间复杂度O(1)
    • 删除效率低：可能需要把后面很多的数据进行前移。时间复杂度O(n)
    • 添加效率低：可能需要把后面很多的数据进行后移；还可能要对数组进行扩容。时间复杂度O(n)

  • ArrayList集和的创建过程

    1. 利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组
    2. 添加第一个元素时，底层会创建一个新的长度为10的数组
    3. 存满时，下次添加数据会扩容1.5倍
    4. 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度为原数组长度加上添加元素的数量

  • ArrayList集和适合的应用场景

    • 适合：根据索引查询数据，比如根据随机索引取数据（高效），或者数据量不是很大时。
    • 不适合：数据量大的同时又要频繁的进行增删操作时。

LinkedList集和的底层原理及应用场景

  • LinkedList：有序、可重复、有索引

  • LinkedList集和是基于双链表实现的

    • 双链表的特点：空间上离散。
    • 查询慢：无论查询哪个数据都要从头开始找。时间复杂度O(n)
    • 增删快：不需要移动大量的元素。查询时间复杂度O(n) 增删时间复杂度O(1)
    • 对首、尾元素的增删改查特别快。时间复杂度O(1)

  • LinkedList集和适合的应用场景

    1. 可以用来设计队列 queue（只在首尾增删元素）
    2. 可以用来设计栈 stack（只在首部增删元素）
      • 压栈 push() = addFirst()
      • 出战 pop() = removeFirst()

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

Set集和

特点

  • 无序：添加数据顺序和获取数据顺序不一致；不重复；无索引
    • HashSet：无序、不重复、无索引
    • LinkedHashSet：有序、不重复、无索引
    • TreeSet：排序、不重复、无索引
  • Set要用到的常用方法，基本上就是Collection提供的，自己几乎没有额外新增一些常用功能。

哈希值

  • 就是一个int类型的数值，Java中每个对象都有一个哈希值。
  • Java中的所有对象，都可以调用0bejct类提供的hashCode()方法，返回该对象自己的哈希值。
1
public int hashCode()  //返回对象的哈希码值。
  • 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
  • 不同的对象，它们的哈希值一般不相同，但也有可能会相同（哈希碰撞）。

HashSet集和的底层原理及应用场景

  • HashSet：无序、不重复、无索引

  • HashSet集和是基于 哈希表 实现的

    • 哈希表是一种增删改查数据性能都较好的数据结构。
    • 如果数组满了继续存入数据导致链表过长，会降低增删改查的效率。

  • 哈希表

    • JDK8之前，哈希表 = 数组 + 链表
      1. 创建一个默认长度16的数组，默认加载因子为0.75，数组名table。
      2. 使用元素的哈希值对数组的长度求余计算出应存入的位置。
      3. 判断当前位置是否为null，如果是null直接存入。
      4. 如果不为null，表示有元素，则调用equals方法比较，相等则不存；不相等，则存入数组。
        • JDK8之前，新元素存入数组，占老元素位置，老元素链接在下面。
        • JDK8之后，新元素直接链接在老元素下面。
      5. 为防止链表过长影响查找效率，当加载因子到0.75时会自动进行数组扩容。
    • JDK8开始，哈希表 = 数组 + 链表 + 红黑树
      • JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树
      • 提高了数据量大时的查找性能

  • 树

    • 二叉查找/排序树：左节点>中节点>右节点
    • 平衡二叉树：满足二叉查找树的基础上让树尽可能矮，以提高数据查询性能
    • 红黑树：可以自平衡的二叉树，是一种增删改查数据性能都相对较好的数据结构

  • HashSet集和去重复的机制

    • HashSet集合默认不能对内容一样的两个不同对象去重复。（因为hashCode不同）
    • 比如内容一样的两个学生对象存入到HashSet集合中去，HashSet集合是不能去重复的。

  • 结论：如果希望Set集合认为2个内容一样的对象是重复的，必须重写对象的equals()和hashCode()方法。

    • equals()重写后：只要两个对象内容一样，就返回True。
    • hashCode()重写后：只要两个对象内容一样，hashCode就是一样的。

LinkedHashSet集和的底层原理及应用场景

  • LinkedHashSet：有序、不重复、无索引

  • LinkedHashSet集和是基于 哈希表 实现的

  • 但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

TreeSet集和

  • TreeSet：不重复、无索引、可排序（默认升序，由小到大）

  • 底层是基于红黑树实现的排序。

  • 注意：

    • 对于数值类型：Integer，Double，默认按照数值本身的大小进行升序排序。
    • 对于字符串类型：默认按照首字符的编号升序排序。
    • 对于自定义类型如Student对象，Treeset默认是无法直接排序的。

  • 字定义排序规则

    • 方法一：让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。
    • 方法二：通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象），用于指定比较规则。（lambda表达式）

  • 两种方式中，关于返回值的规则：

    • 如果认为第一个元素> 第二个元素 返回正整数即可。
    • 如果认为第一个元素<第二个元素返回负整数即可。
    • 如果认为第一个元素=第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复。

  • 注意：如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序。

注意事项：集和的并发修改异常问题

  • 集和的并发修改异常

    • 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。

    • 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误。

    • 解决方法：

      • for循环：每次删除后i–；或者从后往前遍历
      • 迭代器：使用迭代器自带的remove方法
      • 增强for循环：无法解决
      • lambda：无法解决