数据结构Java--8

二叉搜索树

像上图这样满足,任意一棵子树左子树小于该子树的根结点右子树大于该子树的根结点,满足这样的条件,则这种树就被称为二叉搜索树。

public class BinarySearchTree {static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root = null;public boolean search(int val) {TreeNode cur = root;while(cur!=null){if(cur.val > val){cur = cur.left;}else if(cur.val < val) {cur = cur.right;}else{return true ;}}return false;}public void insert(int val) {TreeNode node = new TreeNode(val);if(root==null){root=node;return;}TreeNode cur = root;TreeNode parent = null;while(cur!=null){parent = cur;if(cur.val>val){cur=cur.left;}else if(cur.val<val){cur=cur.right;}else{return;}}if(parent.val>val){parent.left = node;}else if(parent.val<val) {parent.right = node;}}public void remove(int val){if(root==null){return;}TreeNode cur = root;TreeNode parent = null;while(cur!=null) {if(cur.val>val){parent=cur;cur=cur.left;}else if(cur.val<val){parent=cur;cur=cur.right;}else{removeNode(parent,cur);}}}private void removeNode(TreeNode parent,TreeNode cur) {if(cur.left == null) {//以cur为根左树为空的情况if(cur==root){//parent和cur在一起(顶根为要删除的节点时)root=cur.right;}else if(cur==parent.left){//cur为要删除元素并且走到了parent左边,cur左边为空,把parent的左边接上cur的右边parent.left=cur.right;}else{//cur为要删除元素并且走到了parent右边,cur左边为空,把parent的右边接上cur的右边parent.right=cur.right;}} else if (cur.right == null) {//以cur为根右树为空的情况if(cur==root){root=cur.left;}else if(cur==parent.left){parent.left=cur.left;}else{parent.right=cur.left;}}else{//cur左右都不为空的情况************TreeNode targetParent = cur;TreeNode target = cur.left;while(target.right!=null){targetParent = target;target = target.right;}cur.val=target.val;if(target==targetParent.right){targetParent.right=target.left;}else{targetParent.left=target.left;}}}
}

二叉搜索树的模拟只要遵循二叉搜索树的特性即可。

单支的二叉搜索树

如果插入的顺序不恰当,二叉搜索树就会出现只有单支的情况

这样也属于二叉搜索树,但是由于另一半枝没有放入元素,我们对该种搜索树进行操作时,效率必然会有所下降。

Map和Set

先了解一下Map和Set的概念,以及两者的区别。

首先这两种集合是高效的搜索容器,很适合动态查找,不同于我们以前学过的其他数据结构,那些数据结构进行动态查找都需要不小的时间复杂度。

Map是一种Key-Value模型,kv模型的意思就是,如果你往里面存放数据,那就需要提供key 和 value的值,我们也称这种模型为键值对模型。例如我们要统计某单词在英语试卷中出现的次数,

<单词,单词出现的次数>对应的就是 Key 和 Value

Set是一种Key模型,如果你往里面存放数据,只需要提供一个数据Key,但是Set不允许有重复的数据,所以Set更偏向于去重,查找是否存在目标数据

TreeMap

TreeMap就是结合了刚刚提到的KeyValue模型和搜索树,实际上TreeMap底层是红黑树,现阶段还没学到红黑树,这里不细说它的结构

Map<String,Integer> map = new TreeMap<>();
TreeMap<String,Integer> map2 = new TreeMap<>();

创建一个TreeMap有以上两种格式,推荐使用第一种

Map有几个核心的方法

public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();//key value typeTreeMap<String,Integer> map2 = new TreeMap<>();map.put("b",3);map.put("c",2);map.put("v",5);int val = map.getOrDefault("d",-1);//如果存在key就返回key的value,不存在就返回Default(-1)System.out.println(val);val = map.get("c");System.out.println(val);Set<String> set = map.keySet();//收集keyCollection<Integer> collection=map.values();//收集valueSet<Map.Entry<String,Integer>> entries = map.entrySet();//搜索树上每一个节点放的都是Map.Entryfor (Map.Entry<String,Integer> entry :entries) {System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());}for (Map.Entry<String,Integer> entry :map.entrySet()) {System.out.println(entry.getKey()+entry.getValue());}
}

TreeSet

Set是纯Key模型,适合查找存在

