Java哈希查找(含面试大厂题和源码)
哈希查找(Hash Search)是一种基于哈希表(Hash Table)的数据查找方法。哈希表通过使用哈希函数将键(Key)映射到表中的位置来存储数据,从而实现快速的数据访问。哈希查找的效率通常取决于哈希函数的设计、哈希表的大小以及处理哈希冲突的策略。
哈希查找的工作原理:
- 哈希函数:通过哈希函数将键转换为哈希表中的索引。
- 存储数据:将数据存储在哈希表的相应位置。
- 查找数据:通过键计算哈希值,直接访问数据所在的哈希表位置。
- 处理冲突:当两个不同的键产生相同的哈希值时(称为哈希冲突),需要采用某种策略来解决。常见的冲突解决策略包括链地址法(Chaining)和开放寻址法(Open Addressing)。
哈希查找的优缺点:
优点:
- 平均情况下,哈希查找可以实现接近 O(1) 的时间复杂度。
- 哈希表可以高效地支持大量的数据插入、查找和删除操作。
缺点:
- 哈希表的性能依赖于哈希函数的设计和冲突解决策略。
- 哈希表可能需要额外的存储空间来处理冲突。
- 哈希查找不保留元素的顺序。
哈希查找的Java实现:
import java.util.HashMap;
import java.util.Map;public class HashSearch {private Map<Integer, String> hashTable;public HashSearch() {hashTable = new HashMap<>();}public void insert(int key, String value) {hashTable.put(key, value);}public String search(int key) {return hashTable.get(key);}public static void main(String[] args) {HashSearch search = new HashSearch();search.insert(1, "apple");search.insert(2, "banana");search.insert(3, "cherry");String result = search.search(2);System.out.println("Value for key 2: " + result);}
}
在面试中,了解哈希查找的原理和实现是非常重要的,尤其是当面试官询问关于数据结构和算法的问题时。通过实现哈希查找,可以展示你对基本数据结构和算法的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试!哈希查找是大厂面试中常见的题目类型,尤其是在处理大量数据和需要高效查找的场景中。以下是三道可能出现在大厂面试中的与哈希查找相关的编程题目,以及相应的Java源码实现。
题目 1:设计一个 LRU 缓存
描述:
设计一个 LRU(Least Recently Used)缓存,它应该支持以下操作:获取数据 get 和写入数据 put。
示例:
输入: ["LRUCache", "put", "put", "get", "put", "get", "get"][ [2], [1, 1], [2, 2], [1], [3, 3], [2], [4]输出: [null, null, null, 1, null, 2, 3]
Java 源码:
import java.util.HashMap;
import java.util.Map;public class LRUCache {private final int capacity;private final Map<Integer, Integer> cache;private final DoublyLinkedList lru;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();this.lru = new DoublyLinkedList();}public int get(int key) {if (cache.containsKey(key)) {lru.moveToHead(key);return cache.get(key);}return -1;}public void put(int key, int value) {if (cache.containsKey(key)) {cache.put(key, value);lru.moveToHead(key);} else {if (cache.size() >= capacity) {int last = lru.removeTail();cache.remove(last);}cache.put(key, value);lruaddToHead(key);}}private void lruaddToHead(int key) {Node newNode = new Node(key);lru.addFirst(newNode);}private void lru.moveToHead(int key) {Node node = lru.find(key);if (node != null) {lru.remove(node);lruaddToHead(key);}}private void lru removeTail() {if (!lru.isEmpty()) {lru.removeLast();}}private class DoublyLinkedList {private Node head, tail;DoublyLinkedList() {head = new Node(0, 0);tail = new Node(0, 0);head.next = tail;tail.prev = head;}void addFirst(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}void remove(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}void removeLast() {if (tail.prev != head) {Node last = tail.prev;remove(last);}}Node find(int key) {Node current = head.next;while (current != tail) {if (current.key == key) {return current;}current = current.next;}return null;}}private class Node {int key, value;Node prev, next;Node(int key, int value) {this.key = key;this.value = value;}}public static void main(String[] args) {LRUCache lru = new LRUCache(2);lru.put(1, 1);lru.put(2, 2);System.out.println(lru.get(1)); // 返回 1lru.put(3, 3); // 该操作会使得关键字 2 作废System.out.println(lru.get(2)); // 返回 -1 (未找到)System.out.println(lru.get(3)); // 返回 3lru.put(4, 4); // 该操作会使得关键字 1 作废System.out.println(lru.get(1)); // 返回 -1 (未找到)System.out.println(lru.get(3)); // 返回 3System.out.println(lru.get(4)); // 返回 4}
}
题目 2:字符串哈希映射
描述:
给定一个字符串,将所有出现的大写字母映射到一个新字符串中,映射规则为 ‘A’ -> ‘a’,‘B’ -> ‘b’,…,‘Z’ -> ‘z’。
示例:
输入: "LEETCODEISHIRING"
输出: "ldecodishngi"
Java 源码:
public class MapStringToHash {public String stringHashMapping(String s) {StringBuilder result = new StringBuilder();for (char ch : s.toCharArray()) {if (Character.isUpperCase(ch)) {result.append((char) (ch + 32));} else {result.append(ch);}}return result.toString();}public static void main(String[] args) {MapStringToHash solution = new MapStringToHash();String input = "LEETCODEISHIRING";String output = solution.stringHashMapping(input);System.out.println("Mapped string: " + output);}
}
题目 3:两个字符串的哈希映射
描述:
给定两个字符串,计算它们在哈希表中的相似度。如果一个字符串的字符可以通过另一个字符串中的字符进行替换得到,那么这两个字符串是相似的。
示例:
输入: s1 = "great", s2 = "raste"
输出: true
Java 源码:
import java.util.HashSet;
import java.util.Set;public class HashMappingTwoStrings {public boolean areAlmostEqual(String s1, String s2) {if (s1.length() != s2.length()) {return false;}Set<Character> set1 = new HashSet<>();Set<Character> set2 = new HashSet<>();for (int i = 0; i < s1.length(); i++) {set1.add(s1.charAt(i));set2.add(s2.charAt(i));}return set1.equals(set2);}public static void main(String[] args) {HashMappingTwoStrings solution = new HashMappingTwoStrings();String s1 = "great";String s2 = "raste";boolean result = solution.areAlmostEqual(s1, s2);System.out.println("Strings are almost equal: " + result);}
}
这些题目和源码展示了哈希查找在解决实际问题中的应用。在面试中,能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试!
相关文章:
Java哈希查找(含面试大厂题和源码)
哈希查找(Hash Search)是一种基于哈希表(Hash Table)的数据查找方法。哈希表通过使用哈希函数将键(Key)映射到表中的位置来存储数据,从而实现快速的数据访问。哈希查找的效率通常取决于哈希函数…...
c++中常用库函数
大小写转换 islower/isupper函数 char ch1 A; char ch2 b;//使用islower函数判断字符是否为小写字母 if(islower(ch1)){cout << ch1 << "is a lowercase letter." << end1; } else{cout << ch1 << "is not a lowercase lette…...
Scrapy框架 进阶
Scrapy框架基础Scrapy框架进阶 【五】持久化存储 命令行:json、csv等管道:什么数据类型都可以 【1】命令行简单存储 (1)语法 Json格式 scrapy crawl 自定义爬虫程序文件名 -o 文件名.jsonCSV格式 scrapy crawl 自定义爬虫程…...
ubuntu22安装snipaste
Ubuntu 22.04 一、Snipaste 介绍和下载 Snipaste 官网下载链接: Snipaste Downloads 二、安装并使用 Snipaste # 1、进入Snipaste-2.8.9-Beta-x86_64.AppImage 目录(根据自己下载目录) cd /home/jack/Downloads/softwares/AppImage# 2、Snipaste-2.8.9-…...
spring-cloud微服务openfeign
Spring Cloud openfeign对Feign进行了增强,使其支持Spring MVC注解,另外还整合了Ribbon和Nacos,从而使得Feign的使用更加方便 优势,openfeign可以做到使用HTTP请求远程服务时就像洞用本地方法一样的体验,开发者完全感…...
小程序变更主体需要多久?
小程序迁移变更主体有什么作用?小程序迁移变更主体的好处有很多哦!比如可以获得更多权限功能、公司变更或注销时可以保证账号的正常使用、收购账号后可以改变归属权或使用权等等。小程序迁移变更主体的条件有哪些?1、新主体必须是企业主体&am…...
19 Games101 - 笔记 - 相机与透镜
**19 ** 相机与透镜 目录 摘要一 照相机主要部分二 小孔成像与视场(FOV)三 曝光(Exposure)四 景深(Depth of Field)总结 摘要 虽说照相机与透镜属于相对独立的话题,但它们的确是计算机图形学当中的一部分知识。在过往的十多篇笔记中,我们学习的都是如…...
Flink入门学习 | 大数据技术
⭐简单说两句⭐ ✨ 正在努力的小新~ 💖 超级爱分享,分享各种有趣干货! 👩💻 提供:模拟面试 | 简历诊断 | 独家简历模板 🌈 感谢关注,关注了你就是我的超级粉丝啦! &…...
Arthas实战教程:定位Java应用CPU过高与线程死锁
引言 在Java应用开发中,我们可能会遇到CPU占用过高和线程死锁的问题。本文将介绍如何使用Arthas工具快速定位这些问题。 准备工作 首先,我们创建一个简单的Java应用,模拟CPU过高和线程死锁的情况。在这个示例中,我们将编写一个…...
HTML制作跳动的心形网页
作为一名码农 也有自己浪漫的小心思嗷~ 该网页 代码整体难度不大 操作性较强 祝大家都幸福hhhhh 效果成品: 全部代码: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD><TITLE> 一个…...
如何在Odoo 17 销售应用中使用产品目录添加产品
Odoo,作为一个知名的开源ERP系统,发布了其第17版,新增了多项功能和特性。Odoo 17包中的一些操作简化了,生产力提高了,用户体验也有了显著改善。为了为其用户提供新的和改进的功能,Odoo不断进行改进和增加新…...
为什么pdf拆分出几页之后大小几乎没有变化
PDF 文件的大小在拆分出几页之后几乎没有变化可能有几个原因: 图像压缩: 如果 PDF 文件中包含图像,而这些图像已经被压缩过,拆分后的页面依然会保留这些压缩设置,因此文件大小可能不会显著变化。 文本和矢量图形: PDF 文件中的文…...
如何在 VM 虚拟机中安装 OpenEuler 操作系统保姆级教程(附链接)
一、VMware Workstation 虚拟机 若没有安装虚拟机的可以参考下篇文章进行安装: 博客链接https://eclecticism.blog.csdn.net/article/details/135713915 二、OpenEuler 镜像 点击链接前往官网 官网 选择第一个即可 三、安装 OpenEuler 打开虚拟机安装 Ctrl …...
(六)PostgreSQL的组织结构(3)-默认角色和schema
PostgreSQL的组织结构(3)-默认角色和schema 基础信息 OS版本:Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本:16.2 pg软件目录:/home/pg16/soft pg数据目录:/home/pg16/data 端口:57771 默认角色 Post…...
DockerFile定制镜像
dockerfile 简介 Dockerfile 是⼀个⽤来构建镜像的⽂本⽂件,⽂本内容包含了⼀条条构建镜像所需的指令和 说明,每条指令构建⼀层,最终构建出⼀个新的镜像。 docker镜像的本质是⼀个分层的⽂件系统 centos的iso镜像⽂件是包含bootfs和rootfs…...
Java8中JUC包同步工具类深度解析(Semaphore,CountDownLatch,CyclicBarrier,Phaser)
个人主页: 进朱者赤 阿里非典型程序员一枚 ,记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名) 引言 在Java中,并发编程一直是一个重要的领域,而JDK 8中的java.u…...
岛屿个数(dfs)
[第十四届蓝桥杯省B 岛屿个数] 小蓝得到了一副大小为 M N MN MN 的格子地图,可以将其视作一个只包含字符 0 0 0(代表海水)和 1 1 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛…...
【C++造神计划】运算符
1 赋值运算符 赋值运算符的功能是将一个值赋给一个变量 int a 5; // 将整数 5 赋给变量 a 运算符左边的部分叫作 lvalue(left value),右边的部分叫作 rvalue(right value) 左边 lvalue 必须是一个变量 右边 rval…...
Cortex-M3/M4处理器的bit-band(位带)技术
ARM Cortex-M3/M4的位带(Bit-Band)技术是一种内存映射技术,它允许对单个位进行直接操作,而不需要对整个字(通常是32位)进行操作。这项技术主要用于对特定的位进行高效的读写,特别是在需要对GPIO…...
【TOP】IEEE旗下1区,影响因子将破8,3个月录用,CCF推荐,性价比高!
计算机类 ● 好刊解读 IEEE出版社、中科院2区TOP,CCF推荐,今天推荐的期刊可谓buff叠满,好刊质量靠谱,有意向评职晋升毕业作者可重点关注: 01 期刊简介 ✅出版社:IEEE ✅影响因子:7.5-8.0 ✅…...
赚钱游戏 2.0.1 版 (资源免费)
没有c编辑器的可以直接获取资源来玩 #include <iostream> #include <string> #include <windows.h> #include <conio.h> #include <fstream> #include <ctime> #include <time.h> #include <stdio.h> #include <cstring&g…...
服务调用-微服务小白入门(4)
背景 各个服务应用,有很多restful api,不论是用哪种方式发布,部署,注册,发现,有很多场景需要各个微服务之间进行服务的调用,大多时候返回的json格式响应数据多,如果是前端直接调用倒…...
代码随想录算法训练营第三十六天| 435. 无重叠区间、 763.划分字母区间、56. 合并区间
435 题目: 给定一个区间的集合 intervals ,其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 题目链接:435. 无重叠区间 - 力扣(LeetCode) 思路: …...
【AIGC调研系列】rerank3是什么
Rerank 3是一个针对企业搜索和检索辅助生成(RAG)系统优化的新型基础模型,它支持多语种、多结构数据搜索,并提供高精度的语义重排。通过这种方式,Rerank 3能够大幅提升响应准确度和降低延迟,同时大幅降低成本…...
Linux下网络编程基础知识--协议
网络基础 这一个课程的笔记 相关文章 协议 Socket编程 高并发服务器实现 线程池 协议 一组规则, 数据传输和数据的解释的规则。 比如说依次发送文件的文件名, 文件的大小, 以及实际的文件, 这样规定发送一个文件的顺序以及发送的每一个部分的格式等可以算是一种协议 型协议 …...
在 VS Code 中使用 GitHub Copilot
Code 结合使用。 GitHub Copilot 是什么 GitHub Copilot 是一个可以帮助你更简单、更快速地编写代码的工具,由 GPT-3 提供支持。你只需编写所需代码的描述——例如,编写一个函数来生成一个随机数,或对一个数组进行排序——Copilot 就会为你…...
使用spring-ai快速对接ChatGpt
什么是spring-ai Spring AI 是一个与 Spring 生态系统紧密集成的项目,旨在简化在基于 Spring 的应用程序中使用人工智能(AI)技术的过程。 简化集成:Spring AI 为开发者提供了方便的工具和接口,使得在 Spring 应用中集…...
免费的 ChatGPT 网站(六个)
🔥博客主页: 小羊失眠啦. 🎥系列专栏:《C语言》 《数据结构》 《C》 《Linux》 《Cpolar》 ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 一、insCode二、讯飞星火三、豆包四、文心一言五、通义千问六、360智脑 现在智能…...
arm内核驱动-中断
先介绍个东西 ctags 这个工具可以像keil一样在工程里查找跳转,帮我们找到我们想要的东西。 安装教程可以找到,这里只讲怎么用。 在工程目录(包含所有你会用到的头文件等)下,先加载这个命令,可能要等待…...
第十五届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组
试题 C: 好数 时间限制 : 1.0s 内存限制: 256.0MB 本题总分:10 分 【问题描述】 一个整数如果按从低位到高位的顺序,奇数位(个位、百位、万位 )上 的数字是奇数,偶数位(十位、千位、十万位 &…...
国外云服务器哪个好/深圳seo优化推广公司
【前言】树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历。对于二叉树,每个节点至多有两个子节点(特别的称为左,右子节点),又有中序遍历。由于树自身具有的递归性…...
正规的app网站开发/淘宝推广怎么做
格式: jmap [option] vmid 作用: 生成堆转储快照。 使用:(注意:需要使用工具打开,分析。 比如: EclipseMemoryAnalyzer) 转载于:https://www.cnblogs.com/DengGao/p/jmap.html...
别人盗用我的网站备案号怎么办/php开源建站系统
学了几天的python和FME Objects,发现之间教程里的很多对象已经过时了,而且语法和vb相差比较大,但概念还是一样的,下面写一段python代码,将这几天学习的对象联系一下,下面的代码功能是读schema feature和dat…...
什么网站可以分享wordpress/seo技术306
远程桌面连接错误:由于安全设置错误,客户端无法连接到远程计算机。 解决方法: 按 Win R 运行输入:secpol.msc 依次打开本地策略 -> 安全选项 -> 系统加密:将 FIPS 兼容算法用于加密、哈希和签名。默认该项安全…...
网站开发公司兴田德润在那里/网页分析工具
NS是一个基于事件驱动的单线程模拟器,在模拟器中有四种可使用的调度器:链表调度器、堆调度器、日历调度器和实时调度器。调度器调度的是事件,下面是事件的定义(event): class Event { public:Event* next_;…...
videopro wordpress/百度如何发布作品
Q:我用outlook下载了邮箱里所有的邮件,现在想刻盘保存,我应该保存哪些文件呢,以保证我把光盘内的数据放到其他电脑上还可以用outlook查看我的这些邮件? A:找到你outlook的按装文件,你可以全部刻下来,到后期…...