集合进阶之集合体系结构

集合进阶之集合体系结构 一、Collection 1. 集合类特点

提供一种存储空间可变的存储模型，存储的数据容量可以随时发生改变

2. Collection概述和使用

概述：是单例集合的顶层接口，它表示一组对象，这些对象也称为Collection的元素。JDK 不提供此接口的任何直接实现，它提供更具体的子接口（如Set和List）实现。

使用：创建Collection集合的对象，使用多态的方式，具体的实现类ArrayList

3. Collection 集合常用方法

方法名

说明

boolean add(E e)

添加元素

boolean remove(Object o)

从集合中移除指定的元素

void clear()

清空集合中的元素

boolean contains(Object o)

判断集合中是否存在指定的元素

boolean isEmpty()

判断集合是否为空

int size()

集合的长度，也就是集合中元素的个数

4. 遍历 4.1 Iterator

        本质：迭代器，集合的专用遍历方式，不在乎容器里面的数据类型

        Iterator iterator()：返回此集合中元素的迭代器，通过集合的iterator()方法得到，它是依赖于集合而存在的

4.2 Iterator中的常用方法

        E next()：返回迭代中的下一个元素

        boolean hasNext()：如果迭代具有更多元素，则返回 true

4.3 并发修改异常

        并发修改异常：ConcurrentModificationException

        产生原因：迭代器遍历的过程中，通过集合对象修改了集合中的元素，造成了迭代器获取元素中判断预期修改值和实际修改值不一致

        解决方案：用for循环遍历，然后用集合对象做对应的 *** 作即可

5. List 5.1 List概述和特点

        概述：有序集合(也称为序列)，用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引访问元素，并搜索列表中的元素。与Set集合不同，列表通常允许重复的元素。

        特点

        有序：存储和取出的元素顺序一致

        可重复：存储的元素可以重复

5.2 特有方法

方法名

说明

void add(int index,E element)

在此集合中的指定位置插入指定的元素

E remove(int index)

删除指定索引处的元素，返回被删除的元素

E set(int index,E element)

修改指定索引处的元素，返回被修改的元素

E get(int index)

返回指定索引处的元素

5.3 ListIterator

        列表迭代器，通过List集合的listIterator​()方法得到，所以说它是List集合特有的迭代器。用于允许程序员沿任一方向遍历列表的列表迭代器，在迭代期间修改列表，并获取列表中迭代器的当前位置，所以不会触发并发修改异常。

        常用方法

        E next()：返回迭代中的下一个元素

        boolean hasNext()：如果迭代具有更多元素，则返回

        true E previous​()：返回列表中的上一个元素

        boolean hasPrevious​()：如果此列表迭代器在相反方向遍历列表时具有更多元素，则返回 true

        void add​(E e)：将指定的元素插入列表

6. 增强for循环

        目的：简化数组和Collection集合的遍历

        实现Iterable接口的类允许其对象成为增强型 for语句的目标，它是JDK5之后出现的，其内部原理是一个Iterator迭代器

//范例： 
int[] arr = {1, 2, 3, 4, 5}; 
for(int i : arr) {
     System.out.println(i); 
}

7. 数据结构

        数据结构是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

7.1 Stack 栈

        栈是一种数据先进后出的模型

        数据进入栈模型的过程称为：压/进栈
        数据离开栈模型的过程称为：d/出栈

        栈顶元素：最后进入栈的元素
        栈底元素：最先进入栈的元素

7.2 Queue 队列

        队列是一种数据先进先出的模型

        数据从后端进入队列模型的过程称为：入队列
        数据从前端进入队列模型的过程称为：出队列

7.3 linkedList 链表

        增加：
        1. 数据B对应的下一个数据地址指向数据C
        2. 数据A对应的下一个数据地址指向数据B

        删除：
        数据B对应的下一个数据地址指向数据D，数据C删除

        查询：
        必须从头(head)开始查询

        对比数组，链表是一种查询慢、增删快的模型

8. List集合常用子类及特点

        Vector：底层由数据结构是数组，常用其子类Stack（栈），线程安全。

        ArrayList：底层数据结构是数组，查询快，增删慢，具有索引，可通过索引访问。

        linkedList：底层数据结构是链表，查询慢，增删快，具有指针，只能从头结点开始访问。

8.1 linkedList集合的特有功能

方法名

说明

public void addFirst​(E e)

在该列表开头插入指定的元素

public void addLast​(E e)

将指定的元素追加到此列表的末尾

public E getFirst​()

返回此列表中的第一个元素

public E getLast​()

