Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2585244
  • 博文数量: 877
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 5920
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-05 12:25
个人简介

技术的乐趣在于分享,欢迎多多交流,多多沟通。

文章分类

全部博文(877)

文章存档

2021年(2)

2016年(20)

2015年(471)

2014年(358)

2013年(26)

分类: Java

2015-01-06 19:17:22

哈希算法快速查表的原理

HashMap、Map等是很多公司面试、笔试的时候常考的题目,也是实际开发中经常用到的数据结构,必须好好掌握。因此我从《J2EE开发全程实录》中摘取了下面的片段,希望对同学们有帮助。学习时请对照着《数据结构》这门课中“散列”相关的章节复习。

    在实际问题中,按照给定的值进行数据查询是经常遇到的,比如,在电话号码簿中查询某个人的电话号码;在图书馆中按照ISBN 编号查找某本书的位置;在地图中按照坐标查找某个地点的地名等等。为此,人们创造了一种能够根据记录的关键码 ( 也就是用以标识数据在记录中的存放位置的数据项 ) 方便的检索到对应的记录信息的数据结构,这就是字典 ( Dictionary ) 

2.2.1字典的定义

我们都使用过字典,如英汉字典、成语字典,图书的检索目录、电话簿等也可以看作广义上的字典。在计算机科学中,把字典也当成一种数据结构。

我们把字典定义为“键- 值对” (Key-Value Pair) 的集合。根据不同的问题,我们为名字和值赋予不同的含义,比如,在英汉字典中,英文单词是名字,此单词的中文解释条目是值;在电话簿中,人名是名字,此人名对应的电话号码是值。

字典最基本的操作包括:find( 查找 )  add( 插入 )  remove( 删除 ) ,分别用来从字典中检索数据、插入数据和删除数据。在实际存储中,我们将“键 - 值对”存储于记录中,通过键 ( 也就是“键 - 值对”中的名字 ) 来标识该“键 - 值对”。“键 - 值对”的存放位置和其键之间的对应关系用一个二元组表示: (  , 值的位置 ) 

从字典中查找“键- 值对”的最简单方法就是使用数组存储,然后在查找的时候遍历此数组,当遍历到和被查找的“键 - 值对”的名字相同项的时候,这个“键 - 值对”就被找到了。这种最朴实的方式肯定是不能满足实际要求的,因此人们发明了一种检索效率非常高的组织字典数据的方法 ,即哈希表结构。

2.2.2哈希表与哈希方法

哈希方法在“键- 值对”的存储位置与它的键之间建立一个确定的对应函数关系 hash() ,使得每一个键与结构中的一个唯一的存储位置相对应:

存储位置=hash(  )

在搜索时,首先对键进行hash 运算,把求得的值当做“键 - 值对”的存储位置,在结构中按照此位置取“键 - 值对”进行比较,若键相等,则表示搜索成功。在存储“键 - 值对”的时候,依照相同的 hash 函数计算存储位置,并按此位置存放,这种方法就叫做哈希方法,也叫做散列方法。在哈希方法中使用的转换函数 hash 被称作哈希函数 ( 或者散列函数 ) 。按照此中算法构造出来的表叫做哈希表 ( 或者散列表 ) 

哈希函数建立了从“键- 值对”到哈希表地址集合的一个映射,有了哈希函数,我们就可以根据键来确定“键 - 值对”在哈希表中的位置的地址。使用这种方法由于不必进行多次键的比较,所以其搜索速度非常快,很多系统都使用这种方法进行数据的组织和检索。

举一个例子,有一组“键值对”:<5,  tom  > <8,  Jane  > <12,  Bit  > <17,  Lily  > <20,  sunny  >,我们按照如下哈希函数对键进行计算 :hash(x)=x%17+3 ,得出如下结果: hash(5)=8  hash(8)=11  hash(12)=15  hash(17)=3  hash(20)=6 。我们把 <5,  tom  > <8,  Jane  > <12,  Bit  > <17,  Lily  > <20,  sunny  >分别放到地址为 8  11  15  3  6 的位置上。当要检索 17 对应的值的时候,只要首先计算 17 的哈希值为 3 ,然后到地址为 3 的地方去取数据就可以找到 17 对应的数据是“ Lily ”了,可见检索速度是非常快的。

