算法在某个集合中找个一个或者多个的和等于某个固定值_哈希树(HashTree)查找算法..._weixin_39975055的博客-CSDN博客

e3296d9f6d217e3899f246b8a087c653.png

多年前,作者已公开发表过一篇关于哈希树查找算法[1]的文章[2]。在该文章中,作者已经初步分析和讨论过哈希树算法有关的理论依据、基本定义、构建方式以及相关特点。经过多年的公开检验,该算法已经得到了初步的理解和认可。作者同时也注意到哈希树查找算法中还存在诸多问题,需要进一步明确和补充,以方便读者理解和应用哈希树查找算法。

本文是对之前所发表文章的删减、修改、完善和补充,与之前所发表的文章差异甚大,请读者仔细阅读并予以区分。另外后面为了方便叙述算法或程序步骤,本文所有代码一律以Java语言的方式予以说明。

一、查找算法

在各种数据集合(包括数组、线性表、树等数据结构)中,数据记录[3]在集合中的实际位置[4]是随机的,和数据记录的关键字之间不存在确定的关系。因此在数据集合中查找数据记录时需要进行一系列关键字的比较。查找算法大多数是建立在关键字比较的基础上。

在顺序查找时,比较的结果为"

"与"

"两种可能。在折半查找、二叉排序树查找和树查找时,比较的结果为"

"、"

"与"

"三种可能。

查找的效率主要决定于查找过程中所进行的比较次数和时长。同等关键字模式 [5]下,又以比较次数为最主要的因素。

为确定数据记录在被查找集合中的实际位置,需和给定值进行比较的关键字个数(也即比较次数)的期望值称为:查找算法在查找成功时的平均查找长度(Average Search Length)。下面简单讨论一下在含有个数据记录的集合中,几种常见查找算法的平均查找长度。

在等概率的情况下,顺序查找的平均查找长度为:

对于折半查找(表要求是顺序表),在

比较大(

)的时候,可有以下近似结果:

在随机情况下(二叉树查找可能退化为顺序查找),对于二叉树,其平均查找长度为:

在平衡二叉树上进行查找,其平均查找长度为:

,其中

对于一颗阶的树,从根节点到关键字所在节点的路径上涉及的节点数可以说是平均查找长度的上限:

