首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >散列表(哈希表)

散列表(哈希表)

作者头像
用户1215536
发布于 2018-02-05 03:19:28
发布于 2018-02-05 03:19:28
7570
举报

序言:

如果将一系列的记录按照关键字的某种函数存储,那么在查找某个数据的时候就可以直接通过关键字计算出来了,而不在需要“比较”,这样会非常高效,这就是散列技术。

所以散列技术就是:     存储位置=f(关键字)        不管是记录的存储还是查找,都用这种方法

散列技术具有很高的效率,但是使用起来有一些限制。如1个关键字对应多个记录的情况(比如在一个学校的学生中按性别查找,则对应太多的记录),此外散列技术同样不适合于范围查找和排序等操作。

一、散列函数的构造

在设计散了函数的时候主要考虑两个原则:

(1)计算效率高:散列的优点就是高效,如果通过关键字计算地址的时间比其他查找方法比较用的时间还长,那么要它还有何用呢?

(2)散列地址分布均匀:这样才能保证存储空间的有效利用,也可以减少处理冲突而耗费的时间。

常用散列函数的构造方法:

(1)直接定址法:

取某个关键字的线性函数作为散列地址:f(key)=a*key+b      (a,b取常数)

此法需要事先知道关键字的分布情况,适合查找数据较少且连续的记录。

(2) 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

此法适合关键字位数比较大的情况。

(3)平方取中法:取关键字平方后的中间几位作为散列地址。

此法比较适合不知道关键字分布,而位数又不是很大的情况。 

(4)折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

此法适合事先不知道关键字分布且位数较多的情况。

(5)除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。

(6) 随机数法:选择一随机数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

二、处理冲突的方法

(1)开放寻址法:如果发生冲突,就去寻找下一个散列地址,如此循环,直到找到为止。

   它的公式是:Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:

  1. di=1,2,3,…, m-1,称线性探测再散列;

  2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

  3. di=伪随机数序列,称伪随机探测再散列。 ==

(2)再散列法:事先准备多个散列函数,如果用一种函数产生冲突后,立马换另一中计算,如此循环,直到找到。

Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

(3) 链地址法(拉链法):将所有同义词记录在一个链表中,每次产生冲突,就直接在链表后增加一个结点而已。

(4) 建立一个公共溢出区:一旦发生冲突就把数据放在放在里面。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-01-05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
哈希查找
这是一种简单/最常用的方法,嘉定哈希表表长为m,取一个不大于m但最接近或等于m的质数p,利用一下公式把关键字转化成哈希地址:
Autooooooo
2020/11/09
4960
哈希查找
2019Java面试题:为什么使用hashmap需要重写hashcodes和equals方法?
总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是Object.equals方法了。但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。
葆宁
2019/04/19
9780
2019Java面试题:为什么使用hashmap需要重写hashcodes和equals方法?
数据结构与算法之哈希表
哈希表也叫散列表。 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
袁新栋-jeff.yuan
2020/08/26
7830
散列表的相关概念
HashMap是Java源码中非常优秀的源码,涉及到很多的概念,算法、红黑树、数组、链表... 之前也尝试过硬着头皮去学习,但是由于基础本身就不是很牢固,所以后面也没有多少收获。那么,这次笔者先来梳理一下HashMap的一些概念。
飞翔的竹蜻蜓
2020/07/08
7700
散列表的相关概念
数据结构之哈希表(HASH)
   当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二分查找,通过比较key与a[i]的大小来折半查找,直到相等时才返回索引i。最终通过索引找到我们要找的元素。    但是,这两种方法的效率都依赖于查找中比较的次数。我们有一种想法,能不能不经过比较,而是直接通过关键字key一次得到所要的结果呢?这时,就有了散列表查找(哈希表)。