2.2.3冲突与冲突的解决

通常键的取值范围比哈希表地址集合大很多,因此有可能经过同一哈希函数的计算,把不同的键映射到了同一个地址上面,这就叫冲突。比如,有一组“键- 值对”,其键分别为 12361  7251  3309  30976 ,采用的哈希函数是:

public static int hash(int key)

{

return key%73+13420;

}

则将会得到hash(12361)=hash(7251)=hash(3309)=hash(30976)=13444 ,即不同的键通过哈希函数对应到了同一个地址,我们称这种哈希计算结果相同的不同键为同义词。

如果“键- 值 对”在加入哈希表的时候产生了冲突,就必须找另外一个地方来存放它,冲突太多会降低数据插入和搜索的效率,因此希望能找到一个不容易产生冲突的函数,即构 造一个地址分布比较均匀的哈希函数。常用的哈希函数包括:直接定址法、数字分析法、除留余数法、乘留余数法、平方取中法、折叠法等。应该根据实际工作中关 键码的特点选用适当的方法。

虽然采用合适的哈希方法能够降低冲突的概率,但是冲突仍然是不可避免的,处理冲突的最常用方法就是“桶”算法:假设哈希表有m 个地址,就将其改为 m 个“桶”,其桶号与哈希地址一一对应,每个桶都用来存放互为同义词的键,也就是如果两个不同的键用哈希函数计算得到了同一个哈希地址,就将它们放到同一个桶中,检索的时候在桶内进行顺序检索。

2.2.4Java中的 Map 接口

字典数据结构如此重要,以至于实际开发中经常需要使用它们。JDK 中提供了相关的类供我们使用,从而避免了自己开发字典类的麻烦。

在以前版本的JDK 中,最常使用的字典类就是 Dictionary 抽象类及其实现类 Hashtable ,不过在新版本的JDK 中不推荐读者使用 Dictionary 抽象类而是使用Map 接口,并且由于 Dictionary 的实现类 Hashtable 也实现了Map 接口,所以我们没有理由不使用 Map 接口。

Map接口有很多实现类,比如 HashMap  TreeMap  Hashtable  SortedMap 等,在第三方开源包中也有提供了更多功能的实现类,比如Apache-Commons 项目中的 LRUMap 。最常用的就是 HashMap  Hashtable ,它们最大的区别就是 Hashtable 是线程安全的,而 HashMap 则不是线程安全的,在使用的时候必须进行同步。由于JDK 中的工具类 java.util . Collections 提供了一个 synchronizedMap 方法,可以将非线程安全的Map 接口变量采用装饰者模式改造成线程安全的,因此使用 HashMap 的场合更多一些,后边的论述也将以 HashMap 为主。

2.3HashMap

HashMap Map 接口的实现类中最常用的一个,熟练的掌握这个类的使用将会提高解决问题的速度 

HashMap的主要方法

int size() :得到Map中“键-值对”的数量

boolean isEmpty() :Map是否是空的,也就是是否不含有任何“键-值对”

boolean containsKey(Object key) :Map中是否含有以key为键的“键-值对”

boolean containsValue(Object value) :Map中是否含有以 value 为值的“键-值对”

Object get(Object key) :从Map中得到以key为键的值,如果Map中不含有以key为键的“键-值对”则返回null

Object put(Object key, Object value) :向Map中存储以key为键、value为值的“键-值对”

Object remove(Object key) :从Map中移除以key为键的“键-值对”

void putAll(Map t) :将另一个Map中的所有“键-值对”导入到此Map中

void clear() :清除所有“键-值对”

Set keySet() :得到所有的键

Collection values() :得到所有的值

Set entrySet() :得到所有的“键-值对”,Set中的类型是Map.Entry



阅读(698) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~