总的来说,这些查找算法的效率都将随着数据记录数的增长而下降。仅仅是有的比较快(时间复杂度为

,有的比较慢(时间复杂度是

)而已。

这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中,对数据结构[6]中数据记录的频繁增加和删除将不断地改变着原有的数据结构。这些操作将可能导致某些数据结构退化为链表结构,那么其性能必然将下降。为了避免出现这种情况而采取的调整措施,又不可避免的增加了程序的复杂程度以及操作的额外时间。

二、哈希函数

2.1定义

最理想的查找算法是不经过任何比较,一次操作便能得到所查的数据记录。那就必须在数据记录的实际位置和它的关键字之间建立一个唯一确定的对应关系

,使每个关键字和数据集合中某个唯一的实际位置相对应。

在依据给定值

查找时,只要根据这个对应关系

可以得到给定值的像。若数据集合中存在关键字

和给定值

相等的数据记录,则数据记录必定在

所指的实际位置上。由此,不需要进行比较便可直接取得所查的数据记录。在此称这个对应关系

为哈希(Hash)函数。哈希函数的平均查找长度是1,时间复杂度是

哈希函数是一种运用于计算机查找算法的函数,是一个实际应用。所有针对哈希函数的讨论,均是基于整数范围内的讨论。也即:给定值

、关键字

以及

应均为整数或整数序列。如果给定值

、关键字

或者

不为整数(例如:浮点数、字符串、字节数组等),均可以在计算机中"转化"为适用的整数或者整数序列予以表达。

2.1.1单调哈希函数

在某个关键字数值区间内,随着关键字数值的增加,哈希函数

单调递增或者单调递减,则称该哈希函数为单调哈希函数。单调函数保证了关键字集合和压缩映像集合的"一一映射"关系。

适用于单调哈希函数的性质和定理同样适用于能"一一映射"的哈希函数

例如:哈希函数

(

),在区间内

就是单调递增函数。

定义如下哈希函数

:对于所有正整数关键字进行开方运算,取小数点后三位的有效数字组成新的数字。显然这个哈希函数在区间内

不是单调函数。

给定值k

开方结果

sqrt(k)

0

0

0

1

1

0

2

1.414

414

3

1.732

732

4

2

0

5

2.236

236

6

2.449

449

7

2.645

645

8

2.828

828

9

3

0

10

3.162

162

……

……

……

100

10

0

2.1.2字符串取余操作

当关键字

是一个字符串时,可以将该字符串转化为字节数组。如果关键字

的字符串中没有任何本地语言字符(即全部均为ASCII码),则直接可以转换成字节数组;如果关键字的字符串中可能有本地语言字符,则可以依据本地字符集编码或者通用字符集编码,将字符串转换成字节数组。转化为字节数组后,即可按照字节数组进行取余操作。

在Java程序中,字符串可以按照char类型(unicode编码)进行访问,将char类型直接按照short类型进行处理。

1

2.1.3字节数组取余操作

1

2.2冲突

在哈希函数中对于不同数值的关键字有可能得到同一实际地址值,即

,而

。这种现象称做冲突(Collision)。

哈希函数是从关键字集合到实际地址集合的映射[7]。通常关键字的集合比较大,包括所有可能的关键字。而实际地址集合的元素则受限于所分配的物理空间。

例如:标识符可定义为以字符为首的8位字符,则以标识符为关键字的集合大小为

。如将其全部记录存储,则需要的物理存储空间大约为8.75TB。显然这个数据量已经超过常规计算机内存或磁盘的存储能力。

换个角度简单点说:设有4个关键字元素,都需要映射到实际地址集合中,地址编号从1到3。那么必然有两个元素会有同一个实际地址值,与具体所选择的哈希函数无关。这个压缩映射也是"抽屉原则"的体现。

总而言之,哈希函数是一个压缩映像函数,不可避免的要产生冲突。冲突只能尽可能地减少,而不能完全避免。

2.3评价哈希函数

同样的关键字集合和实际地址集合,可以有很多哈希函数可供选择。本节将讲述哈希函数的主要性质以及如何评价哈希函数。

2.3.1分辨能力

定义1:分辨能力

是指关键字集合经哈希函数的映射后,所得像集合中所有不重复元素的个数 [8]

像集合中至少要有一个元素,即

_。_例如:所有整数关键字元素都需要压缩映射到编号从0到9999的实际地址集合中。那么该哈希函数的分辨能力

;对于哈希函数

(其中为任意常数),该哈希函数的分辨能力

;对于哈希函数

,该哈希函数的分辨能力

;对于哈希函数

(

),该哈希函数的分辨能力

分辨能力的数值越大,说明哈希函数"越好"。当分辨能力

的时候,哈希函数的分辨能力最强,同时像集合所使用的实际物理空间也将是无穷大。实际应用中,是不可能有足够的资源来预先分配出所有的存储空间。因此对于分辨能力

的哈希函数是没有实际应用意义的。更多地是需要在分辨能力、存储空间和时间复杂度中寻找平衡点。

定理2:对于单调哈希函数,任何两个间隔不超过其分辨能力

的关键字不可能具有完全相同的压缩映像数值。

在整数范畴内,关键字

具有一定的排列规律,且这种排列是连续的。当哈希函数是单调函数时,那么从任意给定值

起始至

这个范围内,这样

个不同的关键字将拥有

种不同的压缩映像数值(否则就与预设条件矛盾)。也就是说,对于任意两个给定值

,如果间隔不超过

,就不可能获得同样的压缩映像数值。

2.3.2冲突概率

定义3:两个任意给定值

),导致哈希函数出现

的概率。这个概率被称作冲突概率

根据定义1,可知哈希函数分辨能力

意味着压缩映像集合中有

种不同元素。随机选择

个不同的给定值

,经过哈希函数映射后,得到

种不同状态的计数统计结果为:

。显然

某个压缩映像元素的冲突概率

为:

该哈希函数冲突概率

为:

由此可以看出,对于任意哈希函数的冲突概率计算是比较复杂的。

推论4:单调哈希函数的冲突概率

对于单调哈希函数,每种压缩映像元素出现的概率都相等,均为

。所以对于任意两个给定值

。出现

的概率是

,出现

的概率也是

,一共有

种状态。因此哈希函数的冲突概率(即

):

可以由上式看出:如果一个单调哈希函数的像集合中元素的个数仅有1个,那么冲突概率就是100%;如果一个单调哈希函数的像集合中元素的个数是无穷多个,那么冲突概率就是0。

2.3.3等价函数

判定5:两个具有相同分辨能力且每种压缩映像元素均具有相同冲突概率的哈希函数是等价函数。

严格的说:两种完全不同分辨能力的哈希算法肯定不是等价算法。但有些哈希函数随着关键字取值范围的扩大,分辨能力和每种压缩映像元素的冲突概率会相互接近。这些哈希函数被称为条件等价函数。

推论6:具有相同分辨能力或者冲突概率的单调哈希函数是等价函数。

由前面所述单调哈希函数的性质,以及判定5可以很容易证明上述推论。

如以下有两个单调哈希函数:

  1. 函数1:将所有整数关键字元素压缩映射到编号从0到9999的实际地址集合中。
  2. 函数2:将所有长度为8位标识符(字符串)元素缩映射到编号从0到9999的实际地址集合中。