全栈程序员站长
2022/07/21
6300
数据结构之哈希表(HASH)
哈希表基本概念介绍及哈希冲突的处理方法(附源码)
  哈希表(散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做哈希(散列)函数,存放记录的数组叫做哈希(散列)表。
嵌入式与Linux那些事
2021/05/20
9630
哈希表基本概念介绍及哈希冲突的处理方法(附源码)
【数据结构】什么是哈希表(散列表)?
在正式开始深入了解哈希表之前呢, 我想带大家先回忆一下生活中咱们的这个"老朋友"。可能你会感到诧异, 我怎么会和它是"老朋友"呢? 别急, 其实你的生活中常常会出现哈希的身影,只是你没有细心观察罢了,不信你看下面几个场景对你来说是不是非常熟悉呢:
修修修也
2024/10/06
3170
【数据结构】什么是哈希表(散列表)?
散列查找和哈希查找_散列检索
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系,公式如下:
全栈程序员站长
2022/11/15
1.1K0
散列表(一):散列表概念、 散列函数构造方法、 常见字符串哈希函数(测试冲突)
一、散列表基本概念 1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置 来访问记录,以加快查找的速度。这个映射函数叫做散
s1mba
2017/12/28
2.3K0
散列表(一):散列表概念、 散列函数构造方法、 常见字符串哈希函数(测试冲突)
哈希相关知识再学习
在平时工作和源码学习的过程中经常遇到哈希相关的问题,每次都会上网找资料回忆哈希相关的知识点。趁这机会记录下来,防止以后又忘记了!!
静默加载
2020/05/29
8070
python hash
help(hash) Help on built-in function hash in module builtins: hash(obj, /)     Return the hash value for the given object.#返回给定对象的哈希值     Two objects that compare equal must also have the same hash value, but the     reverse is not necessarily true.     #两个比较相等的对象也必须有相同的散列值,但是逆转不一定是正确的。
py3study
2020/01/09
8850
查找-散列查找
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。查找时,根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上。
全栈程序员站长
2022/08/28
1.7K0
查找-散列查找
学生物的女朋友都能看懂的哈希表总结!
之前给大家介绍了链表,栈和队列今天我们来说一种新的数据结构散列(哈希)表,散列是应用非常广泛的数据结构,在我们的刷题过程中,散列表的出场率特别高。所以我们快来一起把散列表的内些事给整明白吧,文章框架如下。
公众号袁厨的算法小屋
2020/11/25
9220
学生物的女朋友都能看懂的哈希表总结!
数据结构与算法-散列表
无论是顺序表还是树表,查找数据元素时要进行一系列的键值比较的过程,为了减少比较次数,就需要使数据元素的存储位置和键值之间建立某种联系,为此我们就需要使用散列技术动态查找表。首先我们需要熟悉几个基本一概念:
越陌度阡
2020/11/26
8960
数据结构与算法-散列表
重温数据结构:哈希 哈希函数 哈希表
该文介绍了计算机科学中的哈希表(Hash Table)及其在编程中的应用。哈希表是一种数据结构,可以高效地完成查找、插入、删除等操作。文章还介绍了哈希函数、哈希冲突、拉链法等概念。
张拭心 shixinzhang
2018/01/05
2.8K1
重温数据结构:哈希 哈希函数 哈希表
程序员必读:教你摸清哈希表的脾气
在哈希表中,记录的存储位置 = f (关键字),通过查找关键字的存储位置即可,不用进行比较。散列技术是在记录的存储位置和它的关键字之间建立一个明确的对应关系f 函数,使得每个关键字 key 对应一个存储位置 f(key) 且这个位置是唯一的。这里我们将这种对应关系 f 称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。
谭庆波
2018/08/10
4110
程序员必读:教你摸清哈希表的脾气
STL源码剖析-hashtable
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877353
bear_fish
2018/09/14
9440
STL源码剖析-hashtable
《大话数据结构》 查找 以及一个简单的哈希表例子
第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):是由同一类型的数据元素构成的集合。 关键字(key):是数据元素中某个数据项的值,又称为键值。 若此关键字可以唯一的标识一个记录,则称此关键字为主关键字(Primary key)。 对于那些可以识别多个数据元素的关键字,我们称为次关键字(Secondary key)。 查找表按照操作方式来分有两大种:静态查找表和动态查找表 静态查找表(Static
xcywt
2018/03/28
2.4K0
《大话数据结构》 查找 以及一个简单的哈希表例子
【数据结构】哈希表
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为 $O(N)$ ,平衡树中为树的高度,即 $O(logN)$ ,搜索的效率取决于搜索过程中元素的比较次数。
椰椰椰耶
2024/09/20
1640
【数据结构】哈希表
重学数据结构(八、查找)
顺序查找的基本思想:从表的一端开始,顺序扫描线性表,依次扫描到的结点关键字和给定的K值相比较,若当前扫描到的结点关键字与 K相等,则查找成功;若扫描结束后,仍未找到关键字等于 K的结点,则查找失败。
三分恶
2020/12/16
9060
重学数据结构(八、查找)
相关推荐
哈希查找
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档