PHP数据结构(十五) ——哈希表​

PHP数据结构(十五)——哈希表

(原创内容,转载请注明来源,谢谢)

一、概述

查找的效率与查找的次数有关,查找的次数越少速度越快。因此,希望能够一次查找出结果,此时键值一一对应,称满足这条件的f(k)为哈希函数。

1、定义

1)冲突

不同的关键字通过哈希函数,得到同一个地址,称为冲突。具有相同函数值的关键字称为同义词。

2)哈希表

根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映像到一个有限连续的地址集上,以关键字的“像”作为记录的位置,此表称为哈希表,映像过程称为哈希造表或散列,所得存储位置称哈希地址或散列地址。

2、性质

哈希函数是一个映像,设定灵活,任何关键字由此所得的哈希值落在表长允许范围内。

二、构造哈希表

对于关键字集合中的任意一个关键字,经哈希函数映像到地址集合中的任一地址的概率是相等的,称为均匀的哈希表。

1、直接定址法

取关键字或某个线性函数作为哈希地址,即H(key)=key,或(key)=a*key+b(a、b都是常数)。

该方法地址集合和关键字的大小一样,不会有冲突,但是实际上很少用到。

2、数字分析法

此方法适用于能够预先估计到全部的结果。假设关键字是以R为基的数(例如R=10的十进制),且可以知道哈希表的所有值,则可以用关键字的一部分组成哈希地址。

例如,10000-10099,可以用key0-99来表示。

3、平方取中法

取关键字平方和的中间几位作为地址。此方法类似数字分析法,将关键字进行平方的目的是拉大两个关键值之间的差距。该方法较为常用。因为平方之后的中间几位和这个数的每个数字都有关,具体位数由表长决定。

4、折叠法

将关键字分割成几部分,这几部分叠加和(舍去进位)作为哈希地址。当关键字很长,且分布均匀时,可以采用此方法。

5、除留余数法

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

即H(key)=keyMOD p(p<=m),该方法比较简单,而且可以结合折叠、平方取中等方式。但是要注意,选的数不能太小,也最好不要有很多因数,否则有可能取出来的余数相同的太多。最好选择20以上的质数来取余。

6、随机数法

选择一个随机数,取关键字的随机函数值为它的哈希地址,即H(key)=random(key)。通常,当关键字长度不等时采用此法构造哈希函数比较恰当。

三、构造过程需要考虑的因素

1、计算哈希函数所需的时间,包括硬件指令的因素。

2、关键字的长度。

3、哈希表的大小。

4、关键字的分布情况。

5、记录查找的频率。

四、冲突处理方法

使用哈希函数,很有可能会出现冲突,即多个数经过哈希函数得到同一个结果。此时,就需要冲突处理方法,来使得发生冲突的关键字能够得到一个单独的映射结果。冲突处理方法,用符号Hi表示。

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,-1,4,-4,9,-9…(m/2)2

3)伪随机数序列

以上三种结果各有好坏。

1)使用线性探测再散列,可以理解为取点i作为哈希值,如果发生冲突,就取i+1,如果还冲突,就取i+2。这样可以保证,只要哈希表还有空间,就一定能够取得哈希值。但是,这样速度会比较慢,特别是比较密集的区间,可以要连续做好几次的冲突处理才可以得到一个结果。

2)使用二次探测再散列,速度将比较快,因为其是采用平方的方式,而不是逐一递增,因此在经过i次的查找,其查找的范围达到i2,这样有效跳出一个大范围的区间。但是,因为这个方式不是逐一取结果,因此有可能最终没有找到能使用的哈希值。

3)伪随机数是随机的数,则结果不稳定,有可能特别快,也有可能特别慢。

2、再哈希法

Hi=RH(key)。即发生冲突时,换一种冲突处理方式,来解决冲突。

3、链地址法

该方法取得的哈希值键值不是一一对应的,而是一个哈希值指向一个存储空间,该空间是一个线性链表,由所有哈希结果一致的键组成。该方式可以保证哈希的结果足够快,不需要进行再哈希或者开放地址计算,也能保证每一个键一定可以有哈希值。但是,查找的时候相对速度较慢,因为需要在链表里面逐一判断结果。

4、建立公共溢出区

该方式为补救措施,即建立一个公共的区域,所有无法取得哈希的结果都放在此区域。该方式获取结果效率会比较低,但是作为补救措施,可以保证数据不丢失。

——written by linhxx 2017.07.15

相关阅读:

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-15

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

LeetCode_832. Flipping an Image_Solution

题目所描述的意思是对每个数组先进行取反,并且对数组中的每个元素进行取反转换,所以一共要执行两个操作。

662
来自专栏数说工作室

【SAS Says】基础篇:读取数据(中)

特别说明:本节【SAS Says】基础篇:读取数据(上),用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择。...

3385
来自专栏郭耀华‘s Blog

网易笔试编程题:被3整除

1242
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》 附录A NumPy高级应用A.1 ndarray对象的内部机理A.2 高级数组操作A.3 广播A.4 ufunc高级应用A.5 结构化和记录式数组A.6 更多

在这篇附录中,我会深入NumPy库的数组计算。这会包括ndarray更内部的细节,和更高级的数组操作和算法。 这章包括了一些杂乱的章节,不需要仔细研究。 A.1...

5086
来自专栏大数据挖掘DT机器学习

【面试】数据分析师常见的10道面试题解答

1、海量日志数据,提取出某日访问百度次数最多的那个IP   首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最...

4986
来自专栏蜉蝣禅修之道

Leetcode之Longest Valid Parentheses

1192
来自专栏ACM算法日常

简单计算器(栈的变种)- HDU 1237

测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输...

731
来自专栏计算机视觉与深度学习基础

Leetcode 22 Generate Parentheses 搜索与DP的纠结

Given n pairs of parentheses, write a function to generate all combinations of ...

1809
来自专栏Fish

CUDA PTX ISA阅读笔记(一)

不知道这是个啥的看这里:Parallel Thread Execution ISA Version 5.0. 简要来说,PTX就是.cu代码编译出来的一种东西...

2295
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

632

扫码关注云+社区