集合继承体系

  • Collection(接口) 单列"集合"
    • List(接口) (列表) 有序可重复
      • ArrayList 数组
      • LinkList 链表
    • Set (接口) 无序不可重复
      • HashSet 数组+链表 或 数组+链表+红黑树
      • ThreeSet 红黑树
  • Map(接口) 双列"集合" 键值对 键不可重复
    • HashMap 数组+链表 或 数组+链表+红黑树
    • ThreeMap 红黑树

该"集合"这是汉语中的语义的统称 具体该为对应单词所表示的东西

常见数据结构的特点

栈:先进后出

队列:先进先出

数组:查找快增删慢

链表:增删快查找慢

树:->树状结构

二叉树:任意一个节点的度要小于等于2 (度: 每一个节点的子节点数量)

查找树(排序树):

  1. 每一个节点上最多有两个子节点
  2. 左子树上所有节点的值都小于根节点的值
  3. 右子树上所有节点的值都大于根节点的值

平衡二叉树:

  1. 二叉树左右两个子树的高度差不超过1
  2. 任意节点的左右两个子树都是一颗平衡二叉树

红黑树:

红黑规则

  1. 每一个节点或是红色的,或者是黑色的
  2. 根节点必须是黑色
  3. 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil 视为叶节点,每个叶节点(Nil)是黑色的
  4. 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连 的情况)
  5. 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点

如何实现红黑规则
根节点位置:

	直接变为黑色

非根节点位置:

	父节点为黑色:

		不需要任何操作,默认红色即可

	父节点为红色:

	 	叔叔节点为红色:

			将"父节点"设为黑色,将"叔叔节点"设为黑色

				将"祖父节点"设为红色

				如果"祖父节点"为根节点,则将根节点再次变成黑色

		叔叔节点为黑色:

			 将"父节点"设为黑色

				将"祖父节点"设为红色

				以"祖父节点"为支点进行旋转

Collection中的方法()

返回只类型 方法(参数列表) 用法
boolean add(E e) 往集合中添加元素
boolean remove(Object o) 从该集合中删除指定元素
boolean clear() 从该集合中删除全部元素
default boolean removeIf(Predicate<? super E> filter) 删除满足条件的元素
int size() 返回此集合中的元素数
boolean contains(Object o) 如果此集合包含指定的元素，则返回 true
Iterator iterator() 获得迭代器对象
default void forEach(Consumer<? super T> action) 从迭代器对象中获得的方法(接口中有方法体)

1.Collection是接口创建对象 需要创建子类对象

2.removeIf()的使用

实现一个 断言的接口 该接口对返回值为真的 元素进行删除

 collection.removeIf(new Predicate<Student>() {
            @Override
            public boolean test(Student student) {
                boolean a = student.getName().startsWith("a");
                return a;
            }
 });

3.forEach()的使用

实现一个 消费者的接口 该接口 对接受的 每一个元素进行操作 一般进行遍历 增删会导致并发修改异常

collection.forEach(new Consumer<Student>() {
            @Override
            public void accept(Student student) {
                System.out.println(student);
            }
});

4.手写迭代器
https://www.cnblogs.com/acman-mr-lee/p/16413241.html

List中的方法

特点:

  • 有序 放入的数据顺序和取出数据顺序的顺序一致
  • 有索引 有下标可以直接锁定单一的元素
  • 可以放重复的元素 这里的重复指的是 对象封装的信息的相同
方法名 描述
void add(int index,E element) 在此集合中的指定位置插入指定的元素
E remove(int index) 删除指定索引处的元素，返回被删除的元素
E set(int index,E element) 修改指定索引处的元素，返回被修改的元素
E get(int index) 返回指定索引处的元素

ArrayList

底层:数组结构 查询快 增删慢

底层:链表结构 增删快 查询慢

特有方法:

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

区别:(来自百度)

1、数据结构不同

  • ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构。

2、效率不同

  • 当随机访问List (get和set操作)时，ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。

当对数据进行增加和删除的操作(add和remove操作)时，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

3、自由性不同

  • ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。

4、主要控件开销不同

  • ArrayList主要控件开销在于需要在List列表预留一定空间；而LinkList主要控件开销在于需要存储节点信息以及节点指针信息

自己实现对 对象的排序 实现对List的排序

