您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法入门之散列表简介

时间:2022-10-25 13:37:44  来源:今日头条  作者:Java面试365

什么是散列表

散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。

 

键值不会重复所以通过键就可以找到与之对应的值,一般散列表查询的时间复杂度为O(1),那么为什么散列表会这么快呢?

哈希函数

在分析原因之前我们需要知道散列表其存储底层是数组,正是利用了数组下标获取元素效率高的特点,但我们需要注意的是数组下标是整型,而散列表的键值可不一定是整型,为什么散列表还能通过键高效获取值呢?这就需要聊到哈希函数,所谓的哈希函数就是将散列表的键转换为存储数组的下标,再通过下标获取散列表的值,获取过程如下。

 

哈希函数如何实现

那么哈希函数如何实现呢?每个语言会有自己的计算逻辑,这里以JAVA为例。如果想要自己设计一个哈希函数第一步是需要取到每个键唯一且为整数的标识,在JAVA中有这种功能的函数被称为hashCode方法,是每个对象唯一的标识,所以键对应的哈希函数就可以采用如下逻辑(JAVA中必然不可能如此简单还会通过一系列的位运算提升效率,这里只是简单讨论)。

// key.hashCode()调用键的hashCode方法得到唯一的int值
// arr.length表示散列表底层数组的长度
int index = key.hashCode()%arr.length;

哈希碰撞

无论多好的哈希函数都避免不了的一个问题就是,两个不相同的哈希值可能计算出来的数组下标为同一个。

假设数组长度为6,需要放入两个键key1和key2,key1的hashCode值为3,key2的hashCode值为9,那么通过与数组长度模运算得到两个数组下标都是3,如果按照数组的存储方式,后面存储的必然会把前面存储的值覆盖,这种场景被称为哈希碰撞

为解决哈希碰撞提出了两种方法,分别为链表法和开放寻址法。

开放寻址法

开放寻址法其原理就是,当存储元素的键下标被占用时,自动查找下一个空挡位置存放值,如下

 

存在一个元素Entry2,计算其数组下标为2,也就是Entry3的位置,计算出来的数组下标被占用,那么就往下查找下一个元素但是被Entry4占用,再去查找为空的位置,直到查找到数组下标为4的位置,插入元素保存即可。

这种方法在JAVA中的经典应用就是ThreadLocal~

链表法

链表法就是将散列表由单纯的数组存储改为数组+链表组合的形式存储,每个数组中的元素都可以理解为链表的头节点,当需要存储元素时,先判断该下标元素是否为空如果为空之间作为头节点插入,如果不为空则将该数组下标元素头节点指向需要插入的元素。

 

JAVA中的HashMap就是采用的链表法来解决哈希冲突,当然链表法不是万无一失,当链表过长那么检索的效率必然降低因为链表检索需要遍历链表,时间复杂度为O(n),所以HashMap中还会涉及到扩容,扩容后将所有的元素重新哈希,以此来达到缩短链表长度的目的。



Tags:散列表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
深度图解 Redis Hash(散列表)实现原理
Redis 的散列表Dict 由数组 + 链表构成,数组的每个元素占用的槽位叫做哈希桶,当出现散列冲突的时候就会在这个桶下挂一个链表,用“拉链法”解决散列冲突的问题。1、是什么Redis...【详细内容】
2023-05-29  Search: 散列表  点击:(202)  评论:(0)  加入收藏
算法入门之散列表简介
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Search: 散列表  点击:(313)  评论:(0)  加入收藏
介绍常用的数据结构:数组,栈,链表,队列,树,图,堆,散列表
常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。1、数组 数组是可以再内存中连续存储多个元素...【详细内容】
2020-03-01  Search: 散列表  点击:(339)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(15)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(51)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(45)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(96)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(64)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条