那么函数1和函数2的分辨能力是相等的(

),因此函数1和函数2是等价函数。所以评价两个单调哈希函数是否等价,主要与压缩映射后的集合元素个数有关。

2.3.4模拟评估

当需要了解一个哈希函数的分辨能力和冲突概率时,直接的数学分析可能存在一定难度。这个时候,可以通过计算机模拟冲突来评估该哈希函数。

随机选择

个不同的给定值

,经过哈希函数映射后,得到

种不同状态的计数统计

。显然

此时可以将

认为是该函数的分辨能力,

认为是该函数的冲突概率。当随机选择的给定值

越多(即

越大),则模拟评估数值就越逼近目标值。

以2.1.1中所定义的哈希函数

为例,按照上述方法统计模拟分辨能力以及模拟冲突概率。

关键字取值范围

分辨能力D'

冲突概率λ'

[0,9]

7

0.244444

[0,99]

91

0.019192

[0,999]

675

0.002915

[0,9999]

979

0.001161

[0,99999]

998

0.001011

[0,999999]

1000

0.001001

[0,9999999]

1000

0.001000

由此表以及详细分析(包括每种压缩映像元素的冲突概率)可以得出结论:该哈希函数

与哈希函数

是条件等价函数。

2.4哈希函数分类

哈希函数的具体对应关系

有很多种类可选,实际上均可以简化和归纳为两种基本类别:商数类哈希函数

[9]和余数类哈希函数 [10]。

2.4.1线性类哈希函数

线性类哈希函数是指利用整数除法作为对应关系

生成方式的哈希函数。

为了方便讨论,将不超过实数

的最大整数称为

的整数部分,记作取整函数

(其中

)。那么一个整数数值

可以表达为:

,(其中

其中

部分被称为商,

称为除数,

称为余数(也可以表达为

)。

2.4.1.1商数类哈希函数

给定一个除数序列

,按照如下方式对整数数值求得一个结果序列

。这个结果序列的"倒序"

就是哈希函数的结果:

例如:

,除数序列

。结果序列就是

,其倒序就是

显然依据上例,当除数序列

中的元素均为10时,这个哈希函数的结果就是整数数值

的十进制计数结果。当除数序列

中的元素不完全相同时,此时哈希函数的结果可以称为变进制计数结果。在实际应用中,结果序列

和其倒序

均可以作为哈希函数的结果。具体使用哪一种,可以根据实际情况具体安排。

根据哈希函数的结果序列

,可以得到一个整数数值

(其中

实际应用中,除数序列

不可能有无限多元素,因此该哈希函数的分辨能力

就是整数数值

的数值范围。

另外可以证明在区间

内,该哈希函数为单调哈希函数,其冲突概率为

2.4.1.2余数类哈希函数

给定一个除数序列

,按照如下方式对整数数值求得一个结果序列

。这个结果序列就是哈希函数的结果:

例如:

,除数序列

。那么经哈希函数运算可以得结果

有关余数类哈希函数的分辨能力

的计算将会比较复杂,将放在后面进行讨论。此处只做一个初步的概念介绍。另外可以证明在任意一个长度为

的关键字区间内,该哈希函数为"一一映射"哈希函数。由于"一一映射"哈希函数与单调哈希函数具有相同的性质,所以其冲突概率为

如果知道了除数序列和余数类哈希函数的结果,那么如何求解满足这样的数?设整数

满足上述条件,那么由题设可以得到:

(其中

由于

相互独立,可令

。其实就相当于求解两条直线

的交点。由于两条直线的斜率不一样,所以必存在一个交点。把求得的该特解记为

。例如:对于指定的除数数列

和余数数列

,则

满足这样条件的通解

(其中

)。

2.4.2非线性类哈希函数

非线性类指是哈希函数为非线性函数。也就是说哈希函数完全使用非线性函数,或者非线性函数和线性函数混合使用。只要哈希函数使用了非线性函数,那么就被划分至非线类。

这些非线性类对应关系可以分成两类:非线性函数和分段处理方法。

2.4.2.1非线性函数

利用非线性函数构建的哈希函数被称为非线性哈希函数。这些函数主要导致映射后的像元素冲突概率发生不均衡改变,而并不能使哈希函数分辨能力的增加(甚至是减少)。

例如本文前面所定义的函数

。根据其描述,就可以推测这种哈希函数的分辨能力

。因为对于任意给定值

,其中的完全平方数,必然会被映射到像集合中的同一个元素上。这种哈希函数不会比线性哈希函数

具有更大的分辨能力

。另外在计算机中,整数运算更加简单快捷,所以这种非线性哈希函数是不会得到广泛应用的。在构建哈希算法时完全可以摒弃非线性哈希函数。

2.4.2.2分段处理方法

分段处理方法就是将任意给定值

分成若干部分,针对每个部分分别建立一定的对应关系

[11]。例如:某个手机号码一共11位(13001071272),前三位130代表了运营商,后续三位0107代表的归属地,1272则是用户识别码。这样可以加快查询手机用户的数据实际存储地址。而不是在用户数据集合中逐一比较。

假设任意给定值

可以被分成段

,每段所有可能的状态个数为

(其中

)。那么可以得出以下结论:

任何一个段的状态至少是有两个状态,或者换个角度说每一个段都是

进制。当所有

时,那么其实就等价于10进制计数;当所有

时,那么其实就等价于2进制计数;当所有

时,那么其实就等价于26进制计数,可以相当于英文单词字母。

例如:

,如果按照10进制分成四段,那么每段可以是9,5,2,7;如果按照2进制数值0010 0101 0011 0111,则可以分为16段;如果按照16进制数值2537,也可以分成四段。

由此可以发现分段对应关系可以看成是一种变进制计数方法,其与商数类哈希函数一致,完全可以将其归纳至由商数类表达方法中。

3哈希算法

依据哈希函数构建的查找算法被称为哈希算法。本文前面已经归纳和总结过:哈希函数可以简化和归纳为商数类哈希函数和余数类哈希函数。那么构建哈希算法,也就主要在这两类函数中选择或由这两类函数派生。另外对于哈希函数的评价方式,同样适用于哈希算法,包括分辨能力和冲突概率。

本节中先补充前面对余数类哈希函数分辨能力

的计算,然后对比两类函数的优缺点,最后说明哈希算法的基本构建思路。

3.1质数分辨定理

定理7:选取任意个互不相同的质数:

),定义:

),那么对于任意的,

)=(

)不可能总成立。