Set中的方法

特点:

  • 无序 放入取出的数据 顺序不一致

  • 没有索引 不可以用普通for 遍历

  • 不可以重复 封装的信息内容不可以重复

    ​ HashSet 通过 哈希值+ equals实现 不重

    ​ ThreeSet 通过 比较(自身可比,或构造 传 比较器 )实现

方法: 常用无特有方法 和 Collection中的一样

HashSet

方法: 常用无特有方法 和 Collection中的一样

话术:

  • HashSet 底层的数据结构是 数组+链表 ,

  • 存放规则是: 底层在添加add时会先比较哈希值 不同则会添加元素 哈希值相同 则比较equals 再根据equals 结果,选择性存放;

  • 之所以要比较两次是因为 ,我们为了去除业务上认为的 相同 要重写hashCode()和equals ()方法,

额外使用hash值的原因是为了提高比较的效率,因为如果用equals是需要比较每各属性值的,重写的hashCode()产生的哈希值 将不再是唯一,如果不要equals()方法比较 而直接放弃存储,是按自己的意愿 想强制改变底层 比较流程,

总结:

  1. HashSet 底层数据结构是 数组+链表结构(JDK1.7) 数组+链表+红黑树(jdk1.8)当链表 长度大于8时链表会转为红黑树
    放元素时是 先根据 哈希值 对 数组长度 模运算 来分组 存放元素 模值相同的元素以链表结构存在
    当数组中存放的 链表结构(节点(Node)对象) 的数目为 数组长度的0.75倍时 数组扩容

  2. 存放规则

    去重依赖:重写hashCode()和重写eqalus()

    默认情况下 底层在添加add时会先比较哈希值 不同则会添加元素 哈希值相同 则比较equals 再根据equals 结果判断

  3. 为啥写重写两个---- 为了满足 业务逻辑(我们认为的一样)
    不重写hashCode写重写equls 根据添加流程的控制 hash值不同 是要添加元素的
    只重写hashCode 不重写eqalus 重写后的哈希值不再唯一

  4. 为啥要有哈希值呢 为了提高比较的效率

分析:

  1. HashSet 底层数据结构是 数组+链表结构 (JDK1.7)
  • 放元素时是 先根据 哈希值 对 数组长度 模运算 来分组 存放元素 模值相同的元素以链表结构存在
  • 当数组中存放的 链表结构(节点(Node)对象) 的数目为 数组长度的0.75倍时 数组扩容
  1. 添加规则
  • 当模运算的结果相同时 通过元素的equals方法比较 相同则不放 不同则放入// (这是自己定义的添加规则和jdk的一样)
    补充:默认情况下 底层在添加add时会先比较哈希值值相同 则比较equals 不同则会添加元素 (添加数组null 或已有的节点中)
  1. HashSet存在自定义类型时 要求属性一样认为是重复
    JDK:中的
  • 没有重写 haseCode() 是调用父类 该方法是个本地方法 计算时是基于对象的堆地址计算 哈希值的 该值具有唯一性
  • 重写 haseCode() 计算基于对象的 属性计算 哈希值 自己写的 不一定唯一
  • 没有重写 equals() 是比较 对象的堆内存地址值
  • 重写 equals() 比较是对象的 属性进行比较
  1. 不重写hashCode 不重写 equals
    每次new一次 得到一个新的堆内存地址 每次hash值不同都可以放入到HashSet 中
  2. 重写hashCode 不重写 equals
    可能不同属性的 两个对象的哈希值一样 ,而根据添加规则 这样的对象会被添加进去;
    (equals 比地址值不同,不同类new 两次)

如果是相同属性的 两个对象 哈希值也一样,而根据添加规则 这样的对象也会被添加进去;
(equals 比地址值不同,相同类new 两次)

  1. 不重写hashCode 重写 equals
    hash值肯定不同 肯定会加 重写 equals 的没有起作用
  2. 重写hashCode 重写 equals (hasCode重写后不唯一 为了Java的扩展性+equals)
    hash值相同的一定放在一组中 equals比较的是内容 相同则 不放入
    加equals方法 是为了防止 自己重写的hashCode产生值一样 而不equals 直接不放而产生<误判><-----流程不进行equals

ThreeSet

方法:

和Collection的常用方法一样

新特性:

​ 可排序

