# java数据结构

> 来源：梦飞idc云平台 | 原文：https://www.mfisp.com/22059.html | 发布：2023-07-14 | 更新：2023-07-14 | 分类：建站教程

哈希表

 

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

---
本页由 梦飞idc云平台（https://www.mfisp.com）提供。站点导航见 https://www.mfisp.com/llms.txt