证明:假设定理7的结论不正确,那么对于任意的,

)=(

)将总是成立。这个可以表达为:

设:

显然,是

一个合数,而且包含质因素

。根据质数的定义和质因素分解定理,

可以表达为:

而另外一方面,根据

,可以得出:

很明显,这两个结论是相互矛盾的。因此原定理7正确。

这个定理7可以简单的表述为:个不同的质数可以"分辨"的连续整数的个数和他们的乘积相等。"分辨"就是指这些连续的整数不可能有完全相同的余数序列。

3.2余数分辨定理

在这里,对更为普遍的余数分辨方式做一个论述。

定理8:选取任意个互不相同的自然数:

),定义LCM(Lease Common Multiple)为的最小公倍数。

),那么对于任意的

,(

)=(

)不可能总成立。

证明:假设定理8的结论不正确,那么对于任意的

,(

)=(

)将总是成立。这个可以表达为:

设:

显然,

是一个合数,而且包含因素

。根据最小公倍数的定义,可以表达为:

而另外一方面,根据

,可以得出:

很明显,这两个结论是相互矛盾的。因此原定理8正确。

这个定理8可以简单的表述为:个不同的数可以"分辨"的连续整数的个数不超过他们的最小公倍数。定理7是定理8的一个特例。

3.3两类哈希函数的比较

3.3.1分辨能力的比较

由上述定理8可以得知,对于余数类哈希函数,其分辨能力

的大小是除数序列

的最小公倍数(LCM)。当除数数列中的元素相互互质【依据定理8】(或均为素数【依据定理7】)时,则分辨能力的大小为除数数列所有元素的乘积。

可以看出商数类哈希函数和余数类哈希函数的分辨能力

在表达形式上基本一致。因此从分辨能力这个角度来看,这两类哈希函数的优劣也就在伯仲之间。另外由于等价函数的概念存在,那么也意味着两者之间可以相互转化。

例如:对于商数类哈希函数

,选择除数数列

,则其对应的哈希函数实际上就是按照256进制计数的。同样可以构造一个余数类哈希函数

,选择除数数列

[12]。虽然这两个函数的计算方法和结果有所不同,但这两个函数的分辨能力

已经很接近。显然商数类哈希函数可以对每个bit物尽其用,而余数类哈希函数可能会有一定的浪费。

3.3.2除数数列的选择

商数类哈希函数比较直观和简单,实际应用中多采用分段方式进行处理。其除数数列的选择一般依据常用计数进制即可。余数类哈希函数则与除数数列的选择有密切关系,因此选择时有一定的技巧。在实际应用中,为了减少查询时间复杂度,可以选取较大数。另外依据定理8所选择的除数数列比依据定理7所选择的除数数列则略有优势。

例如如下四组除数数列:

利用这四组除数数列按照上述方式分别构建成的余数类哈希函数,具有差不多的分辨能力。但是时间复杂度明显不同,而且对数列

来说,其中还存在冗余。

这里推荐一种余数类哈希函数常用的除数数列。依据定理7,按照降序列出从251至2的连续32个质数

[13]。还可以依据定理8,再进一步优化除数序列

[14]。

