# java数据结构

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

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中插入一个新元素,这个元素一定是叶子结点位置插入！}）

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