数据结构相关

文章目录

• • 数据结构相关
  • @[TOC](文章目录)
  • 前言
  • 一、数据结构介绍
  • 二、不同的逻辑结构的存储方案(Java实现)
  • • 2.1 线性结构：线性表、数组
    • 2.2 线性结构：栈
    • 2.3 线性结构：队列
    • 2.4 树形结构：树
  • 三、一些常见的
  • • 3.1 布隆过滤器Bloom Filter，BF
    • 3.2 Hash

前言

数据结构的逻辑结构描述数据元素之间的逻辑关系，与数据存储无关，独立于计算机。每种逻辑结构可以使用不同的存储方式。
java中提供了一些集合的实现，如LinkedList实现了线性表的双向链表存储结构、Stack（Vector的子类）实现了栈的结构，由于Vector的底层就是Object[]数组，因此Stack的底层也是Object[]数组实现的，即使用顺序存储，而非链式存储
还有Java的一些集合底层也用到了这样的逻辑结构。
在此说明：Stack有其体现栈结构的特殊操作，但是用其父类的add()方法也不是不可以！

一、数据结构介绍

1、基本概念

• 数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合，是计算机程序加工的原料。
• 数据元素：是数据的基本单位，作为一个整体进行考虑何处理。一个数据元素有若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。如：学生记录是一个数据元素，由学号、姓名、性别等数据项组成。
• 数据对象：具有相同性质的数据元素的集合，数据的一个子集。
• 数据类型：原子：值不可再分；结构类型：其值可以再分解为若干成分的数据类型；抽象数据类型：抽象数据组织及与之相关的操作
  队列、栈属于抽象数据类型ADT，即使用数组/链表模拟出来的一个栈/队列的特征

总结：若干数据项→数据元素(数据基本单位)–相同性质集合—>数据对象
2、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种数据元素相互之间的关系称为结构。数据结构的三要素：逻辑结构、物理结构、数据的运算。一个算法的设计取决于所选定的逻辑结构，算法的实现依赖于所采用的存储结构。

• 运算结构：施加在数据上的运算包括运算的定义（针对逻辑结构，运算的功能）和实现（针对存储结构，具体步骤）
  • 分配资源，建立结构，释放资源
  • 插入、删除
  • 获取、遍历
  • 修改、排序
• 逻辑结构：数据元素之间的逻辑关系，与数据存储无关，独立于计算机。主要分为线性（线性表）、非线性结构（集合、树、图）。

  • 线性结构：一对一。如线性表、栈、队列、串、数组

    • 线性表：由n个元素组成的一个有限序列，表中的每一个元素有且只有一个前驱、后继，除根/终结点外
      顺序存储：顺序表（java中提供的实现ArrayList）
      链式存储：单链表、双链表（Java中提供了LinkedList的实现，可以直接用）、循环链表、静态链表
    • 栈
      顺序存储：顺序栈（Java中提供了顺序栈的实现Stack）
      链式存储：链式栈
    • 队列
      顺序存储：顺序队、循环队
      链式存储：链式队（Java中只提供了DeQue的接口由LinkedList实现）

  • 集合结构：同属于一个集合，集合之间没有逻辑关系。如各种各样的集合

  • 树形结构：一对多。如树、二叉树

    • 顺序存储：满/完全二叉树
    • 链式存储：传统二叉链表、线索二叉树

  • 图形结构：多对多。如各种各样的图

    • 顺序存储：邻接矩阵
    • 链式存储：十字链表(有向)、链接多重表(无向图)
    • 链式+顺序：邻接表法
• 物理/存储结构：数据元素、关系的表示，用计算机语言实现，依赖于计算机语言
  角度一：顺序结构、链式结构、索引结构、哈希结构
  角度二：线性表（一维数组、链表、栈、队列）、树（二叉树、B+树）、图（多对多）、哈希表（HashMap、HashSet)
  优缺点比较方面：空间利用率、插入、删除、访问、检索、排序
  • 顺序存储：一组连续的存储单元一次存储逻辑上相邻的各个元素。适用范围：查询操作多的场景
    • 优点：支持下标/随机访问，查询效率高，内存空间连续
    • 缺点：插入、删除引起元素移动，只能静态分配连续空间可能会造成空间的浪费
  • 链式存储：不使用连续的存储空间存放元素，每个元素一个节点（数据域、指针域-指向下一个节点的指针）。适用于插入/删除
    • 优点：插入、删除效率高，空间利用率高，存储元素无限增加
    • 缺点：额外的空间表示数据之间的存储关系，只知道下一个节点的位置，访问效率低（从头结点开始遍历）
  • 索引结构：除了建立存储节点信息外，还建立附加的索引表。索引表的每一项称为索引项，索引的一般形式：关键字、地址。
    • 优点：用节点的索引号确定节点存储位置，检索速度快
    • 缺点：插入、删除还需额外维护索引表，索引表占空间
  • 散列结构：根据元素的关键字直接计算出该元素的存储地址，又称Hash存储。
    • 优点：检索、插入、删除效率高
    • 缺点：不支持排序，占用空间更多，记录的关键字不能重复

