专栏首页轮子工厂程序员必读:教你摸清哈希表的脾气

程序员必读:教你摸清哈希表的脾气

1. 相关概念

在哈希表中,记录的存储位置 = f (关键字),通过查找关键字的存储位置即可,不用进行比较。散列技术是在记录的存储位置和它的关键字之间建立一个明确的对应关系f 函数,使得每个关键字 key 对应一个存储位置 f(key) 且这个位置是唯一的。这里我们将这种对应关系 f 称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。

当存储记录时,通过散列函数计算出记录的散列地址;当查找记录时,我们通过同样的是散列函数计算记录的散列地址,并按此散列地址访问该记录。散列技术即使一种存储方法,也是一种查找方法;散列技术之间没有关系,只有关键字和函数之间有关系,所以散列技术是一种面向查找的存储技术

缺点是会存在关键字重复的问题,比如说男女为关键字的时候就不合适了。同样不适合查找范围的,比如说查找18-20岁之间的同学。散列表技术对于1对1的查找是适合的。

2. 构造散列函数

2.1 两个基本原则

“好的散列函数 = 计算简单 + 分布均匀”。其中计算简单指的是散列函数的计算时间不应该超过其他查找技术与关键字比较的时间,而分布均匀指的是散列地址分布均匀。

2.2 具体方法

2.2.1 直接定址法

即使用关键字本身作为函数值,即f(key) = key。假如有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。 如下图所示

又假果现在要统计的是1980年以后出生的人口数,那么我们对出生年份这个关键字可以变换为:用年份减去1980的值来作为地址。即:f(key) = key – 1980

所以直接定值法是取关键字的某个线性函数值为散列地址,即 f(key) = a*key + b。其优点是简单、均匀,不会产生冲突;但缺点是需要知道关键字的分布情况,希望数值是连续的。

2.2.2 数字分析法

数字分析法通常适合处理关键字位数比较大的情况,例如我们现在要存储某家公司员工登记表,如果用手机号作为关键字,那么我们发现抽取后面的四位数字作为散列地址是不错的选择,如下图所示 :

2.2.3 平方取中法

平方取中法是将关键字平方之后取中间若干位数字作为散列地址。这种方法适用于不知道关键字的分布,且数值的位数又不是很大的情况。

2.2.4 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表表长取后几位作为散列地址。

2.2.5 除留余数法

此方法为最常用的构造散列函数方法,对于散列表长为m的散列函数计算公式为:

f(key) = key mod p(p<=m)

事实上,这个方法不仅可以对关键字直接取模,也可以通过折叠、平方取中后再取模。例如下表,我们对有12个记录的关键字构造散列表时,就可以用f(key) = key mod 12的方法。

p的选择是关键,如果对于这个表格的关键字,p还选择12的话,那得到的情况未免也太糟糕了:

p的选择很重要,如果我们把p改为11,那结果就另当别论啦:

当然在上述的这种情况中仍然是有冲突的情况,对于这种情况在后面中会介绍解决的方法。

2.2.6 随机数法

选择一个随机数,取关键字的随机函数值为它的散列地址。

f(key) = random(key)

这里的random是随机函数,当关键字的长度不等时,采用这个方法构造散列函数是比较合适的。

2.3 哈希表的选择

现实中,我们应该视不同的情况采用不同的散列函数,这里给大家一些参考方向:

(1) 计算散列地址所需的时间;

(2) 关键字的长度;

(3) 列表的大小;

(4) 关键字的分布情况;

(5) 记录查找的频率。

3. 处理散列冲突的方法

3.1 开放定址法

所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。它的公式是:

fi(key) = (f(key)+di) MOD m (di=1,2,…,m-1)

例:假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},使用除留余数法(m=12)求散列表

也可以修改di的取值方式,例如使用平方运算来尽量解决堆积问题:

fi(key) = (f(key)+di) MOD m (di=1²,-1²,2²,-2²…,q²,-q²,q<=m/1)

还有一种方法是,在冲突时,对于位移量di采用随机函数计算得到,我们称之为随机探测法:

fi(key) = (f(key)+di) MOD m (di是由一个随机函数获得的数列)

3.2 再散列函数法

同时准备多个散列函数,当第一个散列函数发生冲突的时候可以用备选的散列函数进行计算。

3.3 链地址法

例:假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表,如下图所示

在上面个的链表中,如果没有发生冲突的话,元素后面的地址为空;如果有冲突的话就将他链接到下一个元素。

3.4 公共溢出区法

例:假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表,如下图所示

