算法通过村——Hash和队列问题解析
算法的备胎Hash和找靠山的队列
备胎Hash
Hash,不管是算法,还是在工程中都会大量使用。很多复杂的算法问题都用Hash能够轻松解决,也正是如此,在算法例就显得没什么思维含量,所以Hash是应用里的扛把子,但在算法里就是备胎的角色,只要有其他方式,一般就不会考虑队列了。这也是面试算法和应用算法的一个区别。
Hash的重要性
Hash在技术面试中也频繁出现,常见问题有三个:
1.对象比较为什么要计算hashCode
2.HashMap的实现原理;ConcurrentHashMap的实现原理,特别是并发和扩容方面的问题。
3.ThreadLocal里的Map工作原理
找靠山的队列
直接考察队列的算法题几乎没有,大部分场景是作为高级算法的一个工具。经典问题是树里的层次遍历相关问题和图 等高级主题中 与 广度优先相关的问题。所以说队列需要找一个靠山才行。
队列的重要性
对于Java程序员来说,队列真正的大热门是作为技术面试,考察JUC里的阻塞队列、AQS等的实现原理等。这个一般在多线程相关的课程里讲解。
Hash基础
Hash的概念和基本特征
概念
哈希(Hash)也称为散列,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,这个输出值就是散列值。
基本特征
映射:
假设数组array存放的是1到15这些数,现在要存在一个大小是7的Hash表中,该如何存储呢?
存储(如下图所示):
存储位置计算公式
index = number % 7
读取:
index = number % 7
存储案例
将1至6存入的时候,图示如下:

将7至13存入的时候,图示如下:

最后存14 和 15

读取案例
假如我们要测试13在不在这个结构中,同样使用上面的公式进行计算。通过计算,
13 % 7 = 6。则可以直接访问array[6]这个位置,很明显是存在的,所以返回true。
假如我们要测试20在不在这个结构中,同样使用上面的公式进行计算。通过计算,
20 % 7 = 6。则可以直接访问array[6]这个位置,但这个位置上只有6和13,没有20,所以返回false。
碰撞处理方法
碰撞
在上面例子中,有些在Hash中的位置可能要存储两个甚至多个元素,很明显单纯的数组是不行的(会出现元素覆盖)。这种由 两个不同的输入值,根据同一散列函数计算出的散列值相同的现象 就叫做 碰撞。
碰撞解决方法
- 开放地址法(Java里的ThreadLocal)
- 链地址法(Java里的ConcurrentHashMap)
- 哈希法(布隆过滤器)
- 建立公共溢出区
开放定址法
开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据存入其中。
图例

例如上面要继续存7,8,9的时候,7没问题,可以直接存到索引为0位置。8本来应该存到索引为1的位置,但是已经满了,所以继续向后找,索引3的位置是空的,所以8存到3位置。同理9存到索引6位置。
疑惑解释
疑惑:
这样鸠占鹊巢的方法会不会引起混乱? 比如再存3 和6的话,本来自己的位置好好的,但是被外来户占领了,该如何处理呢?
解释:
这个问题学习Java里的ThreadLocal后能解开。其基本思想如下:
ThreadLocal有一个专门存储元素的TheadLocalMap,每次在get 和set元素的时候,会先将目标位置前后的空间搜索一下,将标记为null的位置回收掉,这样大部分不用的位置就收回来了。
这就像假期后你到公司,每个人都将自己的位子附近打扫干净,结果整个工作区就很干净了。当然Hash处理该问题的整个过程非常复杂,涉及弱引用等等,这些都是Java技术面试里的高频考点。
链地址法
将哈希表的每个单元作为链表的头节点,所有哈希地址为 i 的元素构成一个同义词链表。即发生Hash冲突时,就把该关键字链在以该单位为头节点的链表的尾部,如下图所示:

这种处理方法的问题是处理起来代价还是比较高的。要落地还要进行很多优化
例如在Java里的ConcurrentHashMap中就使用了这种方式,其中涉及元素尽量均匀、访问和操作速度要快、线程安全、扩容等很多问题
错误的Hash结构
看一下下面这个Hash结构,下面的图有两处非常明显的错误

错误解释
首先是数组的长度必须是2的n次幂,这里长度是9,明显有错,然后是entry 的个数不能大于数组长度的75%,如果大于就会触发扩容机制进行扩容,这里明显是大于75%
原因
总:
在许多哈希表的实现中,选择2的n次幂作为哈希表的大小,可以提高散列函数的计算速度、解决哈希冲突的效率,并可以更好地利用内存。这些因素都有助于提高哈希表的性能。
分:
散列函数计算索引:哈希表使用散列函数将键(key)映射到索引,然后将值(value)存储在该索引处。对于2的n次幂大小的哈希表,散列函数可以使用位操作,而不需要执行较慢的模运算。例如,可以使用按位与运算(bitwise AND)操作,通过掩码来获取索引。这样可以提高散列函数的计算速度。
哈希冲突的解决:在哈希表中,不同的键可能会被散列到相同的索引位置,这称为哈希冲突。为了解决冲突,通常使用开放定址法、链表法或者其他方法。当哈希表的大小为2的n次幂时,使用位移操作(bitwise shift)可以快速计算出下一个索引位置,这样可以加快解决哈希冲突的速度。
内存分配的优化:许多现代计算机体系结构中,内存是以块(block)的形式进行分配的,其中每个块的大小通常是2的n次幂。如果哈希表的大小与内存块的大小匹配,可以更好地利用内存,减少内存分配的碎片化。
正确的Hash结构

