哈希表

就是一个链表数组（Node[]） **在10w数量级上，哈希表的性能要优于红黑树

    广义
    理论
    处理方式（开散列 闭散列）
    考点：四个角度解析源码（21.1.18）：{
        成员变量：数据结构，树化阈值
        构造函数：Lazy-Load hash方法
        Put与get流程
        哈希算法，扩容，性能}

***JDK8之后，HashMap引入了红黑树，当一个链表的长度超过一个值(最小容量64)时，就会“树化”，将链表转为红黑树（就会进一步降低查找的时间复杂度 O(n）->O(logn)
七大排序

排序的稳定性：待排序的序列中若存在值相等的元素，经过排序之后，相等元素之间的原有先后顺序保持不变，就叫稳定的排序算法

（基于比较【直接把两个元素进行大小比较的排序：内部排序，将数据都在内存中操作】）

//外部排序：需要借助硬盘等辅助存储介质进行的排序操作（大数据排序，数据大到内存放不下：桶排序（基于归并思想），技术排序，基数排序）

插入图

    堆排序（heapSort）
    冒泡排序（bubbleSort）
    选择排序（）：每次在一组待排序的数据中选择最大（最小值）的一个元素，存放在无序区间的最后或者最前，知道全部待排序元素排列完(所有排序算法，一定要注意变量和区间的严格定义)>>优化为双向选择排序  不稳定
    插入排序（）：打扑克>>天然的插入排序 （直接插入排序+折半插入排序【二分查找法（有序区间）】）
    希尔排序（）：缩小增量排序>>先选定一个整数gap，将待排序的数据中所有记录按gap分组。所有距离为gap的数据放在同一组，将组内元素排序。然后不断缩小gap的大小，直到变为1，当gap变为1时，整个数据已经近乎有序（直接插入最好的情况），调用剖同插入排序统一排序即可 不稳定
    归并排序（）：将集合分为两大阶段 ：归&并 稳定
    快速排序（）：选取一个分区点（基准值），将数组分为三部分，基准值之前的数组<基准值<大于基准值，重复快排过程 不稳定

辅助测试：

    生成n个随机数的方法
    生成n个近乎有序的数（测试数据敏感度）
    判断数组是否是升序集合（测试排序算法是否正确）
    测试赛排序性能-完全相同数据下不同算法耗时情况

Java中元素的大小比较

    equals-Object 类：默认比较两个对象地址是否相等
    Comparable接口： return > 0 标志当前对象 > 0

Return = 0 表示当前对象= 0

Return < 0 表示当前对象< 0

    Comparator:接口(更灵活)：对原来Student类无影响 可以实现无数种比较———策略模式

return =0  o1 =o2

Return > 0 o1 >o2;

Return < 0 o1 <o2

Java.lang.Comparable:一个类实现了这个接口，就说明该类具备了可比较的能力

Public int compareTo(Object o):当前对象和传入对象o比较（死板）

Java.lang.Comparator：比较器。Student类无需事先此接口，专门的比较Student的类大小关系实现此皆苦，这种类称为比较器

Public int compare(Object o1,Object o2):比较o1和o2的大小

AgeSec

AgeDesc
优先级队列&TopK

    PriorityQueue优先级队列(基于堆)：满足队列的三大操作：

入队offer：调用堆的add方法

出队poll：按照优先级出队，最高先出调用堆的extractMax()

查看队首元素peek：查看堆顶元素

操作系统的作业调度（JDK的PriorityQueue基于最小堆实现,需要调整为最大堆（原o1-o2改为o2-o1）2）

    TopK问题：取大构建小堆 取小构建大堆

时间复杂度 O（nlogk）

       空间复杂度 O（k）

两种解决思路：1.排序法Nlogn 2.优先级队列 nlogk 3.最优解 ：快排partition思想O（n）
Map和BST

二叉树：理论基础

二分搜索树——TreeMap(红黑树，二分搜索树)

哈希表——HashSet,HashMap

    Map和Set:

set存储不重复的线性表——若只是判断元素是否存在，或者过滤重复元素，使用Set集合

Map:存储的数据是一种映射关系：需要根据不重复的key对应value，需要使用Map集合

**，Map和Set是一种专门用来进行搜索的容器或者数据结构，其搜索德效率 与具体的实例化子类有关。****

尽量不要使用Map和Set集合进行遍历，对于这俩集合的遍历操作是效率比较低的操作。使用Set和Map集合的核心操作在于搜索

    Map集合的常用操作：

    Map集合内部的元素之间的先后顺序与插入顺序关系不大（put(key,value）
    根据Key 取得value: get(key) getOrDefault（key,dafaultValue）
    Map集合中删除元素 ：remove(key)
    Map集合的遍历：（不到万不得已，不要使用）：collection 接口及其子类可以很方便的使用for_each循环进行遍历，但是Map和Collection几个没有任何关系：keySet(); values();entrySet()【Set<map.Entry<K,V>> entrySet()】
    Map集合的搜索 contains方法在Map中是非常高效的

（HashMap中接近O(1)）TreeMap中接近O（logN）

    Set集合的使用，等同于List,都是Collection的子接口 最常用Set集合的场景，（元素去重）

***Map 存映射 Set存不重复元素，用于去重***

    二分搜索树（BST）

    核心操作在于查找 3 {1.是个二叉树；2,。所有节点值满足：根节点 }左子树的所有节点，根节点<右子树的所有节点，此处不考虑等于的情况（JDK中的BST没有重复元素3；存储的元素必须具备可比较性，Comparable或者传入Comparator）
    规律：{1,；中序遍历得到的结果就是一个升序集合 2.源于最小最大值 最小值：第一个node.left==null 最大值：第一个node.right == null；3.在BST中插入一个新元素,这个元素一定是叶子结点位置插入！}）