    public static void main(String[] args) {Set<String> set = new TreeSet<>();set.add("a");set.add("g");set.add("tq");set.remove("a");boolean flag =set.contains("g");System.out.println(flag);System.out.println(set);}
    public static void main(String[] args) {Set<String> set = new TreeSet<>();set.add("a");set.add("g");set.add("tq");set.add("a");
//        set.remove("a");boolean flag =set.contains("g");System.out.println(flag);System.out.println(set);}

TreeSet的底层也是红黑树

哈希表

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较。

顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2(N) ),搜索的效率取决于搜索过程中 元素的比较次数。

但是哈希表不一样,哈希表可以不经过任何比较,一次直接从表中得到要搜索的元素。

冲突

要明白什么是哈希表的冲突之前,不防这样设想一下,假若有5个数据,他的范围在1到10之间

这个时候我们不难发现,如果创建一个带有1到10下标的表格把对应数据存放起来,这样一来我们将来要找目标数据的时候就会很方便,只需要对应下标就可以找到。

但是如果保持5个数据数量不变的情况下,但是把范围改变至1到20,并且这个时候我们不能把表进行扩容

假若这个时候指定规则,不管目标数据为个位数还是十位数,数据的个位数是什么我们就放到什么位置,这个时候我们把12放到2下标的位置,表的内容就产生了冲突

哈希函数

针对冲突的发生,又引出了一个概念,哈希函数可以有很多种,举个常见的,线性函数,比如:        Hash(Key)= A*Key + B ,但是大多数情况下,我们使用除留余数法,函数为:                           Hash(Key)= Key % 表长

负载因子

散列表的负载因子=元素个数/表长,通常来说负载因子越小,冲突的概率越低,就像马路一样,如果马路越宽,那么堵车的可能性也会变低。我们通常扩展列表的长度来使得负载因子扩展,通常情况下,如果负载因子达到了0.75,我们就要对散列表进行扩容

解决冲突

既然有了哈希函数,并且产生了冲突,那我们就要解决冲突,解决冲突可以分为两种方式,开散列和闭散列。

首先来说说闭散列,闭散列我们通常采用线性探测的方式来解决冲突,按上面的例子来简单说就是,12得到的结果是2要放在2的位置,但是2已经有了数据,这个时候我们就把12放到下一个为空的位置

这种解决方式虽然简单粗暴,但是必然会影响查找的时间复杂度,以为增加后续可能发生的冲突

所以我们就要用开散列的方法

哈希桶

哈希表的底层就是哈希桶,哈希桶是什么呢?哈希桶就是在前面我们画的表格的基础上,每一个表格都宽展出一个链表,使得一个下标能存放更多的数据

public class HashBucket {//哈系桶是哈希查找的关键static class Node{public int key;public int value;public Node next;public Node(int key,int value){this.key = key;this.value = value;}}public Node[] array;public int usedSize;public HashBucket() {array = new Node[10];}public void putLast (int key,int value){//尾插法,这里的尾差指的是,在表对应的位置上,对链表结构进行尾插int index = key % array.length;Node node = new Node(key,value);if(array[index] == null){//第一次插入array[index] = node;usedSize++;if(loadFactor() >=0.75){resize();}return;}Node cur = array[index];//若不是第一次插入,则进行尾插while(cur.next!=null){//尾插cur = cur.next;}cur.next = node;usedSize++;if(loadFactor() >= 0.75){resize();}}public void putFirst (int key , int value) {int index = key % array.length;Node node = new Node(key,value);Node cur = array[index];//先遍历一遍链表结构,检查是否存在当前的keywhile(cur!=null){if(cur.key==key){cur.value = value;//若存在当前key,则把当前的value更新掉return;}}node.next = array[index];array[index] = node;usedSize++;if(loadFactor() >= 0.75){resize();}}private double loadFactor() {//算负载因子return usedSize*1.0/array.length;}private void resize(){//如果负载因子大于0.75就对表进行扩容Node[] tempArray = new Node[array.length*2];for (int i = 0; i < array.length; i++) {//遍历原来的表Node cur = array[i];while(cur != null) {//找到非空的表位Node curNext = cur.next;//先记录下表位的next,后续会对next进行修改,所以要进行next的备份int newIndex = cur.key % tempArray.length;//算出表位链表上的key对应新表的位置,如13%20=13,就找到13位置cur.next = tempArray[newIndex];//头插到新表里,这样就把key:13从链表中分离出来了tempArray[newIndex] = cur;cur = curNext;//遍历表位的链表}}array=tempArray;//覆盖旧表}public int get(int key) {int index = key % array.length;Node cur = array[index];while(cur!=null){if(cur.key == key){return cur.value;}cur = cur.next;}return -1;}
}

HashMap

public class TestHashMap {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("你好",1);map.put("再见",2);map.put("嗨",3);System.out.println(map.containsKey("你好"));System.out.println(map.containsValue(3));System.out.println(map.get("你好"));System.out.println(map);}
}