3、算法和算法评价
算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作
算法特性：出入可行，确定很穷

• 输入：0/1/多个输入，输入来自于某个特定数据对象的集合。
• 输出：必须有输出，1/多个输出，输出是与输入有着某种特定关系的量。
• 可行性：算法中的操作都可以通过已经实现的基本运算执行有限次来实现。
• 确定性：每条指令要有确切的含义，对于相同的输入必须得到相同的输出。
• 有穷性：执行有穷步骤后结束，且每一步都在有穷时间内完成。

算法"好"目标：正确性(求解问题)、可读性、健壮性(非法数据)、效率与低存储量需求
算法效率的度量：
时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和T(n)——该算法问题规模n的函数，时间复杂度分析它的数量级。因此采用算法中基本运算的频度f(n)来分析
T(n)=O(f(n))
由于时间复杂度与问题规模、输入数据的性质有关：最好、最坏、平均时间复杂度
空间复杂度：S(n)=O(g(n))，算法所耗费的存储空间，一个程序执行过程中除了需要存储空间存放本身所用的指令、常数、变量、输入数据外，还需要对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，与算法无关，那么只分析除输入和程序之外的额外空间。
算法原地工作：指算法所需的辅助空间为常量，即O(1)。

二、不同的逻辑结构的存储方案(Java实现)

每种数据结构需要根据它的特点→使用不同的物理结构实现，定义不同的结构体，以及相关的操作
但是Java也提供了一些逻辑结构的物理实现可以直接用：LinkedList、ArrayList、Stack、TreeSet、TreeMap

2.1 线性结构：线性表、数组

1、线性表：由n个元素组成的一个有限序列，表中的每一个元素有且只有一个前驱、后继，除根/终结点外
特点：元素个数有限、逻辑上顺序性、数据类型相同、元素具有抽象性（仅考虑元素关系，不考虑是什么内容）、元素都是数据元素，每个元素都是单个元素
（1）顺序存储——顺序表：用一组地址连续的存储单元一次存储线性表中的数据元素，使得逻辑和物理都相邻
下面的特点以数组为例：用来存放同一种数据类型的集合，注意只能存放同一种数据类型。
特点：提供随机访问 并且容量有限。可以利用元素的索引（index）可以计算出该元素对应的存储地址。

• 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
• 不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢。
• 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。

假如数组的长度为 n。
访问：O（1）//访问特定位置的元素
插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

//只声明了类型和长度
数据类型[]  数组名称 = new 数据类型[数组长度];

//声明了类型，初始化赋值，大小由元素个数决定
数据类型[] 数组名称 = {数组元素1，数组元素2，......}

自定义数组Array：底层使用Object[]数组实现

//测试几个功能
@Test
public void test1() {
    Array<String> arr = new Array<>(5);
    arr.add("123");
    arr.add("345");
    arr.add("zhang");
    arr.delete("123");
    arr.update("345","789");
    arr.print();
}
//数组实现
class Array<E>{
    private Object[] elementData;//存储数据的数组
    private int size;
    //从构造器就可以看出Array数组必须要指定初始容量，并没有提供无参构造器
    public Array(int capacity){
        elementData = new Object[capacity];
    }
    public int size(){//湖区数组的大小
        return this.size;
    }
    //实现添加元素功能:满了就加不了了
    public void add(E value){
        if(size >= elementData.length){//由于数组的不可变性，已满就不能添加
            throw new RuntimeException("数组已满，不可添加");
        }
        elementData[size] = value;
        size++;
    }
    //查询元素value在数组中的索引位置
    public int find(E value){
        for (int i = 0; i < size; i++) {
            if(elementData[i] == value){
                return i;
            }
        }
        return -1;//返回-1表示不存在
    }
    //从数组中移除首次出现的value元素
    public boolean delete(E value){
        int index = find(value);
        if(index == -1){
            return false;
        }
        for (int i = index; i < size; i++) {
            elementData[i] = elementData[i+1];
        }
        elementData[size - 1] = null;//最后一个置为默认值
        size--;//别忘了size要减1
        return true;
    }
    //将数组中首次出现的oldValue元素替换为newValue
    public boolean update(E oldValue, E newValue){
        int index = find(oldValue);
        if(index == -1){
            return false;
        }
        elementData[index] = newValue;
        return true;
    }
    //遍历数组中所有的数据
    public void print(){
        System.out.print("{");
        for (int i = 0; i < size; i++) {
            if(i == size - 1){
                System.out.print(elementData[i] + "}");
                break;
            }
            System.out.print(elementData[i] + ",");
        }
    }
}