这样安排的好处有如下几点:①实际应用中,哈希算法没必要每个质数都需要求余数,从大数开始有利于减少层次和查询次数;②所有的余数不超过256,可以通过字节数组表达余数数列;③可以形成足够大的总体分辨能力,降低冲突概率。

3.3.3在关键字处理上的差异

当给定关键字为整数类型时,使用商数类哈希函数具有一定的简便性和快捷性。通用计算机的整数类型表达目前不超过64bit(即8个字节),很适合按照256进制进行分段处理。这个也是商数类哈希函数的主要优势。理论上要求的除法和取余运算,实际应用中可以通过简单快捷的位操作予以解决。

但是对于不定长字符串或者较长的二进制关键字时,商数类哈希函数就存在一定的问题:商数类哈希函数需要确定一个最大对齐长度,以确定分段方式。

例如:整数最多8个字节,按字节进行分段;英文单词字典可以设定最大单词长度为32,按照字母进行分段。实际应用中,程序设计需要考虑可能存在的关键字长度上溢。

余数类哈希函数的主要问题在于对于关键字要进行整数取余运算。而按照目前的CPU水平,取余的整数除法操作几乎不算什么难事,但也会消耗一定的CPU时间。对于不定长字符串或者较长的二进制关键字,余数类哈希函数均可以处理,只是所需时间长短不同而已。实际应用中,考虑到所能存储的数据记录数量,以及关键字的实际情况,程序设计中会刻意限定一个最大长度。这个限制是人为限制,而并非理论上的限制。

3.4哈希算法的构建

依据哈希函数构建的查找算法被称为哈希算法。哈希算法可以依据单一的哈希函数而构建,也可以依据多个单一的哈希函数而构建。

当哈希算法依据单一的哈希函数而构建时,哈希算法的总体分辨能力与所依据的哈希函数相等,而且时间复杂度为

考虑到分辨能力

的哈希函数没有实际应用意义,而过于单一的哈希函数也无法完全满足实际应用的需求,因此有时需要构建一个由多层次单一的哈希函数"叠加"的哈希函数来满足实际应用。

选择一组对应关系

(其中

),通过"串联"或者"并联"方式来组合出一种新的哈希函数:

或者

显然对于两种组合方式,时间复杂度均为

的总体分辨能力取决于

中分辨能力的最小值。

的总体分辨能力计算较为比较复杂,但不低于

中分辨能力的最小值。因此最佳的多层次构建方式只能是"单纯"的并联方式。与并联形式相比,串联形式是应当被摒弃的。在实际构建时,要使得总体分辨能力尽可能的大,层次要尽可能少(以减少平均查找长度)。

哈希树

依据哈希函数查找算法要求,将数据集合中的数据记录按照一定的规律组织起来,形成多叉树结构。该数据结构可以被称为哈希树(HashTree)。

在这里假定所有的数据记录均以

的形式进行存储。其中

代表数据记录的关键字,

代表具体的数据。对于给定的数值

,查找的目的就是在数据集合中找到

的数据记录,或者返回数据集合中不存在这样的

。为了绘图和讨论的简便性,后面仅讨论和绘制关键字

部分。

为了后续算法说明的简便性,这里选择哈希函数的除数序列

。(其中)

表示除数序列数组的数值。例如:

。具体程序设计时,可以按照本文之前推荐的方法选择除数序列。

4.1组织结构

哈希树数据结构是一种典型的多叉树结构。

f4a53be026b1e5517d32284bd1e6219e.png

图1 典型的多叉树结构

但是哈希树数据结构与常见的多叉树又有显著的不同。下图是一个典型的哈希树数据结构:

f0c0ed2dd7588c9e7d0cb0cbd5d8cce4.png

图2 基于除数序列M的哈希树数据结构

如图2所示,该哈希树数据结构是基于除数序列构建的。

  1. Root为哈希树的根(深蓝色节点)。
  2. R0和R1为第一层节点(灰色节点)共有2个,对应除数序列中的第一个数

  3. R00、R01、R02、R10、R11、R12为第二层节点(黄色节点)共6个。其中R00、R01和R02是属于R0的子节点,R10、R11和R12是属于R1的子节点。R0和R1下分别有3个子节点,对应除数序列中的第二个数

  4. 后续的R00、R01、R02、R10、R11和R12节点下又分别有5个子节点(白色节点),对应除数序列中的第三个数

读者由本例可以推知,每一层节点下的子节点个数与除数序列的关系。哈希树数据结构的实际情况,与指定的除数序列有着紧密的联系。

4.2插入数据

(1)假设当前哈希树数据结构中没有任何数据记录,现在新插入一条数据记录

f5eeeae1b0e35a0d03993d132a940073.png