利用排序:

​ 1.要么自身可比 即 类本身实现Comparable接口

​ 2.要么再创建集合时传入 比较器对象( Comparator的实现类对象)

推荐使用:比较器的方式, 应为我们用别人的jar 包是.class文件 我们交付的 也是.class文件 自身可比 需要改源码

排序规则

实现Comparable接口重写compareTo() 方法 返回值 int ;实现Comparator接口重写compare()方法 返回值int

  • 如果返回值为负数，表示当前存入的元素是较小值，存左边
  • 如果返回值为0，表示当前存入的元素跟集合中元素重复了，添加新值返回旧值 看起来没有变
  • 如果返回值为正数，表示当前存入的元素是较大值，存右边

add执行

​ new TreeSet 的对象时 底层用的就是TreeMap对象 add方法就是map对象的add方法;add方法中有这样一个流程 如果 构造中传入了 比较器对象 就用比较器对象的compare()获得比较结果 然后根据结果 添加元素, 如果构造器 对象为 null 就将传入的对象 转为 Comparable 类型 用Comparable 的compareTo() 方法 获得比较结果.

例子: 书写自己的 Comparable 和Comparator 接口实现排序

https://www.cnblogs.com/acman-mr-lee/p/16407524.html

Map

Map的特点

​ 1.双列集合,一个键对应一个值

​ 2.键不可以重复,值可以重复

Map的常用方法

方法名 说明
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<Map.Entry<K,V>> entrySet() 获取所有键值对对象的集合 查

Map的遍历

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap <Integer,String> address= new HashMap<>();
        address.put(101,"阿三面馆");
        address.put(102,"阿四粥馆");
        address.put(103,"阿五米馆");
        address.put(104,"阿三快递");
        // set<k>
        Set<Integer> keySet = address.keySet();
        Iterator<Integer> it = keySet.iterator();
        while (it.hasNext()){
            Integer key=it.next();
            System.out.println(key+"--"+address.get(key));
        }
        // EntrySet
        System.out.println("----------");
        Set<Map.Entry<Integer, String>> keyValues = address.entrySet();
        for (Map.Entry<Integer, String> entry : keyValues) {
            System.out.println(entry.getKey()+"--"+entry.getValue());
        }
		// 利用不可变集合 实现批量添加
        Map<String, String> ssMap = Map.ofEntries(
                Map.entry("张三","123"),
                Map.entry("李四","125"),
                Map.entry("王五","123"));
        //ssMap 自身不可以增加 删除 修改
        //ssMap.put("张三","111");//不支持的操作异常
        Map<String, String> map = new HashMap<>(ssMap);
        map.put("赵六","126");
        System.out.println(map);
    }
}

HashMap

注意事项:

  • HashMap底层是哈希表结构的
  • 依赖hashCode方法和equals方法保证键的唯一
  • 如果键要存储的是自定义对象，需要重写hashCode和equals方法

常用方法: 和Map一样

ThreeMap

注意事项:

  • TreeMap底层是红黑树结构
  • 依赖自然排序或者比较器排序,对键进行排序
  • 如果键存储的是自定义对象,需要实现Comparable接口或者在创建TreeMap对象时候给出比较器排序规则

常用方法: 和Map一样

不可变集合

用途: 结合集合的带参构造,实现集合的批量添加

  • 在List、Set、Map接口中,都存在of方法,可以创建一个不可变的集合
    • 这个集合不能添加,不能删除,不能修改
    • 但是可以结合集合的带参构造,实现集合的批量添加
  • 在Map接口中,还有一个ofEntries方法可以提高代码的阅读性
    • 首先会把键值对封装成一个Entry对象,再把这个Entry对象添加到集合当中
  • Arrays.asList() 返回的是一个不可变List集合可以修改值

Arrays.asList() 详解 超链

https://www.cnblogs.com/acman-mr-lee/p/16407474.html

可变参数

语法:

​ 修饰符 返回值类型 方法名(数据类型… 变量名) { }

本质:

  • 这里的变量其实是一个引用类型的数组
  • 如果一个方法有多个参数，包含可变参数，可变参数要放在最后
  • 如果是可变参:调用者可以传入一个元素, 或者不传(得到是一个长度为0的数组,数组不是null), 或者传入多个元素, 或者传入数组都行