（2）链式存储——链表：通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点存放数据域、指针域(存放后继节点的地址)。链表由节点组成。
注意：各种链表的删除、插入操作，指针的修改！
链表的几种形式：单链表、双链表、循环链表。第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。
插入删除O(1)，查找O(n)

• 单链表：只有一个方向，结点只有一个后继指针 next 指向后面的节点。
  常见的操作：头插法、尾插法建立单链表、按序号查找节点值、按值查找节点、插入/删除表节点、求表长操作。
• 双链表：包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
  常见的一些操作：插入、删除，注意需要同时修改pre、next两个节点
• 循环单链表：尾结点不是指向 null，而是指向链表的头结点。
• 双向循环链表：最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
  判尾节点：某个节点p→next==L（头结点），判空：头结点的pre、next都为L头结点
• 静态链表：借助数组来描述线性表，节点也有data、next，这里的指针指的是节点的相对地址（数组下标，又称游标），需要先预分配一块连续的内存空间。

假如链表中有n个元素。
访问：O（n）//访问特定位置的元素
插入删除：O（1）//必须要要知道插入元素的位置

自定义节点（数据域、指针域），自定义单链表结构及一些相关的功能——这里定义的单链表，头结点保存数据了
通过一个一个节点新建链表有头插法、尾插法
说明：对于需要操作的数据data，需要包装成节点Node

//构建节点对象：data、next
class Node<E>{//使用泛型实现
    E data;//存放节点的值
    Node next;//存放下一个节点的地址
    Node(E data, Node next){//新建节点的时候用
        this.data = data;
        this.next = next;
    }
}
//构成单链表
//测试单独的节点的操作：添加，已知头结点的指针
@Test
public void test3() {
    Node node1 = new Node("String",null);//新建节点
    Node node2 = new Node("zzz",null);//新建节点
    node1.next = node2;
}

//还可以构建节点：每次新建一个节点，自己赋值data、next
class Node2<E>{//使用泛型实现
    E data;//存放节点的值
    Node next;//存放下一个节点的地址
    Node(){//默认的无参构造器
    }
}
//单链表类：实现add()
class Link<E>{
    Node header;//头结点，初始化为null
    private int size = 0;//初始化为0
    public int size(){
        return this.size;
    }
    //向链表中添加元素：尾插法
    void add(E data){//第一次调用add方法时，header为null
        Node addNode = new Node(data,null);//new一个节点对象，他是一个待插入当前链表中的节点
        if(header == null){//说明还没有节点
            header = addNode;
        }else{//头结点不为空，通过头结点找到当前的末尾节点，让当前末尾节点的next是新结点
            Node currentLastNode = findLast(header);
            currentLastNode.next = addNode;

        }
        size++;//每添加一个元素后，将size加1，可以获取到size的大小

    }
    //专门查找尾节点的方法，这个方法可以直接调用
    Node findLast(Node node){
        //递归出口：如果一个节点的next是null表示他就是尾节点
        if(node.next == null){//说明这个节点就是尾节点
            return node;
        }
        //能到这里说明：node不是尾节点
        return findLast(node);//递归算法
    }
    /*// 删除链表中某个数据的方法
    public void remove(Object obj){
        //略
    }

    // 修改链表中某个数据的方法
    public void modify(Object newObj){
        //略
    }*/

    // 按值查找：查找链表中某个元素的方法。——不太准确
    public int find(E value){
        Node p = header;//头节点
        //因为建立单链表是从头结点开始存的
        while(true){
        	if(p.data == value){
        		return p;
        	}
        	p = p.next;
        }
        
    }
}

调用示例

//测试单链表
@Test
public void test1() {
	//新建单链表：初始化seize=0，头结点header为null
    Link<String> link = new Link<>();
    link.add("zhangying");
    link.add("shi");
}
//测试单独的节点的操作：添加，已知头结点的指针
@Test
public void test2() {
    Node addNode = new Node("String",null);//新建节点
    Node p = header;//从头节点开始
    //找到尾节点插入addNode节点
    while(p.next != null){
    	p = p.next;
    }
    //循环结束找到p.next为null的尾节点了
    p.next = addNode;//在尾节点插入addNde节点
}

双向链表实现——java中提供了LinkedList实现双向链表，这相当于他的底层源码
这里的双向链表：头结点就是第一个节点。
注意：二叉树也是这样的结构：有两个指针域

class Node<E>{
    Node Prev;
    E data;
    Node next;

    Node(Node prev,E data, Node next){
        this.Prev = prev;
        this.data = data;
        this.next = next;
    }
}
//测试构成双链表的结构
@Test
public void test1(){
	Node node1 = new Node(null,"AA",null);
	Node node2 = new Node(node1,"AA",null);
	Node node3 = new Node(node2,"AA",null);
	node1.next = node2;
	node2.next = node3;//构成双向的
}
//实现双向链表类
class MyLinked<E> implements Iterable<E> {
    private Node first;//链表的首元素
    private Node last;//链表的尾元素
    private int total;//计算链表的长度

