文章目录

Java集合

数据结构：

  • 逻辑结构：—>思想上的结构（厨房、卧室）—>线性表（数组，链表），图，树，栈，队列
  • 物理结构：—>真实结构（钢筋混凝土+牛顿力学）—>紧密结构（顺序结构），跳转结构（链式结构）

1 集合的概念

  • 概念：对象的容器，定义了对多个对象进行操作的常用方法。可实现数组的功能。
  • 和数组区别：
    1. 数组长度固定，集合长度不固定
    2. 数组可以存储基本类型和引用类型，集合只能存储引用类型
  • 位置：java.util.*

集合结构图

在这里插入图片描述

应用场合：

在这里插入图片描述

  • 前后端数据库交互，党需要将相同结构的个体整合到一起的时候，需要集合。
  • 实际应用场合：购物网站、邮件等等

2 Collection接口

子接口：List接口，Set接口

常用方法

增加：add(E e) addAll(Collection<? extends E> c)

删除：clear() remove(Object o) removeAll(Collection<?> c)

修改：stream() 返回以此集合为源的顺序

查看：iterator() 遍历 size()

判断：contains(Object o) equals(Object o) isEmpty()

遍历方式：增强for循环、迭代器

在这里插入图片描述

/*
        **Collection常用方法**

        增加：`add(E e)` `addAll(Collection<?  extends E> c)`
        删除：`clear()` `remove(Object o)` `removeAll(Collection<?> c)`
        修改：`stream()` 返回以此集合为源的顺序
        查看：`iterator()` 遍历 `size()`
        判断：`contains(Object o)` `equals(Object o)` `isEmpty()`
         */
        //1 创建对象：接口不能创建对象，利用实现类创建对象
        Collection col = new ArrayList();
        //2 调用方法：
        //集合只能存放引用数据类型的数据，不能放基本数据类型
        //基本数据类型自动装箱，对应包装，int-->Integer
        col.add(18);
        col.add(12);
        col.add(10);
        col.add(90);

        System.out.println(col.toString());

        List list = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});
        col.addAll(list);//将另一个集合添加入 col 中
        System.out.println(col);

//        col.clear();//集合清空
        System.out.println(col);
        System.out.println("集合中元素的数量："+col.size());
        System.out.println("集合是否为空："+col.isEmpty());

        boolean isRemove = col.remove(1);
        System.out.println(col);
        System.out.println("集合中的数据是否删除成功："+isRemove);


        Collection col2 = new ArrayList();
        col2.add(18);
        col2.add(12);
        col2.add(10);
        col2.add(90);

        Collection col3 = new ArrayList();
        col3.add(18);
        col3.add(12);
        col3.add(10);
        col3.add(90);

        System.out.println("两集合是否一样："+col2.equals(col3));
        System.out.println(col2==col3);//false,地址不一样

        System.out.println("是否包含元素："+col3.contains(12));

//遍历方法
Collection col = new ArrayList();
col.add(18);
col.add(12);
col.add(10);
col.add(90);
col.add("sad");
col.add(3.4);
//对集合遍历（对集合中元素进行查看）
//方式1：普通for循环,不能完成
/*for(int i=0; i<col.size(); i++){
    col
}*/

//方式2：增强for循环
for(Object o:col){
    System.out.println(o);
}
System.out.println("-----------------");
//方式3：iterator()方法
//Iterator：迭代器
/*
通过hasNext()来判断是否有下一个元素，如果有下一个元素，则返回true，否则返回false；
next()方法将元素获取到并且将“指针”下移
 */
Iterator it = col.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

1）Collections工具类

import java.util.ArrayList;
import java.util.Collections;

public class TestCollectios {
    public static void main(String[] args) {
        //Collections不支持创建对象，因为构造器私有化了
        //*ColLections cols = new Collections（）；*/
        //里面的属性和方法都是被static修饰，我们可以直接用类名，去调用即可：
        //常用方法：
        //addAll:
        ArrayList<String> list = new ArrayList<>();
        list.add("aa");
        list.add("cc");
        list.add("gg");
        Collections.addAll(list,"ff","dd","ff");
        Collections.addAll(list,new String[] {"bb","pp","qq"});

        Collections.sort(list);//sort提供升序排列
        //binarySearch 必须在有序的集合中查找--->排序
        System.out.println(Collections.binarySearch(list, "cc"));
        System.out.println(list);
        System.out.println("---------------------");
        //copy：替换方法
        ArrayList<String> list2 = new ArrayList<>();
        Collections.addAll(list2,"jj","kk");
        Collections.copy(list,list2);//将list2的内容替换到list 上去
        System.out.println(list);
        System.out.println(list2);

        //fill填充
        Collections.fill(list2,"zz");
        System.out.println(list2);


    }
}

3 List接口与实现类

实现类：ArrayList类、LinkedList类、Vector类（淘汰）

