哈希表详解 雨点打透心脏的1/2处 2024-04-03 12:52 37阅读 0赞 #### 文章目录 #### * 哈希表 * * 什么是哈希表 * 核心思想 * 哈希表原理解析 * * java代码示例 * * Hash表插入 * 什么是哈希函数 * 什么是映射? * 哈希冲突处理 * 参考链接: ## 哈希表 ## ### 什么是哈希表 ### 哈希表:也叫做**散列表**。是《数据结构与算法》中的学术用语。 它是**根据关键字和值(Key-Value)**直接进行访问的数据结构。也就是说,它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value,然后把键值对映射到表中一个位置来访问记录,以加快查找的速度。 这个映射函数叫做**哈希函数(散列函数)**,用于存放记录的数组叫做 哈希表(散列表)。 哈希表的关键思想是使用哈希函数,将键 key 和值 value 映射到对应表的某个区块中。 ### 核心思想 ### 哈希表算法思想分为两个部分: * **插入**:向哈希表中插入一个关键字,哈希函数决定该关键字的对应值应该存放到表中的哪个区块,并将对应值存放到该区块中 * **查询**:在哈希表中搜索一个关键字,使用相同的哈希函数从哈希表中查找对应的区块,并在特定的区块搜索该关键字对应的值 ### 哈希表原理解析 ### 哈希表的本质是`数组`加`哈希函数`。 在哈希表中,它的作用就是`将哈希表的某个key作为输入,然后经过一系列的运算后,得到数组的某个索引`。 一种很朴素的思路是,先用key计算出一个很大的数,然后对数组长度取模,从而得到索引,这只是众多方法中的一种,其他的比如:直接寻址法,平方取中法等。 得到索引后就可以通过索引对数组执行`插入或查找`的操作,因为`本质上是通过索引来访问数组`,所以哈希表的插入和查找的效率非常高,时间复杂度都是O(1)。 ![在这里插入图片描述][8f64ef5d67c54c4d938b7726c61bb06c.png] #### java代码示例 #### ##### Hash表插入 ##### public static void main(String[] args) { Map<Integer,String> map = new HashMap<>(); //创建HashMap实例 map.put(1,"张三"); //向Hash表插入一条数据:key=1,value=张三 map.put(2,"李四"); //向Hash表插入一条数据:key=2,value=李四 map.put(3,"王五"); //向Hash表插入一条数据:key=3,value=王五 } 创建HashMap实例,并往Hash表里面插入三条数据,实现原理如下图: 1. 向Hash表插入一条数据:key=1,value=张三,经过Hash函数运算后,存入到数组下标为0的区域 2. 向Hash表插入一条数据:key=2,value=李四,经过Hash函数运算后,存入到数组下标为1的区域 3. 向Hash表插入一条数据:key=3,value=王五,经过Hash函数运算后,存入到数组下标为2的区域 ![在这里插入图片描述][f9f932e038c14ec5b528f75d0a0bf6e9.png] 查询的原理同上,不做过多描述。 ### 什么是哈希函数 ### 哈希函数:将哈希表中元素的关键键值映射为元素存储位置的函数。一般来说,哈希函数会满足以下几个条件: * 易于计算,并且尽量使`计算出来的索引值均匀分布`,以此减少哈希冲突 * 哈希函数计算得到的`哈希值是一个固定长度的输出值` * 如果 Hash(key1) 不等于 Hash(key2),那么 key1、key2 一定不相等 * 如果 Hash(key1) 等于 Hash(key2),那么 key1、key2 可能相等,也可能不相等(会发生哈希碰撞) 在实际应用中,key值除了数字类型,还有可能是字符串类型、浮点数类型、大整数类型,甚至还有可能是几种类型的组合。 一般会`将各种类型的关键字先转换为整数类型,再通过哈希函数,将其映射到哈希表中`。 而关于整数类型的关键字,通常用到的哈希函数方法有:`直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法`等。 ***注意:特别的,当Key值是一个JavaBean时,应当如何处理?*** ### 什么是映射? ### 映射属于数学的范畴。在高中数学中,映射定义为: 两个元素的集之间元素相互“对应”的关系,为名词。映射,或者射影,在数学及相关的领域经常等同于函数。 举一个最简单的例子,一次函数:***y = x +1***,x属于自然数集A,y属于自然数集B。当 `x=1,y=2;x=2,y=3;x=3,y=4`。在A集合中随便找出一个值x,在B集合中都有一个y值与其对应。这就是映射。 如下图: ![在这里插入图片描述][9a331eec6f6c42fd812d763c28ede48f.png] ### 哈希冲突处理 ### 哈希冲突:不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 key1 ≠ key2,而 Hash(key1) = Hash(key2),这种现象称为哈希冲突。 ### 参考链接: ### * [java的Map接口常用的方法][java_Map] * [java集合学习笔记][java] * [Map集合遍历方法][Map] * [java解决Hash冲突][java_Hash] [8f64ef5d67c54c4d938b7726c61bb06c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9f687b40c8c54a0dada6e05d7f1821ca.png [f9f932e038c14ec5b528f75d0a0bf6e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/12aeca764a1c461c91a5e0847acbd879.png [9a331eec6f6c42fd812d763c28ede48f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1656fbc53b21471892e558c6809dace1.png [java_Map]: https://blog.csdn.net/m0_58680865/article/details/124963560 [java]: https://blog.csdn.net/m0_58680865/article/details/124803192 [Map]: https://blog.csdn.net/liaomingwu/article/details/118333917 [java_Hash]: https://blog.csdn.net/u010843421/article/details/81181280
相关 哈希表超详解 目录 哈希表 概念 冲突-概念 冲突-避免 冲突-避免-哈希函数设计 冲突-避免-负载因子的调节 冲突-解决-闭散列 冲突-解决-开散列 哈希桶的实现 性 小灰灰/ 2024年03月27日 19:18/ 0 赞/ 35 阅读
相关 哈希表 上一篇博客:[静态链表的介绍及实现][Link 1] > 写在前面:大家好!我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的 ╰半夏微凉°/ 2022年10月30日 07:24/ 0 赞/ 183 阅读
相关 详解哈希表查找 哈希表查找 定义 基本概念 实现方法 1、定义 > 哈希表查找又叫散列表查找,通过查找关键字不需要比较就可以获得需要记录的存储位置,它是通过在记 柔情只为你懂/ 2022年09月28日 14:26/ 0 赞/ 223 阅读
相关 哈希表 我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键 快来打我*/ 2022年06月05日 02:20/ 0 赞/ 331 阅读
相关 哈希表 1. 什么是哈希表 我们先来做个题(leetCode上387题) ![70][] public class Solution_387 { 朱雀/ 2022年05月16日 10:11/ 0 赞/ 273 阅读
相关 哈希表基本原理详解 这篇文章是参考视频 思胜 ASP.Net C#培训-7-3-下午-1-哈希表基本原理.wmv http://v.youku.com/v\_show/id\_XMj 短命女/ 2022年03月19日 13:21/ 0 赞/ 231 阅读
相关 哈希表 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0 今天药忘吃喽~/ 2022年02月01日 14:36/ 0 赞/ 377 阅读
相关 【哈希表】 char FirstNotRepeatingChar(char pString) { // invalid input if(! r囧r小猫/ 2022年01月06日 11:33/ 0 赞/ 301 阅读
相关 哈希表 【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na 傷城~/ 2021年08月11日 17:13/ 0 赞/ 528 阅读
还没有评论,来说两句吧...