和TreeMap的方法种类没有区别,但是底层结构上有所区别,HashMap的底层是哈希桶(HashBucket),TreeMap的底层是红黑树。从先阶段的简单层面来说,可以把HashMap理解成一个两行的列表

Key和Value的类型可以自己定义,可以是<String,Integer>,也可以是<String,String>,这一点在某些算法中有所体现。

HashSet

public class TestHashSet {public static void main(String[] args) {Set<Integer> set = new HashSet<>();set.add(1);set.add(2);set.add(3);set.add(4);System.out.println(set.contains(2));set.remove(2);System.out.println(set);}
}

相比于TreeSet,HashSet的效率更高,因为HashSet不需要进行额外的数据对比操作,在其他方面基本于TreeSet无异。具体要TreeSet还是HashSet需要结合实际来考虑。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/94485.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/94485.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用Spring Boot和EasyExcel导出Excel文件,并在前端使用Axios进行请求

在现代企业应用中&#xff0c;Excel文件的导出是一项常见且重要的功能。Spring Boot作为Java开发中的热门框架&#xff0c;结合EasyExcel这样的高效库&#xff0c;能够轻松实现Excel的导出功能。而在前端&#xff0c;使用Axios进行HTTP请求&#xff0c;可以方便地与后端进行数据…

图论水题5

cf796D 题意 n个点n-1条边&#xff0c;k个特殊点以及整数d&#xff0c;要求删除最多的边保证每个点都可以在d步之内到达一个特殊点&#xff0c;输入保证每个点都可以在d步内到达特殊点 思路 考虑什么时候可以删除一条边&#xff0c;即这条边连接的两个点可以在d步内到达两个不同…

像WPS Office 一样处理pdf页面尺寸

1. 修改页面尺寸import os import shutil import fitz # PyMuPDFdef cm_to_px(cm):# 厘米转换成像素"""doc fitz.open(input_file)page0 doc[0]width_px page0.mediabox.widthheight page0.mediabox.heightprint(fwidth_px&#xff1a;{width_px} height&a…

Linux 基础开发工具

在 Linux 环境下进行开发&#xff0c;熟练掌握基础工具是提升效率、解决问题的核心前提。无论是软件安装、代码编辑&#xff0c;还是编译调试、版本管理&#xff0c;一套 “趁手” 的工具链能让开发过程事半功倍。本文将从 Linux 开发最核心的七大工具模块入手&#xff0c;一步…

TapData vs Kafka ETL Pipeline:竞争?共存?——企业实时数据策略的正确打开方式

【引言】企业实时数据流转&#xff0c;迎来“集成计算”新范式 企业 IT 架构的演进&#xff0c;从最初的数据孤岛&#xff0c;到集中式数据仓库&#xff0c;再到如今的实时数据驱动架构。在这一过程中&#xff0c;数据的集成&#xff08;数据源→目标&#xff09;与数据的计算&…

十九、云原生分布式存储 CubeFS

十九、云原生分布式存储 CubeFS 文章目录十九、云原生分布式存储 CubeFS1、分布式存储初识1.1 分布式存储主要特性1.2 为什么要在K8s上落地存储平台1.3 云原生存储平台CubeFS介绍1.4 分布式存储平台落地架构1.4.1 混合部署1.4.2 独立部署-基础设施集群1.5 资源分配建议1.6 硬件…

如何拯救一家濒临破产的科技公司?

从谷底爬起&#xff1a;Medium 的生死重生之路 2022年的 Medium&#xff0c;正坠入一个深不见底的深渊。 每月亏损260万美元&#xff0c;订阅用户持续流失——这不是增长&#xff0c;而是在消耗资本。更致命的是内容质量&#xff1a;平台充斥着“快速致富学”等空洞内容&#x…

数据结构-算法(一)

一、已知无向图的邻接矩阵&#xff0c;求无向图的邻接表。 &#xff08;1&#xff09;提示&#xff1a;无向图如下图(a)所示&#xff0c;已知邻接矩阵如图(b)所示&#xff0c;求对应的邻接表(c)。&#xff08;2&#xff09;请定义void adjMatrix_2_adjList(int b[4][4], AdjLis…

2025年嵌入式通信电源系统品牌有哪些?