List接口常用方法 扩展的方法都跟索引有关 特点：不唯一，有序

增加：add(int index, E element)

删除：remove(int index) remove(Object o)

修改：set(int index, E element)

查看：get(int index)

判断：

遍历方式：普通for循环、增强for循环、迭代器

List list = new ArrayList();
list.add(13);
list.add(23);
list.add(43);
list.add(11);
list.add(2);
list.add("ab");
System.out.println(list);
list.add(2,10);//增加
System.out.println(list);

list.set(2,1);//修改
System.out.println(list);

list.remove(2);
System.out.println(list);
//在集合中存入的是Integer类型数据时，调用remove方法调用的是：remove(int index)
list.remove("ab");
System.out.println(list);

Object o = list.get(0);
System.out.println(o);

System.out.println("-----list集合遍历----------");
//list集合  遍历
//方式1：普通for循环
for(int i=0; i<list.size(); i++){
    System.out.println(list.get(i));
}
System.out.println("---------------");
//方式2：增强for循环
for(Object obj:list){
    System.out.println(obj);
}
System.out.println("---------------");
//方式3：iterator()迭代器
Iterator it = list.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}

1）ArrayList实现类

  • 数组结构实现，查询快、增删慢
  • JDK1.2版本，运行效率快、线程不安全

源码类似：StringBuilder

ArrayList实现类底层有两个基本要素：（1）Object类型的数组elementData，（2）size：数组的有效长度

transient Object[] elementData; // non-private to simplify nested class access
/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

JDK1.7源码：底层数组，在调用构造器的时候，数组长度初始化为10；扩容时，扩展为原数组的1.5倍。

JDK1.8源码：底层数组，在调用构造器时，底层数组为{}，在调用add方法后底层数组才重新赋值新数组，新数组的长度为10–>节省了内存，在add后才创建长度为10的数组。

  • 底层依旧时Object类型的数组，size：数组中有效长度;
  • ArrayList al = new ArrayList();在调用空构造器的时候，底层elementData数组的初始化为{};

2）Vector实现类

  • 数组结构实现，查询快、增删慢；
  • JDK1.0版本，运行效率慢、线程安全。

与ArrayList实现类的对比：

联系：底层都是数组的扩容

区别：

  1. ArrayList底层扩容长度时原数组的1.5倍，线程不安全 -->效率高
  2. Vector底层扩容长度时原数组的2倍，线程安全–> 效率低（已淘汰）

3）LinkedList实现类

  • 链表结构(双向链表)实现，增删块、查询慢。

LinkedList接口常用方法

增加：addFirst(E e) addLast(E e) offer(E e) offerFirst(E e) offerLast(E e)

删除：poll() pollFirst() pollLast()(<—推荐使用，JDK1.6以后新出的方法，提高代码的健壮性) removeFirst() removeLast()

修改：

查看：element() getFirst() getLast() indexOf(Object o) lastIndexOf(Object o) peek() peekFirst() peekLast()

判断：

遍历方式：普通for循环、增强for循环、迭代器

public class Test4 {
    public static void main(String[] args) {
        /*LinkedList接口**常用方法**
    增加：`addFirst(E e)` `addLast(E e)`
         `offer(E e)` `offerFirst(E e)` `offerLast(E e)`
    删除：`poll()` `pollFirst()` `pollLast()`(<---推荐使用，JDK1.6以后新出的方法，提高代码的健壮性)
         `removeFirst()` `removeLast()`
    修改：
    查看：`element()` `getFirst()` `getLast()`
         `indexOf(Object o)` `lastIndexOf(Object o)`
         `peek()` `peekFirst()` `peekLast()`
    判断：
    遍历方式：普通for循环、增强for循环、迭代器
    */
        //创建一个LinkedList集合对象
        LinkedList<String> list = new LinkedList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("cc");
        list.add("bbb");//LinkedList可以添加重复数据
        list.add("eee");

        list.addFirst("12");
        list.addLast("345");

        list.offer("qaz");//添加数据在再末尾
        list.offerFirst("00");
        list.offerLast("99");

        System.out.println(list.poll());//删除开头的元素，并将元素输出
        System.out.println(list.pollFirst());
        System.out.println(list.pollLast());

        list.clear();//清空集合
        System.out.println(list);
        System.out.println(list.pollFirst());//提高代码的健壮性

        //System.out.println(list.removeFirst());//报错，Exception in thread "main" java.util.NoSuchElementException

        System.out.println(list);        
    }
}

遍历方式：

//集合的遍历
//1 普通for循环
for(int i=0;i<list.size();i++){
    System.out.println(list.get(i));
}
System.out.println("------------------");
//2 增强for循环
for(String str:list){
    System.out.println(str);
}
System.out.println("------------------");
//3 迭代器
/*Iterator<String> it = list.iterator();
while (it.hasNext()){
    System.out.println(it.next());
}*/
//下面这种方式好，节省内存
for(Iterator<String> it = list.iterator();it.hasNext();){
    System.out.println(it.next());
}