解释
数组的长度即是2的n次幂,而他的size又不大于数组长度的75%。 HashMap的实现原理是先要找到要存放数组的下标,如果是空的就存进去,如果不是空的就判断key值是否一样,如果一样就替换,如果不一样就以链表的形式存在链表中(从JDK8开始,根据元素数量选择使用链表还是红黑树存储)。
队列基础
队列的概念和基本特征
概念
队列(Queue)是一种常见的数据结构,它是一种先进先出(First-In-First-Out,FIFO)的线性数据结构。
基本特征
先进先出:节点的排排队次序和出队次序按入队时间先后确定
实现方式
- 数组
队列使用一个固定大小的数组来存储元素,并使用两个指针来标记队列的头部和尾部
- 链表
对于基于链表,因为链表的长度是随时都可以变的,实现起来比较简单。
实现队列
链表实现
package org.example.queue;public class LinkQueue {/*** 构建节点*/static class Node{public int data;public Node next;public Node(int data) {this.data = data;}}/*创建队列头和尾*/private Node front;private Node rear;private int size;// 初始化节点public LinkQueue() {this.front = new Node(0);this.rear = new Node(0);}/*** 入队* @param value 入队数据*/public void push(int value){Node newNode = new Node(value);Node temp = front;while (temp.next != null){temp = temp.next;}temp.next = newNode;rear = newNode;size++;}/*** 出队* @return 出队的值*/public int pull(){if (front.next == null){System.out.println("队列已空,无法出队");}Node firstNode = front.next;front.next = firstNode.next;size--;return firstNode.data;}/*** 遍历队列*/public void traverse(){Node temp = front.next;while (temp != null){System.out.println(temp.data + "\t");temp = temp.next;}}public static void main(String[] args) {LinkQueue linkQueue = new LinkQueue();linkQueue.push(1);linkQueue.push(2);linkQueue.push(3);System.out.println("The first Node = " + linkQueue.pull());System.out.println("队列遍历结果为");linkQueue.traverse();}
}
相关文章:
算法通过村——Hash和队列问题解析
算法的备胎Hash和找靠山的队列 备胎Hash Hash,不管是算法,还是在工程中都会大量使用。很多复杂的算法问题都用Hash能够轻松解决,也正是如此,在算法例就显得没什么思维含量,所以Hash是应用里的扛把子,但在算…...
租赁类小程序定制开发|租赁管理系统源码|免押租赁系统开发
随着互联网的发展,小程序成为了一种重要的移动应用开发方式。租赁小程序作为其中的一种类型,可以为很多行业提供便利和创新。下面我们将介绍一些适合开发租赁小程序的行业。 房屋租赁行业:租房小程序可以帮助房东和租户快速找到合适的租赁…...
后端进阶之路——浅谈Spring Security用户、角色、权限和访问规则(三)
前言 「作者主页」:雪碧有白泡泡 「个人网站」:雪碧的个人网站 「推荐专栏」: ★java一站式服务 ★ ★前端炫酷代码分享 ★ ★ uniapp-从构建到提升★ ★ 从0到英雄,vue成神之路★ ★ 解决算法,一个专栏就够了★ ★ 架…...
Mac 安装不在 Apple 商店授权的应用程序
文章目录 一、场景介绍二、实操说明 一、场景介绍 在日常的工作生活中,发现一些好用的应用程序,但是出于某些原因,应用程序的开发者并没有将安装包上架到苹果商店。 那么这些优秀的应用程序下载安装以后就会出现如下弹框被拒之门外 二、实操…...
【MyBatis】MyBatis把空字符串转换成0的问题处理方案(96)
先看问题: Postman入参: MyBatis采用map循环插入: // Mapper接口层void addPar(Param(value "question") Map<String, Object> paramMap);<!-- 新增:参数 --><insert id"addPar" parameterType"map">INSERT IGNO…...
OpenLayers实战,OpenLayers获取移动端精确定位,OpenLayers适配App混合H5方式调用手机定位位置并定位到指定点
专栏目录: OpenLayers实战进阶专栏目录 前言 本章讲解OpenLayers如何获取移动端精确定位位置。不使用任何native本地方法,只使用纯js实现。 本篇文章适用于App混合H5方式调用手机精确定位,打包时需要选择GPS位置权限,手机获取定位过程中会弹出是否允许定位的权限提示。 …...
Go指针取址问题:循环后每次都拿到相同内容
例子: func main() {yourList : [...]int{1, 2, 3}yourMap1 : make(map[int]*int)yourMap2 : make(map[int]*int)for key, value : range yourList {// 修改前yourMap1[key] &value// 修改后tmp : valueyourMap2[key] &tmpfmt.Println(value, &value…...
用Rust实现23种设计模式之简单工厂
在 Rust 中,可以使用结构体和 trait 来实现工厂方法模式。工厂方法模式是一种创建型设计模式,通过定义一个创建对象的接口,让子类决定实例化哪个类。下面是一个简单的示例,展示了如何使用 Rust 实现工厂方法模式: // …...
SpringBoot + minio实现分片上传、秒传、续传
什么是minio MinIO是一个基于Go实现的高性能、兼容S3协议的对象存储。它采用GNU AGPL v3开源协议,项目地址是https://github.com/minio/minio。 引用官网: MinIO是根据GNU Affero通用公共许可证v3.0发布的高性能对象存储。它与Amazon S3云存储服务兼容…...
logback 里面设置 自动删除3天之前的日志
目录 1 实现 1 实现 要实现达到一定大小后将日志文件压缩,并删除三天前的日志数据,可以结合使用 SizeAndTimeBasedRollingPolicy 滚动策略和 DeleteOlderThan 选项来配置。下面是一个示例配置,实现日志文件达到一定大小后进行滚动和压缩&…...
对于数据库查询索引和查字典索引的理解
之前面试问过我对于数据库索引的理解,这个问题不是具体的问题太宽泛,面试官也没进行引导,我不知道怎么回答,下面是结合查字典进行理解。 查字典 拿查字典举例,知道一个字怎么写但是不知道具体的意思以及发音ÿ…...
git删除已经提交的大文件
当你不小心把一个巨大的二进制文件提交到git仓库的时候,此时删除再提交也没有用了,大文件已经在仓库中留底了。另外比如需要删除某个需要保密的文件,都是相同的解决办法。 我本来想着把dll放在三方库里面提交到仓库里,省得在不同…...
【数据分析】pandas 一
目录 一,pandas简介: 二,pandas数据结构Series简介: 2.1 data为ndarray 2.2 data为字典 三,Serise切片操作: 四,Series性质: 4.1 Series类似于numpy,字典 4.2 矢量化操作和标…...
题解 | #G.Gcd# 2023牛客暑期多校6
G.Gcd 数论 题目大意 给定一个包含两个非负数的初始集合 S { x , y } S\{x,y\} S{x,y} 每次操作可以选定其中不相等的两个数 a , b a,b a,b ,并将 a − b a-b a−b 或 g c d ( a , b ) gcd(a,b) gcd(a,b) 置入集合 S S S ,其中 g c d ( 0 , a …...
苍穹外卖day10——订单状态定时处理(Spring Task)、来单提醒和客户催单(WebSocket)
预期效果 对于超时没处理的需要定时程序处理。基于SpringTask实现。 来单提醒和客户催单。基于WebSocket实现。 Spring Task 介绍 Cron表达式 周几通常不能和日一起指定。 cron表达式在线生成器 在线Cron表达式生成器 入门案例 创建定时任务类 /*** 定义定时任务类*/ Slf4j…...
【多线程初阶】多线程案例之单例模式
文章目录 前言1. 什么是单例模式2. 饿汉模式3. 懒汉模式 --- 单线程版4. 懒汉模式 --- 多线程版5. 懒汉模式 --- 多线程改进版总结 前言 本文主要给大家讲解多线程的一个重要案例 — 单例模式. 关注收藏, 开始学习吧🧐 1. 什么是单例模式 单例模式是一种很经典的…...
跨境选品怎么选?建议独立站卖家收下这份利基产品查找攻略!
跨境电商平台现在可谓是火热发展中,独立站出海风口,其实选择的机会还真不少,相比国内电商的发展势头,看得出来,未来跨境电商的大门,对你而言,敞开着。选品这事儿,就像你上战场前挑选…...
[C++项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍...
项目背景 Boost库是C中一个非常重要的开源库. 它实现了许多C标准库中没有涉及的特性和功能, 一度成为了C标准库的拓展库. C新标准的内容, 很大一部分脱胎于Boost库中. Boost库的高质量代码 以及 提供了更多实用方便的C组件, 使得Boost库在C开发中会被高频使用 为方便开发者学…...
opencv-32 图像平滑处理-高斯滤波cv2.GaussianBlur()
在进行均值滤波和方框滤波时,其邻域内每个像素的权重是相等的。在高斯滤波中,会将中心点的权重值加大,远离中心点的权重值减小,在此基础上计算邻域内各个像素值不同权重 的和。 基本原理 在高斯滤波中,卷积核中的值不…...
Windows 环境Kubernetes安装
目录 前言 安装 Docker 安装 Kubernetes Windows 安装 kubectl 介绍 安装 开启 Kubernetes 前言 Docker作为当前最流行的容器化平台,为Kubernetes提供了强大的容器化技术基础。Kubernetes与Docker的结合,使得容器化应用程序在大规模集群中得以简…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
Qt学习及使用_第1部分_认识Qt---Qt开发基本流程
前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...
