散列

散列

散列表的实现常常叫做散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和查找的技术。但是,那些需要元素间任何排序信息的树操作将不会得到有效的支持。

散列表

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希函数

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面,散列函数的输入和输出不是一一对应的,如果两个散列值相同,两个输入值很可能是相同的,但不绝对肯定二者一定相等(可能出现哈希碰撞)。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

散列的价值

散列的价值在于速度
假如键没有按照一定的顺序进行保存,那么查询的时候就只能按照顺序进行线性查询,然而,线性查询是最慢的查询方式。所以,将键值按照一定的顺序排序,并且使用二分查找能购有效的提升速度。散列在此之上,更近一步,他将键保存在数组中(数组的查询速度最快),用数组来表示键的信息,但是由于Map的容量是可变的,而数组的容量是不变的。要解决这个问题,数组中存的并不是键本身,而是键对象生成的一个数字,将其作为数组的下标,这个数字就是散列码。
而这种办法所产生的问题就是下标重复。而我们的解决办法就是配合equals来确定键值。
查询的过程首先就是计算散列码,然后用散列码来查询函数(下标),通常,我们的数组中保存的是值的list,因此,我们计算出散列码之后,通过下表取到的对应部分的list,然后通过equals就可以快速找到键值。

处理冲突方法

分离链接法

其做法是将散列到同一个值的所有元素保存到一个表中。

执行一次查找,使用散列函数来确定究竟遍历哪个链表。然后在被确定的链表中执行一次查找。执行一次插入,检查响应的链表看看该元素是否已经处在适当的位置(如果允许插入重复元素,那么要留出一个额外的域,这个域当出现匹配事件时增1)。如果这个元素是新的元素,那么它将被插入到链表前端,这个不仅因为方便,还因为常常发生这样的事实:新近插入的元素最有可能不久又被访问。
除链表外,任何方案都可以解决冲突现象,一颗二叉树或者另一个散列表都可以,但是最好的解决方案是散列函数是最好的,那么所有的链表都应该是短的。

开放定址法

分离链接散列算法的缺点是使用一些链表。由于给新单元分配地址需要时间,因此倒着算法的速度有些减慢,同时算法实际上还要求对第二种数据结构的实现。另一种不用链表解决冲突的方法是尝试另外一些单元,知道找出空的单元为止。因为所有大数据都要放入表内,所以这种解决方案所需要的表要比分离链接散列的表大。一般来说对于不适用分离链接的散列表来说其装填因子应该低于0.5,这样的表叫做侦探散列表。这种通常的冲突解决方案有三种。

线性侦探法

平均探测法

双散列法

再散列法

对于使平方探测的开放定址散列法,如果散列表填的太满,那么操作的运行时间将开始消耗过长,且插入操作可能失败。此时,一种解决方案是建立另外一个大约两倍的大的表,而且使用一个相关的新散列函数,扫描整个原始散列表,计算每个元素的新散列值并将其插入到新表中,整个操作就是叫做再散列。

java标准库中的散列表

标准库包括Set和Map的散列表的实现:HashSet和HashMap类。HashSet中的项必须提供equals和hashCode方法。它们通常是用分离链接散列实现的。
散列表操作中费时多的部分就是计算hashCode方法,String类中的hashCode有个重要优化:每个String对象内部都存储它的hashCode值,初始为0,若hashCode方法被调用,那么就记住这个值,ru过hashCode对同一个String对象第二次计算,则可以避免昂贵的重新计算,这个技巧叫做闪存散列代码。

闪存散列代码之所以有效,是因为String类是不可改变的:要是String允许变化,那么它就会使hashCode无效,而重置回0.

可扩散列

处理数据量太大以至于装不进主存的情况。

查找性能分析

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。
查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
1.散列函数是否均匀;
2. 处理冲突的方法;
3.散列表的装填因子。
散列表的装填因子定义为:α= 填入表中的元素个数/散列表的长度
α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。
常用hash算法:
(1)MD4
(2)MD5
(3)SHA-1及其他

开发者首页 wechat
欢迎您扫一扫上面的微信公众号