现在科技跑得飞快&#xff0c;嵌入式通信电源系统可是越来越吃香了&#xff0c;尤其是在5G、物联网、智能家居这些热门地方。这玩意儿不光能让设备稳稳当当干活儿&#xff0c;还特省电、贼聪明&#xff0c;优势杠杠的&#xff01;既然大家伙儿都这么需要它&#xff0c;那到了20…

Ubuntu24.04环境下causal_conv1d和mamba_ssm安装

环境&#xff1a;WSL的Ubuntu24.041.创建conda环境&#xff0c;其中python版本为3.10.132.当前conda环境依次执行下面命令&#xff1a;conda install cudatoolkit11.8 -c nvidia pip install torch2.1.1 torchvision0.16.1 torchaudio2.1.1 -f https://mirrors.aliyun.com/pyto…

Python爬虫实战: 爬虫常用到的技术及方案详解

爬虫是获取网络数据的重要工具,Python因其丰富的库生态系统而成为爬虫开发的首选语言。下面我将详细介绍Python爬虫的常用技术和方案。 一、基础技术栈 1. 请求库 Requests - 同步HTTP请求库 import requests# 基本GET请求 response = requests.get(https://httpbin.org/g…

k8s——持久化存储 PVC

目录 k8s持久化存储&#xff1a; PVC 1 k8s PV是什么&#xff1f; 2 k8s PVC是什么&#xff1f; 3 k8s PVC和PV工作原理 4 创建pod&#xff0c;使用pvc作为持久化存储卷 ​三种回收策略详解​ 1、创建nfs共享目录 2、如何编写pv的资源清单文件 3、创建pv 更新资源清单文…

【系统架构设计师】数据库设计(一):数据库技术的发展、数据模型、数据库管理系统、数据库三级模式

数据库技术是研究数据库的结构、存储、设计、管理和应用的一门软件学科。 数据库系统本质上是一个用计算机存储信息的系统。 数据库管理系统是位于用户与操作系统之间的一层数据管理软件&#xff0c;其基本目标是提供一个可以方便、有效地存取数据库信息的环境。 数据库就是信息…

深入理解 Structured Outputs:基于 JSON Schema 的结构化输出实践指南

深入理解 Structured Outputs&#xff1a;基于 JSON Schema 的结构化输出实践指南 目录 引言Structured Outputs 概述应用场景与优势核心用法&#xff1a;结构化响应的获取功能对比&#xff1a;Structured Outputs 与 JSON 模式典型应用示例链式思维&#xff08;Chain of Tho…

大模型应用编排工具Dify之插件探索

1.前言 ​ dify 1.x版本以后插件功能丰富了很多&#xff0c;推出的插件市场上有各式各样的插件&#xff0c;比如 连接数据库、连接大模型、搜索和 mcp服务等。其中&#xff0c;有一个比较大的改动&#xff0c;模型供应商不再内置&#xff0c;而是通过插件的形式提供。因此&…

ubuntu2204安装搜狗拼音输入法

安装必要的软件包 sudo apt update sudo apt install fcitx5 fcitx5-chinese-addons fcitx5-config-qt fcitx5-configtool -y安装搜狗拼音 下载最新 .deb 包&#xff08;官方地址&#xff1a;https://pinyin.sogou.com/linux/&#xff09;&#xff0c;安装&#xff1a; sudo dp…

三,设计模式-抽象工厂模式

目的 在 工厂模式 中&#xff0c;当需要创建新的产品时&#xff0c;则额外需要创建新的工厂&#xff0c;这种模式是对产品制造方法的抽象化&#xff0c;如果产品种类变多&#xff0c;则工厂数目变多&#xff0c;则代码规模会越来越大&#xff0c;且不同的产品类的生成依赖不同…

Vue3响应式编程核心:ref与reactive全方位对比

在Vue3的Composition API中&#xff0c;ref和reactive是构建响应式数据的核心工具。许多开发者对它们的选择存在困惑&#xff1a;何时用ref的.value&#xff1f;何时用reactive的直接访问&#xff1f;为何解构会丢失响应性&#xff1f;本文从原理、场景到实战陷阱&#xff0c;为…

Redis实战-缓存的解决方案(一)

1.什么是缓存缓存就是数据交换的缓存区&#xff0c;是存储数据的临时区域&#xff0c;读写性能高。浏览器会有缓存&#xff0c;tomcat服务器也会有缓存&#xff0c;数据库也会有缓存&#xff0c;CPU也会有缓存&#xff0c;磁盘也会有缓存&#xff0c;所以说缓存是无处不在的并且…