    //实现增加元素对象的功能：头插法
    public void add(E e) {
        //该节点的前驱指向前一个结点
        Node newNode = new Node(last, e, null);//先把节点构建出来,该节点是添加到最后，因此后继节点为null
        if (first == null) {//判断该链表是否为空
            first = newNode;//如果为空就将这个节点作为头结点
        }else{
            last.next = newNode;//如果不为空就指向新结点
        }
        last = newNode;//改变最后一个节点的位置
    }
    public void delete(E obj){
        Node find = findNode(obj);
        if(find != null){
            if(find.prev != null){
                find.prev.next = find.next;
            }else{
                first = find.next;
            }
            if(find.next != null){
                find.next.prev = find.prev;
            }else{
                last = find.prev;
            }

            find.prev = null;
            find.next = null;
            find.data = null;

            total--;
        }
    }
    private Node findNode(E obj){
        Node node = first;
        Node find = null;

        if(obj == null){
            while(node != null){
                if(node.data == null){
                    find = node;
                    break;
                }
                node = node.next;
            }
        }else{
            while(node != null){
                if(obj.equals(node.data)){
                    find = node;
                    break;
                }
                node = node.next;
            }
        }
        return find;
    }
    public boolean contains(Object obj){
        return findNode(obj) != null;
    }