没有冲突的元素放在左边的表,有冲突的元素,将多余的元素放在右边的那个表。

4. 散列表查找的代码实现

在这里采用除留余数法构造散列函数,代码中还包括散列表的结构定义,散列表的初始化,插入关键字和查找关键字

#define HASHSIZE 12#define NULLKEY -32768// 定义一个散列表的结构typedef struct{
    int *elem;  // 数据元素的基址,动态分配数组
    int count;  // 当前数据元素的个数}HashTable;// 初始化散列表int InitHashTable(HashTable *H){
    H->count = HASHSIZE;
    H->elem = (int *)malloc(HASHSIZE * sizeof(int));
    if( !H->elem )
    {
        return -1;      //申请空间失败
    }
    for( i=0; i < HASHSIZE; i++ )
    {
        H->elem[i] = NULLKEY;      //迭代进行初始化,其中的NULLKEY是一个默认值
    }
    return 0;}// 使用除留余数法int Hash(int key){
    return key % HASHSIZE;        //除数一般小于等于表长}// 插入关键字到散列表void InsertHash(HashTable *H, int key){
    int addr;

    addr = Hash(key);     //只是得到一个偏移地址

    while( H->elem[addr] != NULLKEY )   // 如果不为空,则冲突出现
    {
        addr = (addr + 1) % HASHSIZE;   // 开放定址法的线性探测
    }

    H->elem[addr] = key;}// 散列表查找关键字int SearchHash(HashTable H, int key, int *addr){
    *addr = Hash(key);

    while( H.elem[*addr] != key )
    {
        *addr = (*addr + 1) % HASHSIZE;
        if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )   //后面那个条件说明循环回到原点
        {
            return -1;
        }
    }

    return 0;}

为你推荐以下文章

深入理解Java中的Map集合

支持向量机(SVM)详解

【儿童节礼物】Java从入门到进阶学习资料整理,你渴望变强吗?那就戳进来吧~

本文分享自微信公众号 - 轮子工厂(Programmer-ing),作者:独孤呆博

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我敢打赌,这份python入门教程看了绝对有用

    前段时间用Python刷了一些题,把刷题的过程遇到的一些小知识点总结了一下,都是一些比较基础的知识点,特别适合一些刚入门的新手看~

    谭庆波
  • 推荐一款特别厉害的在线工具,程序员的百宝箱

    今天发现了一款特别厉害的程序员在线工具网站,堪称程序员的百宝箱。可支持在线运行php、c、c++、go、python、java等主流语言,页面简单明了,通俗易懂...

    谭庆波
  • 卧槽,为什么你的程序执行到一半就退出了,原来是因为加了这个

    快到月底了,相信有很多人都和呆博一样,不是“快揭不开锅了”,而是已经快要把锅都吃了〒▽〒。没关系我们可以一起吃掉这篇精神食粮啊,营养又健康,如果觉得味道还不错,...

    谭庆波
  • 散列表(哈希表)

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

    用户1215536
  • 效率提高50倍!谷歌提出从图像中学习世界的强化学习新方法

    关于人工智能体如何随时间推移提升自己决策的研究正借助强化学习(RL)取得快速进展。在这项技术中,智能体在选择动作(如运动指令)时观察一系列感官输入(如相片),有...

    机器之心
  • 谷歌开源PlaNet,一个通过图像了解世界的强化学习技术

    通过强化学习,研究AI如何随着时间的推移提高决策能力的研究进展迅速。对于这种技术,智能体在选择动作(如运动命令)时观察一系列感官输入(如相机图像),有时会因为达...

    AiTechYun
  • 开发 | 谷歌开源强化学习深度规划网络 PlaNet

    AI 科技评论按:近日,谷歌在官方博客上开源了强化学习深度规划网络 PlaNet,PlaNet 成功解决各种基于图像的控制任务,最终性能与先进的无模型智能体相比...

    AI科技评论
  • 一个智能体打天下:谷歌、DeepMind重磅推出PlaNet,数据效率提升50倍

    通过强化学习 (RL),对 AI 智能体如何随着时间的推移提高决策能力的研究进展迅速。

    新智元
  • C语言算法设计之奇数魔方阵

    将1到n(为奇数)的数字排列在nxn的方阵上,且各行、各列与各对角线的和必须相同,如下所 示:

    诸葛青云
  • 提升RabbitMQ消费速度的一些实践

    https://blog.bossma.cn/rabbitmq/practices-on-improving-the-speed-of-rabbitmq-con...

    java进阶架构师

扫码关注云+社区

领取腾讯云代金券