返回此列表中的最后一个元素

public E removeFirst​()

从此列表中删除并返回第一个元素

public E removeLast​()

从此列表中删除并返回最后一个元素

9. Set集合概述和特点

        特点：不包含重复元素的集合，没有带索引的方法，所以不能使用普通for循环遍历

        哈希值：是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值，Object类中有一个方法可以获取对象的哈希值

        public int hashCode​()：返回对象的哈希码值

        默认情况下，不同对象的哈希值是不同的。重写hashCode()方法，可以实现让不同对象的哈希值相同，同一个对象多次调用hashCode()方法返回的哈希值是相同的。

9.1 HashSet

        特点：底层数据结构是哈希表(查询速度快)，对集合的迭代顺序不作任何保证，也就是说不保证存储和取出的元素顺序一致，没有带索引的方法，所以不能使用普通for循环遍历，由于是Set集合，所以是不包含重复元素的集合

        注意：HashSet集合存储元素要保证元素唯一性，需要重写hashCode()和equals()

9.2 linkedSet

        特点：是由哈希表和链表实现 Set 接口，具有可预测的迭代次序，由链表保证元素有序，即存储元素顺序和取出元素顺序一致，由哈希表保证元素唯一性。

9.3 TreeSet

        特点：元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法。没有带索引的方法，所以不能使用普通for循环遍历，由于是Set集合，所以不包含重复元素的集合

        TreeSet​()：根据其元素的自然排序进行排序

        TreeSet​(Comparator comparator) ：根据指定的比较器进行排序

二、Map 1. 概述

        Interface Map   K：键的类型；V：值的类型

        特点：将键映射到值的对象；不能包含重复的键；每个键可以映射到最多一个值

        举例：学生的学号和姓名

                   001    黑山老妖

                   002    牛魔王

        创建Map集合的对象需要用到多态的方式，具体的实现类为HashMap

        例：Map hm = new HashMap<>();

2. 成员方法

方法名

说明

V put(K key,V value)

添加元素

V remove(Object key)

根据键删除键值对元素

void clear()

移除所有的键值对元素

boolean containsKey(Object key)

判断集合是否包含指定的键

boolean containsValue(Object value)

判断集合是否包含指定的值

boolean isEmpty()

判断集合是否为空

int size()

集合的长度，也就是集合中键值对的个数

V get(Object key)

根据键获取值

Set keySet()

获取所有键的集合

Collection values()

获取所有值的集合

Set> entrySet()

获取所有键值对对象的集合

3. Map集合的遍历

方式一：①获取所有键的集合，用keySet()方法实现

              ②遍历键的集合，获取到每一个键。用增强for实现

              ③根据键去找值。用get(Object key)方法实现

方式二：①获取所有键值对对象的集合，Set> entrySet()：获取所有键值对对象的集合

              ②遍历键值对对象的集合，得到每一个键值对对象 用增强for实现，得到每一个Map.Entry

              ③根据键值对对象获取键和值 用getKey​()得到键盘；用getValue​()得到值

4. HashMap

        JDK1.8之前，底层采用数组+链表实现，可以说是一个元素为链表的数组

        JDK1.8之后，底层采用数组+链表/红黑树实现

        HashMap默认初始容量16

        存储过程：先将元素的哈希值求余容量长度，得到数为存储位置，然后比较哈希表此位置是否有元素，没有就添加，否则比较哈希值是否相同，不同就添加，相同就比较内容是否相同，不同就添加，相同就不添加

5. TreeMap

        类似于 TreeSet 集合，遍历元素时能按键值自然排序

6. HashMap与HashTable的区别

        虽然二者都称为哈希表，但有以下区别：

        ①底层结构不同

        HashMap：JDK1.8之前，底层采用数组+链表实现，可以说是一个元素为链表的数组；JDK1.8之后，底层采用数组+链表/红黑树实现。

        HashTable：在JDK1.0就出现了，底层由数组+链表构成

        ②默认的初始容量不同

        HashMap：哈希数组默认容量为16        HashTable：哈希数组默认容量为11

        ③扩容机制不同

        HashMap：当前哈希数组容量 * 2        HashTable：当前哈希数组容量 * 2 - 1

三、Collections 1. Collection与Collections的区别

        Collection是单列集合接口，而Collections是针对集合 *** 作的工具类

2. 常用方法

        public static > void sort​(List list)：将指定的列表按升序排序

        public static void reverse​(List list)：反转指定列表中元素的顺序

        public static void shuffle​(List list)：使用默认的随机源随机排列指定的列表