图3 在哈希树数据结构中插入一条数据记录

  1. 查询除数序列可知,根节点下应该有

    个节点。根据前面所描述得算法,将关键字数值取余可得

    。由于根节点下目前没有任何子节点,因此先生成一个子节点R1,并将数据记录放置至R1节点中。

a19bdafc2c7c6a3e9e02ec6d17002d54.png

图4 将数据记录放至R1节点中

(2)在此次操作完成之后,继续新插入一条数据记录

7423e223348317e80bdf2f08801e351e.png

图5在哈希树数据结构中插入一条新数据记录

  1. 查询除数序列可知,根节点下应该有

    个节点。根据前面所描述得算法,将关键字数值取余可得

    。由于根节点下目前没有任何子节点,因此先生成一个子节点R0,并将数据记录放置至R0节点中。

009057d742cdef60f11cefe5f4db33ac.png

图6 将数据记录放至R0节点中

(3)在此次操作完成之后,继续新插入一条数据记录

e89f93f50cfcca1af88529a3d7732c4c.png

图7在哈希树数据结构中插入一条新数据记录

  1. 查询除数序列可知,根节点下应该有

    个节点。根据前面所描述得算法,将关键字数值取余可得

    。调取节点R1的状态,发现该节点已经存储了一条数据记录。因此需要继续查询R1下的子节点寻找空出的存储位置。

  2. 查询除数序列可知,R1节点下应该有

    个节点。将关键字数值取余可得

    。由于R1节点下的R11节点并未生成,可以先生成R11节点,并将数据记录放置其中。

5d9dcdaf5e5ee0cc79202fa0e57a07b2.png

图8 将数据记录放至R11节点中

(4)按照上述的方法将关键字序列

依次添加到哈希树数据结构中,最后可以得到哈希树数据结构如下图所示

[15]:

137241d51af0d7b53e1ccd33f6177e52.png

图9 按照关键字序列K插入数据后的结果

这种数据插入方法的一个好处就是,可以优先占据接近根节点的子节点,降低单次操作中访问的次数,同时使树结构均衡化。按照这种数据插入方法,此哈希树数据结构中,最多可以存储的数据记录数量应大于该哈希算法的总体分辨能力。

4.3查找数据

在图9所示的哈希树状态下,进行数据查找。

  1. 查找的数据记录

    1. 查询除数序列可知,根节点下应该有个节点。根据前面所描述得算法,将关键字数值取余可得

      。调取节点R0的状态,发现该节点已经存储了一条数据记录,而且关键字不等于128。因此需要继续查询R0下的子节点。

    2. 查询除数序列可知,R0节点下应该有个节点。将关键字数值取余可得

      。由于R0节点下的R02节点节点已经存储了一条数据记录,且关键字等于128,因此该节点即为所查找的节点。

    3. 程序操作到此即可结束。
  2. 查找的数据记录

    1. 查询除数序列可知,根节点下应该有个节点。根据前面所描述得算法,将关键字数值取余可得

      。调取节点R1的状态,发现该节点已经存储了一条数据记录,而且关键字不等于31。因此需要继续查询R1下的子节点。

    2. 查询除数序列可知,R1节点下应该有个节点。将关键字数值取余可得

      。由于R1节点下的R11节点节点已经存储了一条数据记录,且关键字不等于31。因此需要继续查询R11节点下的子节点。

    3. 查询除数序列可知,R11节点下应该有个节点。将关键字数值取余可得

      。调取节点R111的状态,发现该节点已经存储了一条记录,且关键字不等于31。

    4. 由于节点R111是最底层节点,因此哈希树中不存在关键字所对应的数据记录。程序到此即可结束。

4.4删除数据

在图9所示的哈希树状态下,进行数据删除。显然删除数据的前提是能找到数据记录。因此在查找算法上,两者具有一致性,这里就不再赘述。

  1. 删除

    的数据记录。

    1. 找到所对应的数据节点R11,并将数据节点R11的状态设置为无数据状态。
    2. 程序到此即可返回。
  2. 删除

    的数据记录。

    1. 找到所对应的数据节点R003,并将数据节点R11的状态设置为无数据状态。
    2. 程序到此即可返回。

经过两次删除操作后,哈希树的当前状态如下图所示:

7d7cdaac977388e72b53a8a45bfa0998.png

图10 经过2次数据删除操作的后哈希树

在经过删除操作后,会出现末端空节点R003和中间空节点R11。考虑到充分利用存储空间的实际要求(避免哈希树的膨胀),可以对末端节点进行"释放"处理。对于中间空节点,可以考虑将最末端的节点挪动到该层上(形成末端空节点的,则需要释放)[16]。当然也可以放置不管,后续的插入数据可以直接利用这些空节点。无论如何操作都是为了保证树结构的平衡性,减少单次操作中的访问次数。

哈希树的特点

(1)结构简单

