java数据结构

哈希表

就是一个链表数组（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个近乎有序的数（测试数据敏感度）
    判断数组是否是升序集合（测试排序算法是否正确）
    测试赛排序性能-完全相同数据下不同算法耗时情况