4）ArrayList和LinkedList的区别

ArrayList：数据结构

  • 物理结构：紧密结构
  • 逻辑结构：线性表（数组）

LinkedList：数据结构

  • 物理结构：跳转结构
  • 逻辑结构：线性表（链表，双向链表）

在这里插入图片描述

模拟Linked List源码：

public class Node {
    private Node pro;
    private Object object;
    private Node next;

    public Node getPro() {
        return pro;
    }

    public void setPro(Node pro) {
        this.pro = pro;
    }

    public void setObject(Object object) {
        this.object = object;
    }

    public void setObject(Node object) {
        this.object = object;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getObject() {
        return object;
    }

    public Node getNext() {
        return next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "pro=" + pro +
                ", object=" + object +
                ", next=" + next +
                '}';
    }
}

public class MyLinkedList {
    //链中一定有一个首节点
    Node first;
    //链中一定有一个尾节点
    Node last;
    //计数器
    int count = 0;
    //提供一个构造器
    public MyLinkedList(){

    }
    //添加元素方法
    public void add(Object o){
        if(first == null){//证明添加的元素是第一个节点
            Node n = new Node();
            n.setPro(null);
            n.setObject(o);
            n.setNext(null);
            //当前链中第一个节点变为n
            first = n;
            //当前链中最后一个节点变为n
            last = n;
        }else{
            Node n = new Node();
            n.setPro(last);//n的上一个节点一定是当前链中的最后已个节点last
            n.setObject(o);
            n.setNext(null);
            //当前链中最后一个节点的下一个元素 要指向n
            last.setNext(n);
            //将最后一个节点变为n
            last = n;
        }
        //链中元素数量加1
        count++;
    }

    //得到集合中元素的数量
    public int getSize(){
        return count;
    }

    //通过下标得到元素
    public Object get(int index){
        //获取链表的头元素
        Node n = first;
        //一路next得到想要的元素
        for(int i = 0;i<index; i++){
            n = n.getNext();
        }
        return n.getObject();
    }
}

public class Test {
    public static void main(String[] args) {
        //创建一个集合对象
        MyLinkedList ml = new MyLinkedList();
        ml.add("aa");
        ml.add("bb");
        ml.add("cc");
        System.out.println(ml.getSize());
        System.out.println(ml.get(0));
        System.out.println(ml.get(1));
        System.out.println(ml.get(2));
    }
}

4 泛型和工具类

1）泛型引入

泛型（Generic）相当于标签

形式：<>

集合容器类在设计阶段/声明阶段不能确定这个容器到底实际存的是什么类型的对象，所以在JDK1.5之前只能把元素类型设计为Object，JDK1.5之后使用泛型来解决，因为这个时候除了元素的类型不确定，其他的部分是确定的，例如关于这个元素如何保存，如何管理等是确定的。因此此时把元素的类型设计成一个参数，这个类型参数叫做泛型。

Collection，List，ArrayList 这个就是类型参数，即泛型。

如果不使用泛型的话，有缺点：
一般我们在使用的时候基本上往集合中存入的都是相同类型的数据 —>便于管理，所以现在什么引用数据类型都可以存入集合—>不方便！

加入泛型的优点：在编译时期就会对类型进行检查，不是泛型对应的类型就不可以添加入这个集合。

//创建一个ArrayList集合，向这个集合中存入学生的成绩
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(78);
        al.add(67);
//        al.add("ssa");//报错
        //对集合遍历
        //方式1
        for(Object obj:al){
            System.out.println(obj);
        }
        //方式2
        for(Integer i:al){
            System.out.println(i);
        }

泛型总结：

  1. JDK1.5以后

  2. 泛型实际就是一个<>引起来的参数类型，这个参数类型具体在使用的时候才会确定具体的类型。

  3. 使用了泛型以后，可以确定集合中存放数据的类型，在编译时期就可以检查出来。

  4. 使用泛型你可能觉得麻烦，实际使用了泛型才会简单，后续的遍历等操作简单。

  5. 泛型的类型：都是引用数据类型，不能是基本数据类型。

  6. ArrayList al = new ArrayList(); 在JDK1.7以后可以写为：
    ArrayList al = new ArrayList<>(); ----钻石运算符

2）自定义泛型结构

（1）泛型类、泛型接口

【1】泛型类 实例化对象

/**
 * GenericTest <E> 泛型类
 * @param <E>
 *     <E>中，E是一个参数类型，这个类型现在是不确定的，相当于一个占位
 *     但是现在确定的是这个类型一定是一个引用类型，而不是基本数据类型
 */
public class GenericTest <E> {
    int age;
    String name;
    E sex;

