集合进阶(一)-(List)-(set)

一、数据结构

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

常见数据结构-栈

数据进入栈模型的过程称为：进栈

数据离开栈模型的过程称为：出栈

栈是一种先进后出的模型

• A-B-C-D进，D-C-B-A出

常见数据结构-队列

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

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

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

常见数据结构-数组

• 查询效率高：查询数据通过索引定位，查询任意数据消耗时间相同
• 删除效率低：删除数据时，要将原始数据删除，同时后面每个数据前移
• 添加效率低：添加数据时，添加位置后的每个数据后移，再添加元素

常见数据结构-链表

---

---

---

二、List集合子类的特点

通过开发文档可以了解到

• ArrayList:底层数据结构是数组，查询快，增删慢
• LinkList:底层数据结构是链表，查询慢，增删快。

三、LinkedList集合的特有功能

方法名	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

四、Set集合

set集合特点

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

public class SetDemo{
    public static void main(String[] args){
        Set<String> set=new HashSet<String>();
        set.add("hello");
        set.add("world");
        set.add("world");
        for(String s:set){
            System.out.print(s);//helloworld
        }
    }
}

五、哈希值

哈希值是JDK根据对象的地址或字符串或数字算出来的int类型的数值

Object类中有一个方法可以获取对象的哈希值

• public int hashCode():返回对象的哈希值

对象的哈希值特点

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

六、HashSet集合

HashSet集合特点

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

HashSet集合保证元素唯一性分析

HashSet集合添加一个元素的过程：

• 要保证元素唯一性，需要重写hashCode()和equals()

七、常见数据结构-哈希表

哈希表

• JDK8之前，底层采用数组+链表实现，可以说是一个元素为链表的数组
• JDK8以后，在长度比较长的时候，底层实现了优化

查看开发文档

• HashSet()
• 构造一个新的空集合; 背景HashMap实例具有默认初始容量（16）

所以是一个长度为16的数组，要实现将哈希值存入数组需要进行计算：将哈希值对16取余数，根据余数放入指定位置

案例

需求

创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合

要求

学生对象的成员变量值相同，我们就认为是同一个对象

此时由于对象不同（哈希值也不同）导致重复。还需要重写hashCode()和equals()

八、LinkedHashSet集合概述和特点

特点

• 哈希表和链表实现的Set接口，具有可预测的迭代次序
• 由链表保证元素有序，也就是说元素的存储和取出顺序是一致的
• 由哈希表保证元素唯一，也就是说没有重复的元素

九、TreeSet集合

TreeSet集合特点

• 元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法

构造方法	描述
TreeSet()	根据其元素的自然排序进行排序
TreeSet(Comparator comparator)	根据指定的比较器进行排序

自然排序Comparable的使用

• 存储学生对象并遍历，创建TreeSet集合使用无参构造方法
• 要求：按照年龄从小到大排序，年龄相同，按照姓名的字母顺序排序

查看开发文档：

public interface Comparable

该接口对实现它的每个类的对象强加一个整体排序。 这个排序被称为类的自然排序 ，类的compareTo方法被称为其自然比较方法 。

因而要实现排序的功能需要元素所属类先实现这个接口

比较器排序Comparator的使用

• 存储学生对象并遍历，创建TreeSet集合使用带参构造方法
• 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序

结论

• 用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的
• 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法
• 重写方法时，一定要注意排序规则必须按照要求的主要和次要条件来写。

案例

①成绩排序

需求：使用TreeSet集合存储多个学生信息(姓名，语文成绩，数学成绩),并遍历该集合

要求：按照总分从高到低出现

ps：假设有同名同姓且成绩完全一样需要再用num3来判定

②不重复的随机数

需求：编写一个程序，获取10个1-20之间的随机数，要求随机数不能重复，并在控制台输出

思路:

• 创建Set集合对象
• 创建随机数对象
• 判断集合的长度是不是小于10，（是）：产生一个随机数，添加到集合，循环该步骤
• 遍历集合

如果使用TreeSet会给随机数排序

Set<Integer> set=new TreeSet<Integer>();