    public void update(E old, E value){
        Node find = findNode(old);
        if(find != null){
            find.data = value;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E>{
        private Node<E> node = first;

        @Override
        public boolean hasNext() {
            return node!=null;
        }

        @Override
        public E next() {
            E value = node.data;
            node = node.next;
            return value;
        }
    }
}

2、数组和链表对比
数组支持随机访问，而链表不支持。
数组使用的是连续内存空间对 CPU 的缓存机制友好，链表则相反。
数组的大小固定，而链表则天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比较耗时的！

2.2 线性结构：栈

1、栈：又称为堆栈或堆叠，只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。
核心类库中的栈结构有Stack和LinkedList。其中Stack就是顺序栈，它是Vector的子类。LinkedList是链式栈。
顺序存储：顺序栈；链式存储：链式栈
体现栈结构的操作方法：peek()查看栈顶元素、pop()弹出栈、push(E e)压入栈、size()大小、empty()判空、search(E e)查看元素出现位置、clear()清栈

假设堆栈中有n个元素。
访问/搜索：O（n）//最坏情况
插入删除：O（1）//顶端插入和删除元素

2、栈的一些操作：栈顶指针是指向栈顶元素的
栈顶指针：s.top，初始设置为s.top=-1，栈顶元素s.data[s.top]（链式取值方式）
进栈push(E e)：栈顶指针(索引)先+1，再添加元素
出栈pop()：先取栈顶值，再栈顶指针(索引)-1。
判空：s.top==-1，栈满s.top==maxsize-1；栈长：stop+1。

3、关于共享栈：利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间，栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
栈空：top0=-1时0号空，top1=maxsize时1号空，
栈满：(top1-top0)=1时，为满
进栈：0号栈top0+1再赋值，1号栈top1-1再赋值；出栈相反

4、栈的应用场景：只涉及在一端插入和删除数据，并且满足后进先出
（1）实现浏览器的回退和前进功能
（2）检查符号是否成对出现：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断该字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。比如 “()”、“()[]{}”、“{[]}” 都是有效字符串，而 “(]”、“([)]” 则不是。
（3）反转字符串
（4）子程序的调用、维护函数调用、递归调用（FIB、Honi）
（5）深度优先遍历DFS
（6）CPU的中断处理

栈的实现：可以通过数组、链表实现，无论哪种方式：入栈/出栈（即插入删除）的复杂度都为O(1)
每次入站之前需要先判断栈的容量是否够用，不够的话就用Arrays.copyOf()扩容
实现功能：push(Object e)、ensureCapacity()、pop()、peek()、peek()、isEmpty()、size()

//自定义栈：顺序栈
class MyStack{
    private Object[] elements;//用来存放元素
    private int index;//用来记录索引
    private int capacity;//记录栈的容量
    private static final int GROW_FACTOR = 2;//全局静态常量，每次自动扩容2倍
    public MyStack(){
        this.capacity = 8;
        //默认初始化容量是10
        this.elements = new Object[8];
        index = -1;//表示当前没有元素
    }
    //入栈操作
    public void push(Object obj){
        if(index == elements.length){
            //扩容
            ensureCapacity();
        }
        index++;//先移动栈顶指针/索引，再添加元素
        elements[index] = obj;//每次栈顶指针指向栈顶元素
    }
    //扩容：只给自己内部使用，外部无需调用，每次扩容2倍
    private void ensureCapacity(){
        int newCapacity = capacity * GROW_FACTOR;
        elements = Arrays.copyOf(elements, newCapacity);
        capacity = newCapacity;
    }
    //出栈：每取出一个元素，栈帧向下移动一位
    public Object pop() throws Exception{
        if(index < 0){
            //栈空抛出异常
            throw new Exception("弹栈失败，栈已空！");
        }
        Object obj = elements[index];//先取栈顶值，再移动栈顶指针
        elements[index] = null;
        index--;
        return obj;
    }
}

java中实现栈的集合的操作：LinkedList、Stack

public class TestStack {
    //测试Stack
    @Test
    public void test1(){
        Stack<Integer> list = new Stack<>();
        list.push(1);
        list.push(2);
        list.push(3);

        System.out.println("list = " + list);

        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());
        System.out.println("list.peek()=" + list.peek());

		System.out.println("list.pop() =" + list.pop());
		System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
        while(!list.empty()){
            System.out.println("list.pop() =" + list.pop());
        }
    }

    //测试LinkedList
    @Test
    public void test2(){
        LinkedList<Integer> list = new LinkedList<>();
        list.push(1);
        list.push(2);
        list.push(3);
        System.out.println("list = " + list);
        System.out.println("list.peek()=" + list.peek());

		System.out.println("list.pop() =" + list.pop());
		System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
        while(!list.isEmpty()){
            System.out.println("list.pop() =" + list.pop());
        }
    }
}

2.3 线性结构：队列

1、队列（Queue）：先进先出 (FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue。

假设队列中有n个元素。
访问：O（n）//最坏情况
插入删除：O（1）//后端插入前端删除元素

2、队列常见的一些操作：队尾指针rear指向队尾元素的下一个位置，队头指向队头元素（不同的地方要求可能不一样，根据实际情况实现入队、出队）→为了避免当只有一个元素时处理麻烦就这样涉及，当rear=font时队列为空。
入队EnQueue(E e)：从队尾入，先送值到队尾，再将队尾指针+1
出队DeQueue()；从队头出，先取队头值，再将队头指针+1
“假溢出”：Q.rear = = maxsize，即出现上溢出，data数组中任然存在可以存放元素的空位置→解决办法循环队列

3、循环队列：解决顺序队列和假溢出问题，即从头开始，形成头尾相接的循环
解决法1：设计队列时保证数组还有一个空闲的位置（即队尾指针指向队尾元素的下一个位置）
判断队列是否为满：(rear+1) % queueSize = = front；判断队空：front = = rear
解决法2：设置一个标志变量flag
队满：rear==front，flag=1；队空flas=0。

4、双端队列双端队列 (Deque) ：一种在队列的两端都可以进行插入和删除操作的队列，相比单队列来说更加灵活。一般来说，我们可以对双端队列进行 addFirst、addLast、removeFirst 和 removeLast 操作。

5、优先队列：从底层结构上来讲并非线性的数据结构，它一般是由堆来实现的。
入队：将新元素其插入堆中并调整堆；队头出队：返回堆顶元素并调整堆。
不论进行什么操作，优先队列都能按照某种排序方式进行一系列堆的相关操作，从而保证整个集合的有序性。虽然优先队列的底层并非严格的线性结构，但是在使用的过程中，是感知不到堆的，从使用者的眼中优先队列可以被认为是一种线性的数据结构：一种会自动排序的线性队列。

6、队列的应用场景
（1）图形的广度优先查找法(BFS)
（2）CPU的作业调度、阻塞队列、线程池中的请求/任务队列、Linux内核进程队列
（3）用于计算机各种事件处理的模拟，如事件队列、消息队列
（4）栈：双端队列天生便可以实现栈的全部功能（push、pop 和 peek），并且在 Deque 接口中已经实现了相关方法。Stack 类已经和 Vector 一样被遗弃，现在在 Java 中普遍使用双端队列（Deque）来实现栈。
（5）层次遍历

实现队列的定义及相关操作——使用数组实现

class Queue {
    Object[] values;
    int size;//记录存储的元素的个数
    public Queue(int length) {
        values = new Object[length];
    }
    public void add(Object ele) { //添加
        if (size >= values.length) {
            throw new RuntimeException("队列已满，添加失败");
        }
        values[size] = ele;
        size++;
    }
    public Object get() { //获取
        if (size <= 0) {
            throw new RuntimeException("队列已空，获取失败");
        }
        Object obj = values[0];
        //数据前移
        for (int i = 0; i < size - 1; i++) {
            values[i] = values[i + 1];
        }
        //最后一个元素置空
        values[size-1]= null;
        size--;
        return obj;
    }
}

2.4 树形结构：树

1、一些概念
结点：树中的数据元素都称之为结点；
根节点：最上面的结点称之为根。每个结点都可以认为是其子树的根
父节点：结点的上层结点；子节点：节点的下层结点；兄弟节点：具有相同父节点的结点称为兄弟节点
结点的度数：每个结点所拥有的子树的个数称之为结点的度
树叶：度数为0的结点，也叫作终端结点
非终端节点（或分支节点）：树叶以外的节点，或度数不为0的节点。
树的深度（或高度）：树中结点的最大层次数
结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1
同代：在同一棵树中具有相同层数的节点

2、树的性质：
树中节点数等于所有节点的度数之和加1
度为m的树中第i层上最多m^i-1 个节点(i>=1)
高为h的m叉树最多有(m^h -1)/(m-1)个节点
具有n个结点的m叉树的最小高度为log_m (n(m-1)+1)取上界

二叉树节点的构造

//二叉树
class TreeNode{
	TreeNode left;
	Object data;
	TreeNode right;
	public TreeNode(Object data){
		this.data = data;
	}
	public TreeNode(TreeNode left,Object data,TreeNode right){
	this.left = left;
	this.data = data;
	this.right = right;
	}
}
//创建对象
创建对象:
TreeNode node1 = new TreeNode(null,"AA",nuLL);
TreeNode leftNode = new TreeNode(null,"BB",null);
TreeNode rightNode = new TreeNode(null,"Cc",null);
nodel.left = leftNode;
node1.right = rightNode;

//或者：树节点
public class BinaryTree<E>{
    private TreeNode root; //二叉树的根结点
    private int total;//结点总个数
    
    private class TreeNode{
        //至少有以下几个部分
        TreeNode parent;
        TreeNode left;
        E data;
        TreeNode right;
        public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {
            this.parent = parent;
            this.left = left;
            this.data = data;
            this.right = right;
        }
	}
}
//创建对象
TreeNode leftNode = new TreeNode(nodel,null,"BB",null);
TreeNode rightNode = new TreeNode(nodel,null,"Cc",null);
nodel.left = leftNode,nodel.right = rightNode;

3、二叉树：每个结点最多只能有两棵子树，且有左右之分。
二叉树的性质：n₀ = n₂ +1（n =n₀ +n₁ +n₂ ，且n=分支数量+1=n₁ +2n₂ 于是得到这个结论）
非空二叉树上第k层最多有2^k-1 个节点（k>=1）
高度为h的二叉树最多有2^h -1个节点(h>=1)
具有n个节点的完全二叉树的高度为log₂(n+1)取上界，log₂ n+1取下界

二叉树的遍历：

• 先序：先输出根结点，再遍历左子树，最后遍历右子树，遍历左子树和右子树的时候，同样遵循先序遍历的规则
• 中序：先递归中序遍历左子树，再输出根结点的值，再递归中序遍历右子树
• 后续：先递归后序遍历左子树，再递归后序遍历右子树，最后输出根结点的值
• 层次遍历。

//先序遍历
public void preOrder(TreeNode root){
	//递归出口
	if(root == null){//每次都是先遍历根节点
		return;
	}
	System.out.print(root.data);//先输出根节点的值
	preOrder(root.left);//先遍历左子树
	preOrder(root.right);//再遍历右子树
}
//中序遍历
public void inOrder(TreeNode root){
	if(root == null){
		return;
	}
	inOrder(root.left);
	system.out.println(root.data);
	inOrder(root.right);
}
//后续遍历
public void postOrder(TreeNode root){
	if(root == null){
		return;
	}
 postOrder(root.left);
	postOrder(root.right);
	system.out.println(root.data);
}

4、几个特殊的二叉树：满二叉树、完全二叉树、二叉排序树(二叉查找树)、平衡二叉树
二叉排序树会退化成单链表的形式→平衡二叉树（LL、RR、LR、RL）

• 其一：满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2^n-1，总的结点个数是2ⁿ-1
• 其二：完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。
• 其三：二叉排序/查找/搜索树BST：左子树<根节点的值<右子树；其中左、右子树也分别为二叉排序/查找/搜索树。查找效率O(logn)
  缺点：如果节点按升序/降序方式插入，那么其会退化成一个线性结构
  建立在BST二叉搜索树的基础上，红黑树、AVL、2-3树都是自平衡二叉树(统称B-树)、替罪羊树、Treap、伸展树
• 其四：平衡二叉树AVL：特殊的二叉排序树，其左右两个子树的高度差的绝对值不超过1；左右两个子树也都是一棵平衡二叉树。在定义AVL树结构时，需要定义一个"height"保存每一个节点的高度。
  目的：减少二叉查找树的层次，提高查找速度。
  缺点：为了保持平衡性，每次插入/删除后都需要进行平衡操作（LL-右单、RR-左单、LR、RL），计算开销会变大。
  在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO，是一项耗时的操作。
  进行下面操作时：重要的是找到插入路径上离插入节点最近的平衡因子大于1的节点A，只需要找到什么导致该节点的不平衡的"xx孩子xx子树"，具体子树的左右子树插入不影响。
  • LL平衡旋转（右单旋转）：由于节点A的左孩子的左子树上插入了新节点，导致以A为根的子树失去了平衡。操作：将A节点向右下旋转成为B的右子树的根节点，B原来的右子树成为A节点的左子树。(用右孩子补偿A)
  • RR平衡旋转（左单旋转）：由于节点A的右孩子的右子树上插入了新节点，导致不平衡。操作：将A向左下旋转称为B的左子树的根节点，B原来的左子树成为A的右子树。(用左孩子补偿A)
  • LR平衡旋转（先左单旋后右单旋）：由于节点A的左孩子的右子树上插入了新节点，导致不平衡。操作：A左孩子B的右子树根节点C左旋（即RR操作）到B位置然后把C节点右旋（即LL）到A节点位置
  • RL平衡旋转（先右单旋后左单旋）：由于节点A的右孩子的左子树上插入了新节点，导致不平衡。操作：LR相反
    
• 其五：红黑树：一种自平衡二叉查找树，查找/插入/删除O(logn)，n指树中元素数目。红黑树的叶子节点为空NULL/NIL（不存放数据，红黑树）
  特性：①根节点是黑色；②叶子节点都是黑色的空节点（NIL节点）；③不连续的红色节点：如果节点是红色那么其子节点必须是黑色（反之不一定）；④相同的黑色高度：任意节点到叶子节点的每条路径上黑色节点数目相同——红黑树的高度不会超过2log(n+1)。
  每个节点非红即黑，黑色决定平衡，红色决定不平衡，相较于AVL树，红黑树只需要保证黑色节点平衡即可，但是这也会带来一个问题——导致树高，多需要多次IO才能查询到。
  优点：插入、删除效率都很高。
  
  当插入或删除节点时，可能会破坏已有的红黑树，处理方式：recolor ：将某个节点变红或变黑、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）
  （1）左倾、右倾染色：插入节点（红色）有父亲、叔叔都是红色
  当前节点的爷爷、父亲、叔叔节点，先把父亲、叔叔节点染黑，爷爷节点染红，当平衡树高操作后会把根节点染黑（对应上该子树的根节点是黑色）
  （2）左旋、右旋调整：染色后，黑色不平衡→旋转调节。情景：插入节点（红色）有父亲红色，没有叔叔
  RR：当前节点的父染黑，爷爷染红→左旋；RL：先右旋→当前节点的父染黑，爷爷染红→左旋
  LL：当前节点的父染黑，爷爷染红→右旋；LR：先左旋→当前节点的父染黑，爷爷染红→右旋
  
  

红黑树定义

public class Node {
    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;
    // AVL 树所需属性
    public int height;
    // 红黑树所需属性
    public Color color = Color.RED;
}

TreeMap红黑树的定义
·TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。·

public class TreeMap<K,V> {
    private transient Entry<K,V> root;
    private transient int size = 0;
    
	static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
}

• 其六：B树（Balance）：B树也称B-树，全称多路平衡查找树。大部分数据库系统及文件系统采用(IO少)。
  关于m阶B树：所有节点的孩子个数的最大值称为B树的阶m
  

  • 特点：
    • 具有n个关键字的节点含有n+1棵子树
    • 非叶的根节点：1≤关键字≤m-1，2≤子树≤m
    • 除根节点外的所有非叶子节点：（取上界）m/2-1≤关键字≤m-1，（取上界）m/2≤子树≤m，叶子节点没有子树但其关键字与之一致
    • 所有非叶节点的结构如下：K_i （i=1…n）表示关键字，P_i (i=0,1…n)表示指向子树根节点的指针。P_i-1 所指子树中所有节点均小于K_i ，所有P_i 所指子树中所有节点均大于K_i 。n表示一个节点中关键字的个数，（取上界）m/2-1≤n≤m-1。
      | n | P₀ | K₁ | P₁ | K₂ | P₂ | … | K_n | P_n |
  • 插入关键字：定位→插入—关键字个数不符合→调整，保证插入关键字后，节点中的关键字要≤m-1
    调整分裂：将插入的节点分裂为三个部分（①左，②取上界的m/2，③右），将①放在原节点中，将②插入原节点的父结点中，③放到新结点，如果这导致了父结点的关键字个数超过上限，那么再将父节点按照同样的方式分类。
  • 删除关键字：保证删除关键字后，节点中关键字个数≥m/2-1的上界。
    删除非终端节点的关键字：用前驱/后继k’来代替，最后关键字必然落在某个终端节点中，接下来讨论当删除的关键字在终端节点中时
    删除终端节点的关键字：①直接删除；②兄弟够借：左/右兄弟及其双亲结点——父子换位法达到新平衡；③兄弟不够借：与左/右兄弟节点合并+双亲节点中的一个关键字

• 其七：B+树：是 B 树的一种变体

  • m阶B+树的特点：
    - 具有n个关键字的节点含有n棵子树
    - 非叶的根节点：2≤关键字≤m，2≤子树≤m
    - 除根节点外的所有非叶子节点：（取上界）m/2≤关键字≤m，（取上界）m/2≤子树≤m，叶子节点没有子树但其关键字与之一致
    - 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
    - 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。
  • 删除/插入：与B树比较类似
  • 查找：在查找过程中，非叶结点上的关键字等于给定值时并不终止，而是继续向下查找，直到叶结点上的关键字为止，因此在B+树中，无论查找是否成功，每次查找都是从根节点稻叶结点的路径。
    

B树&B+树对比：

• 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点，所有非叶节点仅起索引作用，每个索引项只含有对应子树的最大关键字和指向孩子树的指针，不含有该关键字对应记录的存储地址。
• 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有几个关键字的结点含有n+1棵子树。
• 在 B+树中，每个结点(非根内部结点)的关键字个数的范围是（取上界）m/2≤n≤m（根结点2≤n≤m）；在B树中，每个结点(非根内部结点)的关键字个数n的范围是（取上界）m/2-1≤n≤m-1（根节点1≤n≤m-1）
• 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储
• 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中;而在B树中，叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是地址。
• 在B树中，叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的。
• B+树只有叶子节点存，其他内节点只存放 key。B树的所有节点存放key、data
• B 树的叶子节点独立的，B+树相邻叶子节点之间有引用链。
• B 树的检索：对范围内的每个节点的关键字做二分查找，可以不到叶子节点。B+树检索：从根节点到叶子节点，叶子节点的顺序检索。
• B 树中范围查询：首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；
• B+树的范围查询：对链表进行遍历即可
• B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构

三、一些常见的

3.1 布隆过滤器Bloom Filter，BF

作用：一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率（存在会误判，但是不存在不会）和删除难度（比如缓存穿透、海量数据去重）
1、定义：二进制向量（或位bit数组）+ 哈希函数（一系列随机映射函数） = 组成的数据结构。相比于 List、Map、Set 等数据结构，占用空间更少且效率更高，但是其返回的结果是概率性的，不是非常准确，数据不容易删除。
使用位数组存储所有数据，每个元素占1bit（0表false，1表true）。如果申请一个100w个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 KB ≈ 122KB 的空间。

2、布隆过滤器原理

• 添加元素：计算元素值的哈希值（使用Bloom中的哈希函数），有几个哈希函数就得到几个哈希值，根据得到的哈希值，在位数组中把对应下标的值置为1。
• 判断元素是否存在：对给定元素再次进行相同的哈希计算，得到哈希值，判断位数组中对应的几个哈希值是否都为1，但凡有一个不是说明不存在。
  

3、使用场景：

• 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，上亿）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤（判断一个邮件地址是否在垃圾邮件列表中）、黑名单功能（判断一个 IP 地址或手机号码是否在黑名单中）等等。
• 去重：比如爬给定网址的时候对已经爬取过的 URL 去重、对巨量的 QQ 号/订单号去重。去重场景也需要用到判断给定数据是否存在，因此布隆过滤器主要是为了解决海量数据的存在性问题。

4、布隆过滤器的实现：
（1）自定义布隆过滤器：体验布隆过滤器的原理

具体实现：①合适大小的位数组；②几个不同的哈希函数；③添加元素到位数组（布隆过滤器中）；④判断元素是否存在位数组（布隆过滤器中）

import java.util.BitSet;
public class MyBloomFilter{
    private static final int DEFAULT_SIZE = 2 << 24;//位数组的大小
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};//哈希函数的个数
    private BitSet bits = new BitSet(DEFAULT_SIZE);//位数组，并指定容量大小
    private SimpleHash[] func = new SimpleHash[SEEDS.length];//hash函数类的数组
    //初始化多个包含hash函数的类的数组
    public MyBloomFilter(){
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE,SEEDS[i]);
        }
    }
    //添加元素到位数组
    public void add(Object value){
        for(SimpleHash f : func){
            bits.set(f.hash(value),true);//计算出位置然后在对应的bits数组中将其设置为true即1
        }
    }
    //判定元素是否存在于为数组中
    public boolean contains(Object value){
        boolean ret = true;
        for(SimpleHash f : func){
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }
    //静态内部类：用于hash操作
    public static class SimpleHash{
        private int cap;//hash数组容量
        private int seed;
        //提供构造器
        public SimpleHash(int cap, int seed){
            this.cap = cap;
            this.seed = seed;
        }

        //计算hash值
        public int hash(Object value){
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}

（2）利用Google开源的Guava中自带的布隆过滤器
缺陷：只能单机使用，不易扩展容量

导入Guava的依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>

创建布隆过滤器，可以容忍的误判的概率：0.01
当 mightContain() 方法返回 true 时，我们可以 99％确定该元素在过滤器中，当过滤器返回 false 时，我们可以 100％确定该元素不存在于过滤器中。

// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(),
    1500,
    0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

（3）Redis中的布隆过滤器：适用于互联网的分布式场景

3.2 Hash