    public void a(E n){
    }
    public void b(E[] m){
    }
}

class Test{
    public static void main(String[] args) {
        //GenericTest进行实例化
        //1 实例化的时候 不指定泛型,如果实例化的时候不指定泛型，则认为此泛型为Object类型
        GenericTest genericTest = new GenericTest();
        genericTest.a("abc");
        genericTest.a(12);
        genericTest.a(3.2);

        genericTest.b(new String[]{"a","x","e"});
        //2 实例化时指定泛型  *推荐方式*
        GenericTest<String> genericTest2 = new GenericTest<>();
        genericTest2.sex = "男";
        genericTest2.a("sqw");
        genericTest2.b(new String[]{"a","x","e"});
    }
}

【2】继承情况：

  1. 父类指定泛型：
class SubGenericTest extends GenericTest<Integer>{

}
class Demo{
    public static void main(String[] args) {
        //指定父类泛型，那么子类就不需要再指定泛型，可以直接使用
        SubGenericTest sgt = new SubGenericTest();
        sgt.a(12);//Integer类型
    }
}
  1. 父类不指定泛型：
class SubGenericTest2<E> extends GenericTest<E>{

}
class Demo2{
    public static void main(String[] args) {
        SubGenericTest2<String> sgt2 = new SubGenericTest2<>();
        sgt2.a("sdf");
        sgt2.sex = "women";
    }
}

【3】注意细节：

  1. 泛型类可以定义多个参数类型；
  2. 泛型类的构造器写法；
  3. 不同的泛型的引用类型不可以相互赋值；
  4. 泛型如果不指定，那么就会被擦除，泛型对应的类型为Object类型；
  5. 泛型类型中的静态方法，不能使用类的泛型；
  6. 不能直接使用E[]的创建。
import java.util.ArrayList;
import java.util.Objects;

/**
 *
 * @param <A>
 * @param <B>
 * @param <C>
 */
public class GenericTest2<A,B,C> {
    A age;
    B name;
    C sex;
    public void a(A a,B b,C c){
        //A[] i = new A[10]; //不可以直接使用E[]创建数组
        A[] i = (A[])new Object[10];//可以先利用Object类型创建数组，再强制转换
    }

    /*public GenericTest2<A,B,C>(){
        泛型类构造器这种写法不对
    }*/

    public void b(){
        ArrayList<String> list = null;
        ArrayList<Integer> list2 = null;
       // list = lsit2; 不可赋值
    }

    /*public static int c(A a){//静态方法中出现泛型，报错
        return 1;
    }*/

}

（2）泛型方法

  1. 什么是泛型方法？

    不是带泛型的方法就是泛型方法 （T ！= E）
    泛型方法有要求：这个方法的泛型的参数类型要和当前的类的泛型无关
    换个角度：泛型方法对应的那个泛型参数类型和当前所在的这个类 是否是泛型类，泛型是哈 无关

  2. 泛型方法定义的时候，前面要加上
    原因：如果不加的话，会把T当做一种数据类型，然而代码中没有T类型那么就会报错

  3. 调用方法：
    T的类型是在调用方法的时候确定的

  4. 泛型方法能否是静态方法：

    能

/**
 *
 * @param <E>
 *     1 什么是泛型方法？
 *     不是带泛型的方法就是泛型方法 *（T ！= E）*
 *     泛型方法有要求：这个方法的泛型的参数类型要和当前的类的泛型无关
 *     换个角度：泛型方法对应的那个泛型参数类型和当前所在的这个类 是否是泛型类，泛型是哈 无关
 *     2 泛型方法定义的时候，前面要加上<T>
 *      原因：如果不加的话，会把T当做一种数据类型，然而代码中没有T类型那么就会报错
 *     3 调用方法:
 *      T的类型是在调用方法的时候确定的
 *     4 泛型方法能否是静态方法：能
 *
 */
public class GenericTest3<E> {
    //不是泛型方法
    public void a(E e){

    }
    //是泛型方法
    public <T> void b(T t){

    }
    public static <T> void c(T t){
        //静态 泛型方法
    }
}

class Test1{
    public static void main(String[] args) {
        GenericTest3<String> gt3 = new GenericTest3<>();
        gt3.a("sdf");
        gt3.b("ert");
        gt3.b(24);
        gt3.b(false);
    }
}

泛型参数的继承关系：

A和B是子类父类的关系，但是G(A)和G(B)不存在继承关系，而是并列关系。

public class Test {
    public static void main(String[] args) {
        Object obj = new Object();
        String s = new String();
        obj = s;//父类引用指向子类对象（多态的一种形式）

        Object[] objArr = new Object[10];
        String[] strArr = new String[10];
        objArr = strArr;//父类引用指向子类对象（多态的一种形式）

        List<Object> list = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        //list =list2; //
        //总结：A和B是子类父类的关系，但是G(A)和G(B)不存在继承关系，而是并列关系。

    }
}

（3）通配符

