数据结构-hash表

什么是哈希表

哈希表(散列表)是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说,它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度。这个映射函数叫做哈希函数,存放记录的数组叫做哈希表。

给定表M,存在函数f(key),对任意给定的关键字值key,
代入函数后,
若能得到包含该关键字的记录在表中的下标地址,
则称表M为哈希(Hash)表,
函数f(key)为哈希(Hash) 函数。

根据给定的关键字key,运用hash算法得到下标,但是根据算法得到的数据可能会发生下标重复。需要处理hash碰撞冲突,主要有拉链法和线性探测法

优势

上面一堆废话,那hash为啥要这么搞呢(好处是啥)?

举个例子,假如我们现在要插入3个元素:12,15,22

假定数组默认大小是4(size)

给定一个hash算法【算法很多,这里给出一个简单的】h(key) = key%size

index = h(12) = 12%4 = 0

index = h(15) = 15%4 = 3

index = h(22) = 22%4 = 2

index则为元素插入后在数组中的下标

当要查询元素11是否存在的时候怎么查?

for循环遍历查询,如果数组容量很大的时候,根本行不通 如果套入同样的hash算法,是不是很快能得出一个下标,是不是马上可以精准的定位到元素应该被存在的位置

以下内容转载自哈希表原理详解【样式复制问题,个人博客中有原文地址】

还有哪些类似的取下标的算法

1,除法散列法 最直观的一种,上图使用的就是这种散列法,公式: index = value % 16 学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。(上个例子中的算法)

2,平方散列法 求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式: index = (value * value) >> 28 (右移,除以2^28。记法:左移变大,是乘。右移变小,是除。) 如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。

3,斐波那契(Fibonacci)散列法

平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。

1,对于16位整数而言,这个乘数是40503 2,对于32位整数而言,这个乘数是2654435769 3,对于64位整数而言,这个乘数是11400714819323198485

这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,即如此形式的序列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610, 987, 1597, 2584, 4181, 6765, 10946,…。另外,斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。

对我们常见的32位整数而言,公式: index = (value * 2654435769) >> 28

注:用斐波那契散列法调整之后会比原来的取模散列法好很多。

适用范围 快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

基本原理及要点 hash函数选择,针对字符串,整数,排列,具体相应的hash方法。 碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

散列冲突的解决方案

1.建立一个缓冲区,把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时,发现找的不对,就在缓冲区里找。

2.进行再探测。就是在其他地方查找。探测的方法也可以有很多种。

(1)在找到查找位置的index的index-1,index+1位置查找,index-2,index+2查找,依次类推。这种方法称为线性再探测。

(2)在查找位置index周围随机的查找。称为随机在探测。

(3)再哈希。就是当冲突时,采用另外一种映射方式来查找。

本文分享自微信公众号 - JAVA知识总结与分享(summing_up_sharing),作者:爱笑的阿杰

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

原始发表时间:2020-01-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • springBoot学习(二)配置环境动态切换和部分注解的运用

    建立第一个配置文件(springBoot默认读取的文件)application.properties

    杨小杰
  • springBoot学习(五)springBoot自定义banner与web开发

    通过 springBootTestRun.setBannerMode(Banner.Mode.OFF);

    杨小杰
  • 数据结构-栈

    栈(英语:stack)又称为堆栈或堆叠,栈作为一种数据结构,它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹...

    杨小杰
  • Salesforce mainframe UI source code

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    Jerry Wang
  • Salesforce mainframe UI source code

    Jerry Wang
  • Python自定义一个数组类,支持数组之

    py3study
  • 国外FPGA四大巨头简介

    FPGA (Field Programmable Gate Array)现场可编程门阵列,是在硅片上预先设计实现的具有可编程特性的集成电路,它能够按照设计人员的...

    碎碎思
  • 从零开始学 Web 之 移动Web(九)微金所案例

    相关源代码已放置github:https://github.com/Daotin/Web/blob/master/Code/src/11/wjs.zip

    Daotin
  • 任务调度并行算法的Java简单实现

    今天下午抽空写了下并行调度算法的Java版本,是想把这个思路先实现了,后面改写Python版作为参考,调试这个版本之后,再来写Python版,发现差别还不小。 ...

    jeanron100
  • Django+xadmin打造在线教育平台(七)

    代码 github下载 十、授课教师  10.1.讲师列表页 拷贝teacher-list.html和teacher-detail.html到template...

    zhang_derek

扫码关注云+社区

领取腾讯云代金券