开发者社区> 技术让梦想更伟大-李肖遥> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

代码面试之哈希表

简介: 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。
+关注继续查看

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。

  对哈希表的使用者一一人来说,这是一瞬间的事。哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

  哈希表也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

  而且,也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力,就只能选择其他数据结构。

然而如果不需要有序遍历数据,井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

 

哈希表算法-哈希表的概念及作用

  一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。

  理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。

哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...

如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?

 

哈希表算法哈希表算法

 

用上述得到的数值作为对应记录在表中的位置,得到下表:

哈希表算法哈希表算法

 

上面这张表即哈希表。

如果将来要查李秋梅的成绩,可以用上述方法求出该记录所在位置:

李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

问题:如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录?

这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。

 

 

 哈希表算法-哈希表的构造方法

1、直接定址法

例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。

           但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

 

哈希表算法哈希表算法

 

2、数字分析法

有学生的生日数据如下:

年.月.日

75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...

经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。

3、平方取中法

取关键字平方后的中间几位为哈希地址

4、折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则:

 

哈希表算法哈希表算法

 

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

 

哈希表算法-处理冲突的方法


哈希表算法

如果两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:

1、开放定址法

Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

其中m为表长,di为增量序列

如果di值可能为1,2,3,...m-1,称线性探测再散列。

如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

称二次探测再散列

如果di取值可能为伪随机数列。称伪随机探测再散列。

例:在长度为11的哈希表中已填有关键字分别为17,60,29的记录,现有第四个记录,其关键字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:

 

哈希表算法哈希表算法

 

2、再哈希法

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

3、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

哈希表算法哈希表算法

 

4、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录

例如,按上面例9.4所给的关键字序列,用拉链法构造散列表如图9.14所示。 


  
  用拉链法处理冲突,虽然比开放定址法多占用一些存储空间用做链接指针,但它可以减少在插入和查找过程中同关键字平均比较次数(平均查找长度),这是因为,在拉链法中待比较的结点都是同义词结点,而在开放定址法中,待比较的结点不仅包含有同义词结点,而且包含有非同义词结点,往往非同义词结点比同义词结点还要多。
  如前面介绍的例9.4中,用线性探测法构造散列表的过程,我们知道,对前5个关键字的查找,每一个仅需要比较一次,对关键字49和24的查找,则需要比较2次,对关键字38的查找则需要比较4次,而对43的查找则需要比较3次。因此,对用线性探测法构造的散列表的平均查找长度为:
    ASL=(1×5+2×2+3×1+4×1)/9 ≈1.78
而用拉链法构造的散列表上查找成功的平均查找长度为:
    ASL=(1×5+2×3+3×1)/9≈1.55
显然,开放定址法处理冲突的的平均查找长度要高于拉链法处理冲突的平均查找长度。但它们都比前面介绍的其它查找方法的平均查找长度要短。

 

 

 


#define HASHSIZE 32    


//待存入表格数据

char *keywords[] = {
        "auto", "break", "case", "char", "const", "continue", "default", 
        "do",
        "double", "else", "enum", "extern", "float", "for", "goto", 
        "if",
        "int", "long", "register", "return", "short", "signed", "sizeof", 
        "static",
        "struct", "switch", "typedef", "union", "unsigned", "void", "volatile",
        "while"
};

char keybuf[HASHSIZE][10];
static char val_flag[HASHSIZE];
//标致已占用存储单元


void ClearFlag()
{
    int i;
    
    for (i = 0;i < HASHSIZE;i++)
    {
        val_flag[i] = (HASHSIZE+1);
//清标致位

    }
}

//哈希函数,从数据中抽出某个成员用于哈希值的计算

unsigned int hash(char *s)
{
    unsigned int hashval;
    int i = 0;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    hashval = hashval % HASHSIZE; 
//计算下标


    while ((val_flag[hashval] != (HASHSIZE+1)) && (i<32))
    {
        i++;
        hashval = (hashval + i)%HASHSIZE;    
//冲突处理,存储单元(下标)偏移

    }
    if (i<HASHSIZE)
    {
        printf("\n元素下标(%d): 冲突次数: %d -- ",hashval,i);
        val_flag[hashval] = hashval; 
//表示该单元被占用

        return hashval;
    }
    return -1;
}

