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

算法入门之散列表简介

时间: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:散列表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Tags: 散列表  点击:(0)  评论:(0)  加入收藏
常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。1、数组 数组是可以再内存中连续存储多个元素...【详细内容】
2020-03-01  Tags: 散列表  点击:(121)  评论:(0)  加入收藏
▌简易百科推荐
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Java面试365  今日头条  Tags:散列表   点击:(0)  评论:(0)  加入收藏
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  小傅哥    Tags:红黑树   点击:(12)  评论:(0)  加入收藏
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(9)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(16)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(11)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(11)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)—&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(12)  评论:(0)  加入收藏
实现优先级队列最常用的数据结构是堆,堆的常见实现有二叉堆、斐波那契堆、二项堆等。二叉堆堆是一种完全二叉树,我们以小根堆为例,小根堆的性质就是,每个节点都小于其左孩子和右...【详细内容】
2022-09-29  51Testing软件测试网     Tags:数据结构   点击:(9)  评论:(0)  加入收藏
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  java保佑我发大财  今日头条  Tags:布隆过滤器   点击:(51)  评论:(0)  加入收藏
1、A GPU accelerated Genetic Algorithm for the Construction of Hadamard Matrices Andras Balogh, Raven Ruiz这篇论文使用遗传算法来构建Hadamard矩阵。 生成随机矩...【详细内容】
2022-09-06  deephub  今日头条  Tags:遗传算法   点击:(64)  评论:(0)  加入收藏
站内最新
站内热门
站内头条