  • 没有通配符的时候：下面的a方法，相当于方法的重复定义，报错
public class Test {
    public void a (List<Object> list){}
    public void a (List<String> list){}
    public void a (List<Integer> list){}
}
  • 引入通配符
public class Test2 {
    public static void main(String[] args) {

        List<Object> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        List<?> list = null;
        list = list1;
        list = list2;
        list = list3;
        
    }
}

发现：

A和B是子类父类的关系，G和G不存在子类父类关系，是并列的；

加入通配符?后，G<?>就变成了G和GxB>的父类

  • 使用通配符的情况：
public class Test1 {
    /* public void a (List<Object> list){}
        public void a (List<String> list){}
        public void a (List<Integer> list){}*/
    public void a(List< ? > list){
        //遍历
        for(Object obj:list){
            System.out.println(obj);
        }
    }
}

class T{
    public static void main(String[] args) {
        Test1 t = new Test1();
        t.a(new ArrayList<Object>());
        t.a(new ArrayList<String>());
        t.a(new ArrayList<Integer>());
    }
}
  • 通配符使用注意细节
  1. 遍历时，不能使用通配符?，而是使用Object
  2. 数据的写入操作
  3. 数据的读取操作
//1 遍历
for(Object obj:list){
    System.out.println(obj);
}
//2 数据的写入操作
//list.add("asd");--->出错，不能随意的添加数据
list.add(null);

//3 数据的读取操作
Object s = list.get(0);//必须使用Object类型读取

（4）泛型受限

  • 泛型上限：List<? extends Person>list1
  • 泛型下限：List<? super Person>list2
public class Test3 {
    public static void main(String[] args) {
        //a,b,c三个集合时并列关系
        List<Object> a = new ArrayList<>();
        List<Person> b = new ArrayList<>();
        List<Student> c = new ArrayList<>();
        /*开始使用泛型受限：泛型上限
        List<? extends Person> 是List<Person>的父类，是List<Person的子类>的父类
         */
        List<? extends Person>list1 = null;
        //list1 = a;超过上限
        list1 = b;
        list1 = c;

        /*开始使用泛型受限：泛型下限
        List<? super Person> 是List<Person>的父类，是List<Person的父类>的父类
         */
        List<? super Person>list2 = null;
        list2 = a;
        list2 = b;
        //list2 = c; 超过下限
    }
}

5 Set接口与实现类

实现类：HashSet类、TreeSet类

Set接口特点：唯一，无序（相对于List接口，不等于随机）

没有跟索引相关的方法

遍历方式：

  1. 迭代器
  2. 增强for循环

1)HashSet实现类

HashSet简要原理图： 哈希表=数组+链表；如果放入HashSet中的数据，一定要重写两个方法：hasCode，equals

HashSet底层就是利用HashMap来完成的

在这里插入图片描述

【疑问：】

  1. 数组长度是多少？初始是16，为（2^n）
  2. 数组的类型是什么？Entry类
  3. hashCode，equals方法真的调用了吗？
  4. 底层表达式是什么？
  5. 同一个位置的数据，是向前放，还是向后放？JDk1.7是上插，JDK1.8后是下插
  6. 放入数组中的数据，是直接放的吗？是否封装了对象？
import java.util.HashSet;

public class Demo01 {
    public static void main(String[] args) {
        //创建一个HashSet集合
        HashSet<Integer> hs = new HashSet<>();
        System.out.println(hs.add(12));//true
        hs.add(23);
        hs.add(34);
        hs.add(45);
        System.out.println(hs.add(12));//false,这个重复数没有放入到集合中
        hs.add(9);
        System.out.println(hs.size());
        System.out.println(hs);//Integer类型满足：唯一，无序；同理String类型也满足
        System.out.println("--------------------------");
        //自定义的引用数据类型
        HashSet<Student> s = new HashSet<>();
        s.add(new Student(16,"小华"));
        s.add(new Student(13,"小红"));
        s.add(new Student(17,"小明"));
        s.add(new Student(18,"小华"));
        s.add(new Student(10,"小笑"));
        System.out.println(s.size());
        System.out.println(s);//自定义数据类型:不唯一，无序（由于Student数据类型没有重写hasCode，equals）
    }
}

2)LinkedHashSet实现类

LinkedHashSet类实现唯一且有序

public class Demo02 {
    public static void main(String[] args) {
        //创建一个LinkedHashSet集合
        LinkedHashSet<Integer> hs = new LinkedHashSet<>();
        System.out.println(hs.add(12));//true
        hs.add(23);
        hs.add(34);
        hs.add(45);
        System.out.println(hs.add(12));//false,这个重复数没有放入到集合中
        hs.add(9);
        System.out.println(hs.size());
        System.out.println(hs);//唯一，有序 输出[12, 23, 34, 45, 9]
    }
}

3）TreeSet实现类

【1】存入Integer类型数据：（底层利用的内部比较器）

特点：唯一，无序（没有按照输入的顺序进行输出），有序（按照升序进行遍历）。

import java.util.TreeSet;

