Hash表理解
言归正传,哈希表又名散列表,其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。
一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 (key-value这样的数据,要恰当的选择key,一般情况下key和value是等同的)
大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。
具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。 (key转换后成为数组的下标,value作为数组的值)
不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。
前面讲的查找方法是基于比较的方法,查找效率依赖比较次数,其实理想的查找是希望不经比较,一次存取便能得到所查记录。这样就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,查找k时,只要根据这个对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希(hash)函数。按这种思想建立的表叫哈希表(也叫散列表)。
哈希表存取方便但存储时容易冲突(collision):即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是哈希表查找的关键。
1.哈希函数的构造方法
构造哈希函数的方法有很多,这里介绍几种常用的。
直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)
如:人口数字统计表
地址
|
1
|
2
|
3
|
...
|
100
|
年龄
|
1
|
2
|
3
|
...
|
100
|
人数
|
67
|
3533
|
244
|
...
|
4
|
数字分析法:取关键字的若干数位组成哈希地址
如:关键字如下:若哈希表长为100则可取中间两位10进制数作为哈希地址。
81346532
|
81372242
|
81387422
|
81301367
|
81322817
|
81338967
|
81354157
|
81368537
|
平方取中法:关键字平方后取中间几位数组成哈希地址
折叠法:将关键数字分割成位数相同的几部分(最后一部分的位数可以不同)然后取几部分的叠加和(舍去进位)作为哈希地址。
除留余数法:取关键字被某个不大于表长m的数p除后所得的余数为哈希地址。
H(k)=k mod p p<=m
随机数法:H(k)=rondom(k)。
2.处理冲突的方法
假设地址集为0..n-1,由关键字得到的哈希地址为j(0<=j<=n-1)的位置已存有记录,处理冲突就是为该关键字的记录找到另一个"空"的哈希地址。在处理中可能得到一个地址序列Hi i=1,2,...k 0<=Hi<=n-1),即在处理冲突时若得到的另一个哈希地址H1仍发生冲突,再求下一地址H2,若仍冲突,再求H3...。怎样得到Hi呢?
开放定址法:Hi=(H(k)+di) mod m (H(k)为哈希函数;m为哈希表长;di为增量序列)
当di=1,2,3,... m-1 时叫线性探测再散列。
当di=12,-12,22,-22,32,-32,...,k2,-k2时叫二次探测再散列。
当di=random(m)时叫伪随机探测序列。
例:长度为11的哈希表关键字分别为17,60,29,哈希函数为H(k)=k mod 11,第四个记录的关键字为38,分别按上述方法添入哈希表的地址为8,4,3(随机数=9)。
再哈希法:Hi=RHi(key) i=1,2,...,k,其中RHi均为不同的哈希函数。
链地址法:这种方法很象基数排序,相同的地址的关键字值均链入对应的链表中。
建立公益区法:另设一个溢出表,不管得到的哈希地址如何,一旦发生冲突,都填入溢出表。
3.哈希表的查找
例:如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]:
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
14
|
01
|
68
|
27
|
55
|
19
|
20
|
84
|
79
|
23
|
11
|
10
|
|
|
|
当给定值k=84,则首先和a[6]比,再依次和a[7],a[8]比,结果a[8]=84查找成功。
当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记录。
分享到:
相关推荐
Hash表应用 (必做) (查找) [问题描述] 设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; ...
C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。
c语言hash表源码 来自于开源软件项目
从linux内核提取出来的,双向链表和hash表实现。在普通的用户态C程序中,均可使用
stm32f407平台上实现的hash算法
自己实现的hash表,自己的hash函数,优化了的内存管理
封装hashtable的两级hash表,两个键值索引和访问。适合存放稀疏数据,如稀疏矩阵,稀疏表等结构,由于提供key-value的索引遍历,数据稀疏的情况下,相比于传统矩阵遍历的速度更快。
C++写的hash表模板类,效率还是很不错的。另付有测试代码和可运行文件
打造最快的Hash表.doc 据说来自暴雪 nop nop nop nop
基于HASH表和SYN计算的TCP包重组方法.rar
该文档消息描述了hash表的创建、数据插入、数据删除、数据查找以及hash表销毁等操作
Hash表采用了数组加链表的结构,即一个数组元组中不再是存储单个元素,而是存储一个链表,就好比包租婆收租的时候,一个握把上面挂了一连串的钥匙一样。Hash表的引出是为了减少查询数据库操作所带来的时间问题,将...
数据结构第16次作业,hash表 Spellchecking Prerequisites, Goals, and Outcomes Prerequisites: Students should have mastered the following prerequisite skills. • Hash Tables - Understanding of the ...
本人的数据结构实习作业“基于Hash表的代码相似度度量”,代码简洁明了,可读性强,并附带较多的注释,方便他人查看。一般通过查看注释便能了解程序的结构与功能,方便进行修改。以下是实习作业的具体要求: 对于两...
简单的hash学习程序。 关于Hash的详细介绍请见我的文章http://blog.csdn.net/yankai0219/article/details/8185796
hash表操作函数 HASH_ADD_INT HASH_ADD_STR
NULL 博文链接:https://zzqrj.iteye.com/blog/512827
base64加解密, hash表, fnmatch的windows下的实现简单实现版本。是从mosquitto的auth_plug中copy和https://blog.csdn.net/tttmt/article/details/24824291?utm_source=blogxgwz8 看到的 c语言代码。在qt上测试了
hash表的源代码#include <stdio.h> /*标准输入输出函数库*/ #include<stdlib.h> /*标准函数库*/ #include<string.h> #define HASH_LEN 50 /*哈希表的长度 */ #define M 47 #define NAME_N 30 /*人名拼音的最大个...