`
cin_ie
  • 浏览: 47220 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

hash 算法

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

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

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

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

a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p   q   r   s   t   u   v   w   x   y   z  
1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26  

    刘丽   刘宏英   吴军   吴小艳   李秋梅   陈伟   ...  
姓名中各字拼音首字母   ll   lhy   wj   wxy   lqm   cw   ...  
用所有首字母编号值相加求和   24   46   33   72   42   26   ...  
最小值可能为3   最大值可能为78   可放75个学生
 

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


        成绩一   成绩二...  
3   ...          
...   ...        
24   刘丽   82   95  
25   ...          
26   陈伟          
...   ...          
33   吴军          
...   ...          
42   李秋梅          
...   ...          
46   刘宏英          
...   ...          
72   吴小艳          
...   ...          
78   ...          

上面这张表即哈希表。

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

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

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

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

二、哈希表的构造方法

1、直接定址法

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

地址   01   02   ...   25   26   27   ...   100  
年龄   1   2   ...   25   26   27   ...   ...  
人数   3000   2000   ...   1050   ...   ...   ...   ...  
...                                  

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,则:

  5864     5864  
  4220     0224  
+)   04   +)   04  
  -----------     -----------  
  10088     6092  
  H(key)=0088     H(key)=6092  
               
  (a)移位叠加     (b)间界叠加  

5、除留余数法

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

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

6、随机数法

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

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

分享到:
评论

相关推荐

    高运算性能,低碰撞率的hash算法MurmurHash算法.zip

    MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...

    Java实现GeoHash算法

    Java实现GeoHash算法是一种在IT领域中用于地理位置数据存储和检索的技术。GeoHash将经纬度坐标转换为字符串,使得地理位置可以被高效地索引和查询。这种算法利用了空间分割和编码策略,使得相邻的位置在编码后具有...

    图像的相似度Hash算法(aHash的delphi实现).rar

    在IT领域,Hash算法是一种广泛应用于数据验证、存储和比较的技术。它将任意长度的数据转换成固定长度的输出,通常称为Hash值或指纹。在这个压缩包中,我们重点关注的是图像的相似度Hash算法,特别是平均哈希算法(a...

    20多个常用的Hash算法C++ 实现

    Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!

    geohash算法实现Java代码

    GeoHash算法是一种基于地理坐标的分布式空间索引技术,它通过将地球表面的经纬度坐标转化为可比较的字符串,使得我们可以高效地进行地理位置的搜索、范围查询以及邻居查找等操作。这种算法尤其适用于大数据和分布式...

    Hash算法MD5实验报告材料.doc

    "Hash算法MD5实验报告材料" 本实验报告主要介绍了Hash算法MD5的实验报告,旨在通过实际编程来了解MD5算法的加密和解密过程,并加深对Hash算法的认识。 一、Hash算法的定义 Hash算法是一种将输入数据转换为固定...

    几种经典的Hash算法的实现(源代码)

    ### 经典Hash算法概述与实现 #### 一、引言 哈希算法在计算机科学领域扮演着极其重要的角色,特别是在数据检索、信息安全以及数据完整性校验等方面。它能够将任意长度的数据转换成一个固定长度的哈希值,这一过程在...

    hash算法工具类

    一个hash算法的工具类,里面包含了一些常用的hash算法

    hash算法相关介绍

    ### Hash算法相关介绍 在计算机科学领域,哈希(Hash)是一种将任意长度的数据映射为固定长度数据的技术。哈希算法广泛应用于多种场景中,包括但不限于数据完整性验证、密码存储、快速查找等。本文主要介绍了几种...

    C语言实现hash算法

    在IT领域,哈希算法(Hash Algorithm)是一种用于将任意长度的数据转化为固定长度输出的算法。这个过程通常称为哈希或散列。哈希算法在信息安全、数据完整性验证、密码学等多个方面都有着广泛的应用。本项目是用...

    常用的hash算法(java实现)

    在计算机科学中,哈希(Hash)算法是一种用于将任意长度的数据映射为固定长度输出的函数。这种输出通常称为哈希值或消息摘要。在Java编程语言中,实现哈希算法可以方便地用于数据验证、查找表以及密码存储等多种用途...

    实验五:安全Hash算法SHA-1的实现

    ### 安全Hash算法SHA-1的实现 #### 一、Hash函数与数据完整性 Hash函数在现代密码学中扮演着至关重要的角色,它能够确保数据的完整性和一致性。一个典型的Hash函数接受任意长度的数据输入,并产生固定长度的输出,...

    geohash算法实现

    Geohash算法实现,经纬度到geohash编码的实现

    geohash算法mysql版代码

    网上有很多geohash算法的实现,都是基于java或者php代码实现的,没有sql实现的版本,这里使用mysql简单实现了这个算法

    Hash算法实验

    Hash算法在IT行业中扮演着至关重要的角色,尤其是在信息安全和数据完整性验证方面。本实验主题为“Hash算法实验”,主要涉及的是密码学中的消息摘要技术,具体是使用MD5(Message-Digest Algorithm 5)算法对文件...

    Geohash 算法的純 C 實現 将所在地球位置经纬度编解码為一定格式字串 有志於開發外送派單工程師請享用~~

    Geohash算法就是将经纬度编码,将二维变一维,给地址位置分区的一种算法 此檔案為C語言實現 函式庫使用介紹: 1)編碼 char* geohash_encode(double lat, double lng, int precision); 以所需精度獲取緯度和經度並...

Global site tag (gtag.js) - Google Analytics