public class Demo01 {
    public static void main(String[] args) {
        //创建一个TreeSet
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(12);
        ts.add(1);
        ts.add(15);
        ts.add(12);
        ts.add(19);
        ts.add(7);
        System.out.println(ts.size());// 输出 5
        System.out.println(ts);//输出 [1, 7, 12, 15, 19]
    }
}

【2】原理：底层：二叉树（数据结构中的一个逻辑结构）

二叉树遍历：

  1. 中序遍历：左–>根–>右（当前二叉树用的方式----->升序结果）
  2. 先序遍历：根–>左->右
  3. 后序遍历：左–>右–>根

TreeSet底层原理

【3】存放String类型数据：

同Integer类型一样

【4】放入自定义类型数据

同比较器案例

  • 内部比较器实现
  • 外部比较器实现
利用外部比较器，必须自己指定
Comparator<Student> com = new Bijiao();
TreeSet<Student> ts = new TreeSet<>(com);//一旦指定外部比较器，则会按照外部比较器来比较

实际开发中利用外部比较器好，因为扩展性好（多态）

换一种写法：匿名内部类

public class Test {
    public static void main(String[] args) {
        //创建一个TreeSet:
        //匿名内部类,接口创建对象
        /*Comparator<Student> com =new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        };
         TreeSet<Student> ts = new TreeSet<>(com);
        */
        //传的都是具体类的实现对象
        /*new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        }*/
        TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge()-o2.getAge();
            }
        });
        ts.add(new Student(10,"dnana"));
        ts.add(new Student(43,"cnana"));
        ts.add(new Student(12,"anana"));
        ts.add(new Student(10,"fnana"));
        ts.add(new Student(16,"bnana"));
        ts.add(new Student(5,"hnana"));
        System.out.println(ts.size());
        System.out.println(ts);
    }
}

6 Map接口与实现类

实现类：Hashtable类、HashMap类、TreeMap类

Map<K,V>接口（键值对<Key,Value>，K：此映射维护的密钥类型；V：映射值的类型）

1）HashMap实现类

特点：无序、唯一，按照key进行总结的，因为底层key遵照哈希表的结构（数组+链表）

哈希表原理：比如放入这个集合的数据对应的那个类：必须重写hasCode方法和equals方法。

HashMap底层原理

Hashtable类与HashMap类功能一样

  • Hashtable：JDK1.0 效率低 线程安全 key不可以存放null值
  • HashMap：JDK1.2 效率高 线程不安全 key可以存放null值，并且key的null值也遵循唯一的特点

Map接口常用方法

增加：put(K key, V value)

删除：clear() remove(Object key) remove(Object key, Object value)

修改：replace(K key, V value)

查看：entry(K k, V v) entrySet() get(Object key) keySet() size() values()

判断：containsKey(Object key) containsValue(Object value) equals(Object o) isEmpty()

LinkedHashMap实现类

特点：唯一，有序（按照输入顺序进行输出）

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Map接口**常用方法**
 * 增加：`put(K key, V value)`
 * 删除：`clear()` `remove(Object key)` `remove(Object key, Object value)`
 * 修改：`replace(K key, V value)`
 * 查看：`entry(K k,  V v)`  `entrySet()` `get(Object key)` `keySet()`  `size()` `values()`
 * 判断：`containsKey(Object key)` `containsValue(Object value)`  `equals(Object o)` `isEmpty()`
 */
public class Demo01 {
    public static void main(String[] args) {
        //创建一个Map集合
        Map<String, Integer> map = new HashMap<>();
        System.out.println(map.put("lili", 12));//null
        map.put("huahua",12);
        map.put("honghong",20);
        map.put("xixi",7);
        map.put("beibei",18);
        System.out.println(map.put("lili", 16));//12
        /*map.clear();//清空*/
        /*map.remove("huahua");//移除huahua*/
        System.out.println(map.containsKey("lili"));//true
        System.out.println(map.containsValue(12));//false

        System.out.println(map.size());
        System.out.println(map);//{huahua=12, lili=16, xixi=7, beibei=18, honghong=20}
        System.out.println("------------------------------");

        Map<String, Integer> map2 = new HashMap<>();
        System.out.println(map2.put("lili", 12));//null
        map2.put("huahua",12);
        map2.put("honghong",20);
        map2.put("xixi",7);
        map2.put("beibei",18);
        System.out.println(map2.put("lili", 16));//12

        System.out.println(map == map2);//false,比较地址
        System.out.println(map.equals(map2));//true，比较集合中具体的值 是否一致

        System.out.println(map.isEmpty());//false
        System.out.println(map.get("huahua"));//12 返回value
        System.out.println("---------------获取key--------------------");
        //keySet()对集合中的key进行遍历查看
        Set<String> set = map.keySet();
        for(String s:set){
            System.out.println(s);
        }
        //values()对集合中的value进行遍历查看
        System.out.println("--------------获取value法1---------------------");
        Collection<Integer> values = map.values();
        for(Integer i:values){
            System.out.println(i);
        }
        System.out.println("----------------获取value法2-------------------");
        Set<String> set2 = map.keySet();
        for(String s:set2){
            System.out.println(map.get(s));
        }
        System.out.println("----------------entrySet()------------------");
        //entrySet()封装的Map集合的键值对
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for(Map.Entry<String, Integer>e:entries){
            System.out.println(e.getKey()+"------"+e.getValue());
        }

    }
}