哈希树的结构非常简单,每层节点的子节点个数由除数序列指定,子节点可以随时动态创建。哈希树结构是动态的,不需要长时间的初始化过程,没有必要为不存在的关键字节点提前分配存储空间。

(2)易于实现

从上面所讲述的操作过程来说是相当简单的。程序上特别容易实现,比起

树更容易理解和实现。

(3)查找迅速

从前面的分析可以看出,时间复杂度是

(其中

为除数数列的长度)。实际应用中,平均查找长度应该小于

以推荐的除数序列

[17]为例。对于无符号4字节(即32bit)整数的,预估时间复杂度是

),平均查找查找长度要小于5。

(4)易于调整

从前面的删除操作可以看出,对哈希树的平衡操作十分简单:主要在于调整空节点。将最末端节点向前挪动至当前空节点,并释放末端空节点。

(5)非排序性

哈希树不支持整体排序,没有整体顺序特性。不过哈希树可以支持部分排序,只需要在插入数据时将较大(或者较小)数据逐节点交换至末端节点即可。不过这种部分排序性,目前尚未找到实际用途,与其他支持排序的数据结构相比也没有什么优势。

5.1数据插入溢出

在图9所示的哈希树状态下,再插入一条数据记录

。则会发现该数据记录路径上的子节点均有数据记录,已经没有位置给予新插入的数据,这种情况称为数据插入溢出。

对于指定的除数序列

和结果序列

,如果插入数列有如下形式,则会导致数据插入溢出:

其中

则是满足部分余数序列的特解

[18]。

出现数据插入溢出的概率

为:

当除数序列

时,可以得到数据插入溢出的概率

为:

当除数序列为本文推荐的除数序列

[19]时,逐级可以计算得到数据插入溢出的概率为:

层级

溢出概率

2

0.003921

3

6.127e-8

4

3.874e-15

5

1.041e-24

6

1.280e-36

7

6.870e-51

8

1.843e-67

9

2.436e-86

10

1.522e-107

……

……

32

<1.7e-308

由上表可以看出,按照本文推荐的除数序列是几乎不存在数据插入溢出,除非人为刻意去实施。实际应用中,随着哈希树中保留的数据量越来越多,出现插入溢出的概率会逐步提升。

对于这种数据插入溢出的情况,具体处理建议如下:

  1. 选择更长的除数数列。
    实际应用当中,选择尽量长的除数数列(例如本文推荐的数列长达32),因此可以将这种数据插入溢出的概率降至最低。
  2. 抛出异常。
    遇到数据插入溢出,则直接抛出程序异常。然后对原有程序设计和参数选择进行重新审视。

5.2哈希树的退化

哈希树的退化是指:经过哈希树经过反复的数据插入和删除之后,数据记录严重偏向并集中于树结构的某条或某几条分支路径上。这样的分支路径平均查找长度接近预设的最大查找长度。

从本文上面的对哈希树操作的分析可知:删除操作只可能减少分支路径的查询时间复杂度。因此只有数据插入才会导致分支路径的查询时间复杂度增加。一种极端的情况就是出现了数据插入溢出。因此可以将哈希树的退化问题与数据插入溢出问题同等看待。

在实际应用中,所插入的数据记录是不能事先估计的,哈希树只能被动的接受和处理。因此可以在哈希树代码中放入几个统计记录指标,用于衡量哈希树的退化程度。

  1. 实时统计哈希树的实际存储数据量。根据这个存储数据量可以估算出最大平均查找长度。
  2. 实时统计每次数据查询操作的查找长度,并求取平均值。将这个查找长度作为当前哈希树的实际平均查找长度。
  3. 如果实际平均查找长度和最大查找长度很接近,则说明可能存在比较严重的退化问题。
    对于这种哈希树的退化问题,具体处理建议如下:

(1)使用统计指标来检测和衡量退化问题严重程度。

(2)当出现严重的退化问题时,对原有程序设计和参数选择进行重新审视。

5.3与Tire树的区别

Tire树是一种字典树,也是一种多叉树结构。

f7437330ce6af60e0d1a4649144c71cd.png

图11 Tire树基本结构

实际上按照本文所叙述的理论,Tire树可以归结为商数类哈希函数。其采用26位计数进制方式(以英文字母为基础)。
下面是有关于英文单词的统计情况:

29c37f728297be6a4d8ee7ecbd73410f.png

图12 英文单词长度的分布情况

9c3a1afc86bbc6acf7048c44bbbb53c8.png

图12 英文单词长度绝大多数为8

7426a4c0188920c355d240769e5da617.png

图13 英文字母在英文单词种出现的频率

由以上数据统计可以分析得出Tire树的基本情况:
1. 最大查找长度至少要设置至20。
2. 平均最大查找长度应当接近于8。
3. 各个分支路径上的数据记录分布不均匀,某些路径上过多,某些路径上过少。

