通俗的说，程序是能够完成既定目标的具有特定逻辑组织形式的指令集序列。既然有现实的需求，那么我们知道外界环境必然会给予程序某些特定形式的“输入”，然而在机器的内部，这种“输入”将转换为数据的形式，继而这就要求我们为用以描述现实世界需求的数据建立一个结构化的模型，使其能够被机器指令高效的处理。通常，对于数据的处理无外乎以下几种：读取/更新/删除数据项，或者插入新项，其中除插入外其他几种操作均要求对集合进行搜索。而结构化的模型可以通过数组、链表或者树形结构等建立，不同的建模方式对于数据处理中的各种操作有不同的性能表现。由于本文是偏向介绍算法，所以对于数组、链表等数据结构只做简单介绍，并将由这两种结构引出本文的主题——散列，而对树结构的介绍及对其进行操作的算法将会写在后续文章中。一般地，数据结构将直接影响对其处理的算法的选择，在本文中的散列函数算法又会反过来影响散列表这种结构之于数据的存贮效率，可以说，数据结构与算法的关系就好比是一卵双生。
我们先简单看一下数组与链表这两种数据结构存储数据的方式：
图1
由上图，我们可以得出以下几点：
- 通常对于动态集合的插入操作几乎总是会预留一定的资源，通过额外的空间记录现有元素集合的大小或是链表的表头/尾，对于插入某个元素来说总是占用常量的运行时间O(1)。
- 因为读取/更新/删除操作均建立在搜索的基础上，因此运行效率取决于定位某个所要操作的数据项的时间。我们首先来看数组结构，如果所存储的元素集是无序的，那么搜索集合中的任一元素的期望时间E=(1+2+…+n)/n=O(n)，因此从直观上来讲搜索某个数据项我们几乎总是需要遍历整个集合。如果需要大量的搜索操作，那么对于现有集合可以通过排序操作执行适当的预处理，并在此之后调用运行时间为O(㏒n)二分搜索可以获得较好的整体性能。但这几乎总是受到外界环境不稳定因素的限制，例如动态插入操作将导致现有结构的序性质遭到破坏，并且由之前的排序系列可知这种预处理将会消耗O(n)或是O(n㏒n)的运行时间。再来看链表结构，因为除表头之外，每一个元素都是根据其前驱进行定位，这种无法提供随机访问能力的性质决定了即使对链表进行排序也无法运用二分搜索快速查找具有某个固定值的元素，因此同未排序的普通数组一样，链表的搜索操作的期望时间也为O(n)。对于数据处理中的读取/更新，上述分析已然足够，但如果更加深入的思考删除操作，我们发现在有序的普通数组中还需要将已删除数据项所占位置之后的元素逐个前移，使得在维持序关系时整个数组仍然保持紧凑，而在链表中，虽然只需改变待删除数据项的前驱的指向，但高效利用空间的前提条件将会要求我们能够维护一个空闲链表(freelist)，这些都需要额外的时间开销。
- 最后我们知道这两种结构的存储空间利用率都很高，谁说这不是一个优点呢，至少对于散列来说是的。
需要注意的两点是，以上是在单链表情况下对链表进行分析的，而在实际中可以运用的链表还有双向链表，循环链表等等，数据结构的合理选择总是需要考虑特定的应用需求和外部环境，另外上述集合中的元素分别表示某一个变量，并非表示与其对应的ASCII字符。
什么是散列
在解释散列的含义之前，我们先来深入的观察一下普通数组这种数据结构，由图1所示，将集合{a,b,c,d,e,f}存储在数组中时占据了索引为0~5的6个存储空间，我们可以形式化的表示为有序对(Anorderedpair)的集合，即{(a,0),(b,1),(c,2),(d,3),(e,4),(f,5)}。但其实这个集合中的任意一个有序对的元素之间的关系是未定义的(undefined)，因此这样的有序对集合可以有66个。然而我们是否可以构造一个关系，使得待存储的集合{a,b,c,d,e,f}中的任意一个元素通过这个关系都能找到一个指定的索引值（也可以是集合中的一个元素的某个组成部分作为被散列的对象，而该元素的其他部分作为“卫星数据”，但这里我们为了简单化直接假定这些元素是不可分割而直接用于散列），由下图更形象的表示：
图2
根据上图我们知道原有集合中的元素被散列之后所得到的有序对的集合为{(d,0),(b,2),(c,2),(a,3),(f,4),(e,5)}。其中，散列表中的槽（或可称为“桶”）1为空，表示经过散列函数作用之后，原集合中没有任何元素被散列至该位置，而槽2中则存在两个元素，类似于hash(b)=hash(c)=2将两个不同元素散列至相同位置的情形我们称为碰撞(Collision)，如上图所标示的方法，我们通过链表将不同元素链接起来的形式解决碰撞，在后文中还将介绍另外一种称为开放寻址(Openaddressing)的解决方法。这里更具体的说明一下链接法的链接形式：因为散列至同一个槽的元素并无顺序上的先后要求，因此为效率计，我们将总是采用在链表头插入碰撞元素的做法，最终导致的结果是：与某个槽对应的链表中，越靠近链表头的节点，该节点中的元素被散列的次序越靠后。综上所述，我们对散列函数hash的形式化定义：
设在大小为N的集合中存在元素elem，存储原集合中元素的散列表共有m个槽位，则有
hash:elem→γ∈{0,1,2,…,m-1}
散列分析
这里主要是对链接法散列进行分析，其中有些问题与解决思路同样适用于开放寻址。由前文我们知道，对数据的操作主要有读取/更新/删除/插入，而这些操作中的多数又需要对结构化的数据具有快速搜索的能力，因为通过设计某个散列函数hash我们定义了集合元素与散列表下标之间一一对应的关系，从而使得搜索操作只需在常量时间内即可完成，即假定存在某个待搜索的关键字key，那么该关键字必定在槽hash(key)中，唯一值得关心的问题是，整个集合中的所有元素被散列之后的分布状况如何？在最坏情况下，有可能所选取的散列函数将所有元素均散列至同一个槽中，使得所有元素虽然名义上存储在散列表中，但实际上该表已退化为链表，因此由前文分析可知，最坏情况下的搜索操作将花费O(n)的运行开销。显然，我们并非因为散列具有这种最坏情况才去使用它，而能在多数情况下避免这种“退化”的要求将使我们更深入的思考以下两个问题：
- ①如何设计一个好的散列函数
- ②散列表的大小为多少较好，是否正如图2中所描述的，使用与原集合大小相同的散列表？我们将通过量化证明。
第一个问题我们放在后文说明，届时将给出一些散列函数的实例。这里我们主要针对第二个问题进行分析，即散列表的大小为多少较好？要回答这个问题，我们首先必须知道待散列的原集合的大小，因此：
设所有元素之间均相互独立，且每个元素被散列至每个槽的概率均相等 ------------> 假设①
并设原集合的尺寸为n，散列表的大小为m，装载因子α=n/m -------------->假设②
最重要的，我们并不考虑经过散列函数作用所消耗的计算开销 ---------------->假设③
由假设①中每个元素被散列至每个槽的概率相等，假设②中散列表的大小为m，有P{elem→γ∈{0,1,2,…,m-1}}=1/m
这里我们仍假定待查找的关键字为k，因此存在两种情况：Ⅰ、待查找关键字k不存在； Ⅱ、关键字k存在
然而其实情况Ⅰ的搜索开销即为情况Ⅱ的最坏情况运行时间，因为关键字k不存在时将查找整个链表
以下是更详细的分析：
------>Ⅰ、由假设①，并且根据假设②有装载因子α=n/m，所以α即表示每个槽所对应的链表的结点数，因为当待查找的关键字k不存在时，我们必将搜索到该槽对应的链表中的最后一个结点，综上，在这种情况下的搜索开销为O(α)。
------>Ⅱ、对于关键字k存在的情况，其实不做详细分析我们就已经知道，这种情况下的运行时间必然不超过O(α)，然而单单分析自身本身就是一件很有趣的事情，为何不做得彻底一些？更重要的是，下面所用到的这种方法，其体现的思想对于分析随机过程将具有极大的益处。
综上可知，如果我们将散列表设定为与原集合大小相同时即使得装载因子α=1，此时将有常量搜索时间，但其实设置为原集合尺寸的1/2或是2倍并没有多大区别，因为我们知道散列表越大，所占内存空间越大，而搜索时间越少，这里时间与空间总是一对矛盾统一体，某些参数的设置本身总会带有不可量化的成分，因而最终即可将散列表大小设为n。
设计散列函数
如何设计一个好的散列函数？这个问题需要一定的数论功底才能回答，有关数论的详细介绍见这里，借用高斯的一句话：“数论是数学的皇后”，我们便可管中窥豹，这种经过2000多年沉淀仍具有蓬勃生命力的纯粹数学所具有的极高地位。因此这一部分我不打算去详细解释为什么这样做，因为我的数论基础有限，对于散列函数我也只是知道这样的设计有好处，但是他的好处是说不清道不明的，并且实际上因为在理论方面是一块短板所以想要设计高效且合理的散列函数比较困难。尽管脱离了能够对其解释的理论，工程实践将会变得“矮”很多截，但这里所用的一些东西在实际生活中仍具有广泛应用，仅仅只是为了应用而去了解并积累他们仍是有趣的，最终我将用实例演示各种散列函数的性能表现。另外，无论是字符或是数据在机器内部总是以数值的形式表现，所以总能设置一种机制将任何输入转换为数值，例如对字符'a'进行散列，若将'a'解释为与其对应的ASCII码97，则hash('a')=hash(97)，只是当输入变得复杂时这种设计也将相应的增加复杂度，这里我们将避开这些复杂性而直接假设所有的输入均为某一个数。
- 除余散列法
设 hash(key)=key modm，其中key表示被散列的关键字，而m则表示散列表的大小，mod则为取余操作。
这是一种比较简单的散列函数，但简单并不意味着高效。特别是当待散列的原集合中元素之间存在某种模式时，这种散列法会有相当糟糕的性能表现。对该函数一个有用的指导原则是将m选取为接近待散列集合大小的质数。
- 乘法散列法
设 hash(key)=floor(m×(A×key mod1))，其中floor()表示对表达式进行下取整，A∈(0,1)，m如上同样表示散列表的大小，且在这种方法中对m并无任何特殊的要求。
[A×key mod1]表示将key乘上某个在0~1之间的数并取乘积的小数部分，该表达式等价于A×key-floor(A×key)
这里最重要的是A的值应该如何设定，Don•Knuth老大认为A=(√5-1)/2 [黄金分割点]比较好，至于为什么，我也不知道，直观上我认为选择0~1之间的任何无理数应该都没什么问题，比如A=√2/2或是√3/2，这里我们还是听老大的意思。
|