HashMap实现类的重要属性：

HashMap底层源码的重要属性

HashMap实现类的构造器：
在这里插入图片描述

import java.util.HashMap;

public class Demo01 {
    public static void main(String[] args) {
        //创建一个HashMap的对象：存储的是双列数据--键值对：key-value
        HashMap<Integer, String> hm = new HashMap<>();
        //存储数据
        System.out.println(hm.put(12, "丽丽"));
        System.out.println(hm.put(15, "花花"));
        System.out.println(hm.put(5, "腾腾"));
        System.out.println(hm.put(18, "红红"));
        System.out.println(hm.put(12, "华华"));
        System.out.println(hm.put(7, "泰泰"));
        System.out.println("集合中的元素数量："+hm.size());
        System.out.println("集合中元素："+hm);
    }
}

2）TreeMap实现类

特点：唯一、有序（按照升序或降序）

大致原理图：

TreeMap原理图

原理：二叉树，key遵循二叉树的特点，放入集合的key的数据对应的类型内部一定要实现比较器（内部比较器与外部比较器，二选一）

在这里插入图片描述

【1】key的类型为String类型：

import java.util.Map;
import java.util.TreeMap;

public class Demo02 {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("axixi",1);
        map.put("fxixi",3);
        map.put("exixi",5);
        map.put("bxixi",2);
        map.put("axixi",7);
        map.put("cxixi",1);
        System.out.println(map.size());//5
        System.out.println(map);//升序，{axixi=7, bxixi=2, cxixi=1, exixi=5, fxixi=3}
    }
}

【2】key的类型为自定义类型：

（1）内部比较器

public class Student implements Comparable<Student>{
    private int age;
    private String name;
    private double height;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getHeight() {
        return height;
    }

    public void setHeight(double height) {
        this.height = height;
    }

    public Student(int age, String name, double height) {
        this.age = age;
        this.name = name;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", height=" + height +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        //年龄排序
        /*return this.getAge()-o.getAge();*/
        //按名字排序
        return this.getName().compareTo(o.getName());
    }
}
import java.util.Map;
import java.util.TreeMap;

public class Test {
    public static void main(String[] args) {
        Map<Student, Integer> map = new TreeMap<>();
        map.put(new Student(13,"axixi",160.7),1);
        map.put(new Student(19,"exixi",160.7),3);
        map.put(new Student(10,"bxixi",160.7),5);
        map.put(new Student(7,"dxixi",160.7),2);
        map.put(new Student(13,"axixi",160.7),7);
        map.put(new Student(15,"cxixi",160.7),1);
        System.out.println(map.size());
        System.out.println(map);//年龄/名字/身高升序输出
    }
}

（2）外部比较器

public class Student{
    private int age;
    private String name;
    private double height;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getHeight() {
        return height;
    }

    public void setHeight(double height) {
        this.height = height;
    }

    public Student(int age, String name, double height) {
        this.age = age;
        this.name = name;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", height=" + height +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {
        //匿名内部类的形式，使用外部比较器
        Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return ((Double)o1.getHeight()).compareTo((Double)o2.getHeight());
            }
        });
        map.put(new Student(13,"axixi",160.7),1);
        map.put(new Student(19,"exixi",150.7),3);
        map.put(new Student(10,"bxixi",167.7),5);
        map.put(new Student(7,"dxixi",135.7),2);
        map.put(new Student(13,"axixi",160.7),7);
        map.put(new Student(15,"cxixi",180.7),1);
        System.out.println(map.size());
        System.out.println(map);//年龄/名字/身高升序输出
    }
}

补充知识

1）迭代器底层原理（面试题：iterator(),Iterator,Iterable关系）

在这里插入图片描述

迭代器原理

2）hasNext(),next()的具体实现

hasNext与next实现

增强for循环 底层也是通过迭代器实现的

3）ListIterator迭代器

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.add("ee");
        //在“cc”之后添加一个字符串“kk”
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            if("cc".equals(it.next())){
                list.add("kk");//Exception in thread "main" java.util.ConcurrentModificationException
                //并发修改异常
            }
        }
    }
}

出错原因：迭代器和list同时对集合进行操作。

解决办法：事情让一个完成—>引入新的迭代器：ListIterator

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        list.add("ee");
        //在“cc”之后添加一个字符串“kk”
        /*Iterator<String> it = list.iterator();
        while(it.hasNext()){
            if("cc".equals(it.next())){
                list.add("kk");//Exception in thread "main" java.util.ConcurrentModificationException
                //并发修改异常
            }
        }*/