int main(void) 
{
  int i, size, pos;

  size = sizeof(keywords) / sizeof(keywords[0]);
//计算关键字数量

 
  
//将数据存入哈希表

  ClearFlag(); 
  for(i = 0;i < size; i++)
     strcpy(keybuf[hash(keywords[i])],keywords[i]);

  
//根据数据结构中某个成员作为索引值,查找对应数据

  ClearFlag(); 
  for(i = 0; i < size; i++)
  {
    pos = hash(keywords[i]);    
    printf("%-10s: %-3d\n", keybuf[pos], pos);
  }

  return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
记十次面试字节/美团失败总结的《520道LeetCode题Java版答案》
去字节、美团、BAT等大厂面试,刷LeetCode上的数据结构+算法题是必修课。许多读者说,刷题的时候经常会遇到困难,想要找一本答案题解做参考。 下面分享几个用Java语言实现的开源LeetCode题解,也要感谢这些优秀的开源作者们,分享真的会让这个世界变得很美好。 LeetCode题解答案pdf(基于Java实现) 这是一本基于Java语言实现的LeetCode题解,格式为PDF,可作为刷题的辅助和参考,方便阅读,也方便打印出来学习。
12 0
Java面试30天计划Day01(JRE/JDK/JVM三者关系...)
Java语言的特点?JVM与JRE和JDK三者之间何关系?字节码是什么?Java是编译型还是解释型语言?为什么说是半编译/编译与解释共存? Java和C++有什么不同?Oracle JDK 与 Open JDK相比有什么不同?
19 0
Java面试30天计划Day02(变量/数据类型/标识符关键字...)
Java基本数据类型有哪些?注释哪几种?标识符与关键字区别?变量?break/contiune/return区别?字符型常量与字符串常量区别?局部变量与成员变量区别?
27 0
Map与Set高频面试算法题(只出现一次的数字,复制带随机指针的链表,宝石与石头,旧键盘,前k个高频单词)(Java实现)
给一个非空整数数组,只有一个元素出现了一次,剩余的元素都出现了两次,,请找出那个只出现一次的数字
22 0
阿里互联网一线大厂Java岗面试题库(2022年版)这次38k!稳了
前言 本文是为了帮大家快速回顾了Java中知识点,这套面试手册涵盖了诸多Java技术栈的面试题和答案,相信可以帮助大家在最短的时间内用作面试复习,能达到事半功倍效果。 本来想将文件上传到github上,但由于文件太大有的都无法显示所以直接整理成多个PDF,供大家学习
48 0
5.7w字?GitHub标星120K的Java面试知识点总结,真就物超所值了
如果你觉得在一些程序员平台获取到的资料太乱学习起来毫无头绪,但是单看《Java编程思想》相似的一类的Java圣经“枯燥无味”,那我推荐你看一下这份GitHub获得过120k标星的《Java面试知识点总结》PDF,虽然文档章节不多,但是短小精悍,其中总结了Java这几年大佬整理的所有心血结晶!
9 0
《Java开发者面试百宝书》电子版下载地址
敲黑板!Java求职者看过来!保姆级面试干货你要不要!《Java开发者面试百宝书》集结阿里Java大神一手面试经验诚意出品,精选了阿里官方出品的面试干货和面试建议,包括Java面试常见问题标准答案以及阿里技术大神为你总结的面试要点。
9 0
《Java开发者面试百宝书》电子版下载
敲黑板!Java求职者看过来!保姆级面试干货你要不要!《Java开发者面试百宝书》集结阿里Java大神一手面试经验诚意出品,精选了阿里官方出品的面试干货和面试建议,包括Java面试常见问题标准答案以及阿里技术大神为你总结的面试要点。
6 0
京东三面(后端)凭借这份Java面试复盘手册,已斩获60K*15offer
京东提前批一面: 简单的自我介绍 看我的项目取名叫“高级”,问我项目中怎么体现高级的(直接被人蒙了,瞎说了一通,把面试都逗笑了)? 怎么理解springboot、mybatis等框架的 如果没有mybatis,该怎么办(回答了用JDBC)那么mybatis和JDBC的区别是什么,为什么优先用mybatis mybatis是怎么操作数据库的,有哪些参数 你项目里用了kafka,怎么用的?只会用Kafka吗,用过其他的消息队列吗(我说用过blockqeue) ? 你项目里用到redis了,运用到了哪些场景?两大模块三大改进
18 0
CSDN社区分享面试经历活动作品27——java程序员求职总结
找工作已有半个月了,去了几家互联网或软件公司,诸如搜狐、人人、京东、华为等。回头一看,发现学到还不少,以前光顾着写代码,来不及注意到的地方都一一暴漏出来了。
1112 0
文章排行榜
最热
最新
相关电子书
更多
面试常考算法
立即下载
超全算法笔试-模拟题精解合集
立即下载
程序员面试宝典
立即下载