如果使用哈希树进行处理,则可以做到如下几点:

  1. 无需对英文单词的长度做出限制。
    只是单词较长时,取余运算需要消耗较多CPU时间。也可以对英文单词预先使用余数类哈希函数进行处理,将结果数值作为字符串的关键字。这样处理整数要远优于处理长字符串。
  2. 目前英文单词数量超过100万,常用单词5万。以本文推荐的除数数列

    为例,那么最大查找长度预估为3(256×255×253 = 16515840,远大于1000000),其平均查找长度应该不超过3。

  3. 数据记录都会靠近根节点,各分支路径数据是均衡的。可以通过优先插入出现频次高的单词,再插入出现频次低的单词,提高查询击中概率,减少平均查找长度。
    以上就是哈希树在处理英文单词时相对于Tire树的优势。

5.4与数组算法的比较

(1)假设有10000个映射后的元素存储空间,分别使用数组算法和哈希树算法处理。

使用数组算法,可以直接组织成

的形式,其分辨能力为

,冲突概率为0.01%。平均最大查找长度为1,时间复杂度

使用哈希树算法,可以选择除数数列

(选择两层结构是为了区别于数组算法,第一层其实可以直接选择一个10000附近的质数)。其分辨能力为

,冲突概率为0.01%。平均最大查找长度最大为2,时间复杂度

。两者是等价算法,但是在平均最大查找长度上并无优势。

(2)假设有不确定数量的字符串需要存储,每个字符串的长度最长为32字节,总数据量最大不超过2G。分别使用数组算法和哈希树算法处理。

此时再使用数组算法直接组织成

的形式不再适合于当前的问题。主要问题在于:

① 如何确定一个字符串在数组中的相对偏移量。

② 简单的字符串规律是否导致数据结构退化以及冲突概率偏高。

③ 如果只有一层组织结构,产生数据插入冲突又如何解决。

④ 是否需要采取Tire数据结构,平均最大查找程度又是多少。

这些问题归结到最后,其实还是需要在本文中寻找确切的解答。某种意义上来说:哈希树算法是数组算法的延申,也是数组算法中冲突的最佳解决方案

数据总量为2G的字符串,这些字符串最大长度为32。可以初步估计,这些字符串总计至少为2147483648个。当使用哈希树算法时,可以选择本文推荐的数列

。初步估计最大查找长度为4(256×255×253×351 = 4145475840 > 2147483648),实际平均最大查找长度应小于4。有关的冲突概率,冲突处理,数据溢出,退化问题均可以得到确切的答案。这个时候哈希树算法的相关优势就体现出来了。

参考

  1. ^哈希树算法,其英文名称HashTree算法。有很多不同应用领域的Hash算法也会使用该名称。因此同名但是不同用途的称呼很多,读者阅读时需要注意区分。
  2. ^作者之前发表的文章。 https://wenku.baidu.com/view/16b2c7abd1f34693daef3e58.html
  3. ^这里的“数据记录”可以简单理解为(key,value)对,即关键字和数值。
  4. ^这里的“实际位置”可以理解为内存地址,地址偏移量,或者指针等形式。
  5. ^同等关键字模式是指关键字(key)的在计算机中的数据类型。例如:整数,字符串等等。
  6. ^数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。也可以将数据结构理解为按照一定规律构建的数据集合。
  7. ^这种映射实际上是一种压缩映射。
  8. ^哈希函数和抽屉原则类似。
  9. ^商数类可以简单理解为:以商为主要处理对象。
  10. ^余数类可以简单理解为:以余数为主要处理对象。
  11. ^这种方法也属于一种“分而治之”的办法。
  12. ^255=17×5×3;254=2×127;253=11×23;251是素数。这些数是相互互质。
  13. ^从2至251的连续质数:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251。
  14. ^M={256,255,253,251,247,241,239,233,229,227,223,217,211,199,197,193,191,181,179,173,167,163,157,151,149,139,137,131,127,113,109,107}。共计32个数。这些数相互互素,它们的乘积约为2.372×1072(2256约为1.158×1077)。
  15. ^图中标识为直线的节点,表明该节点尚未创建;图中节点有编号无数值,则表明是没有存储数据的空节点。
  16. ^在本例中,可以把节点R111的数据记录拷贝到R11中,并释放节点R111。
  17. ^M={256,255,253,251,247,241,239,233,229,227,223,217,211,199,197,193,191,181,179,173,167,163,157,151,149,139,137,131,127,113,109,107}。
  18. ^参照2.4.1.2部分对B函数的说明。
  19. ^M={256,255,253,251,247,241,239,233,229,227,223,217,211,199,197,193,191,181,179,173,167,163,157,151,149,139,137,131,127,113,109,107}。

原网址: 访问
创建于: 2021-02-01 14:11:35
目录: default
标签: 无

请先后发表评论
  • 最新评论
  • 总共0条评论