//引入ListIterator迭代器
        ListIterator<String> it = list.listIterator();
        while(it.hasNext()){
            if("cc".equals(it.next())){
                it.add("kk");
            }
        }
        System.out.println(it.hasNext());//false
        System.out.println(it.hasPrevious());//true
        //逆向遍历
        while(it.hasPrevious()){
            System.out.println(it.previous());
        }
        System.out.println(it.hasNext());//true
        System.out.println(it.hasPrevious());//false

        System.out.println(list);
    }
}

4）比较器

【1】以int 类型为例：

比较思路：将比较的数据做差，然后返回int类型的数据，将这个int类型的数值 按照=0 >0 <0 来做判断！

int a = 10;
int b = 20;
System.out.println((a - b));// =0  >0  <0

【2】比较String类型的数据：

String类实现了Comparable接口，这个接口中有一个抽象方法compareTo，String类重写这个方法即可

String a = "A";
String b = "B";
System.out.println(a.compareTo(b));  // =0  >0  <0

【3】比较double类型的数据:

Double类实现了Comparable接口，这个接口中有一个抽象方法compareTo

double c = 1.8;
double d = 1.5;
System.out.println(((Double) c).compareTo((Double) d));

【4】自定义类型数据比较：

外部比较器和内部比较器 哪个更好？

答：外部比较器更好，因为外部比较器使用了多态，扩展性好！

  1. 内部比较器
import java.util.Comparator;

public class Student implements Comparable<Student> {
    private int age;
    private double height;
    private String name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public double getHeight() {
        return height;
    }

    public void setHeight(double height) {
        this.height = height;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Student(int age, double height, String name) {
        this.age = age;
        this.height = height;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", height=" + height +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        //比较年龄
        /*return this.getAge() - o.getAge();*/
        //比较身高
        /*return ((Double)this.getHeight()).compareTo((Double)o.getHeight());*/
        //比较姓名
        return this.getName().compareTo(o.getName());
    }
}

public class Test {
    public static void main(String[] args) {
        Student s1 = new Student(12, 160.4, "a张三");
        Student s2 = new Student(18, 182.1, "b李四");
        System.out.println(s1.compareTo(s2));

    }
}
  1. 外部比较器
import java.util.Comparator;

public class Student{
    private int age;
    private double height;
    private String name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public double getHeight() {
        return height;
    }

    public void setHeight(double height) {
        this.height = height;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Student(int age, double height, String name) {
        this.age = age;
        this.height = height;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", height=" + height +
                ", name='" + name + '\'' +
                '}';
    }
}

class TCompare01 implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //比较年龄
        return o1.getAge()-o2.getAge();
    }
}
class TCompare02 implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //比较姓名
        return o1.getName().compareTo(o2.getName());
    }
}
class TCompare03 implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        //比较身高
        return ((Double)o1.getHeight()).compareTo((Double)o2.getHeight());
    }
}

import java.util.Comparator;

public class Test {
    public static void main(String[] args) {
        Student s1 = new Student(12, 160.4, "a张三");
        Student s2 = new Student(18, 182.1, "b李四");
        //获取外部比较器
        Comparator<Student> tc1 = new TCompare01();
        System.out.println(tc1.compare(s1, s2));

        Comparator<Student> tc2 = new TCompare02();
        System.out.println(tc2.compare(s1, s2));

        Comparator<Student> tc3 = new TCompare03();
        System.out.println(tc3.compare(s1, s2));


    }
}

5）经典面试题

  1. 填装因子，负载因子，加载因子 为什么是0.75？
  • 装填因子设置为1：空间利用率得到了很大的满足，很容易碰撞，产生链表->查询效率低
  • 装填因子设置为0.5：碰撞的概率低，扩容，产生链表的几率低，查询效率高，空间利用率太低
  • 0.5~1 取中间值：0.75
As a general rule, the default load factor (.75) offers a good
tradeoff between time and space costs.
  1. 主数组的长度为什么必须为2^n？
  • 原因1：h & (length-1) 等效于 h%length 操作，等效的前提就是：length必须是2 的倍数！
  • 原因2：防止哈希冲突，位置冲突：
验证整数倍：
length ：8
hash 3		00000011
length-1	00000111
---------------------------
与运算		  00000011 -->3位置

hash 2		00000010			不冲突
length-1	00000111
---------------------------
与运算		  00000010 -->2位置

验证非整数倍：
length ：9
hash 3		00000011
length-1	00001000
---------------------------
与运算		  00000000 -->0位置

hash 2		00000010				冲突
length-1	00001000
---------------------------
与运算		  00000000 -->0位置

资料整理于：马士兵教育

视频连接：点击进入

# java # 开发语言 # 经验分享
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