第九章·词典

散列：原理

散列是一种赖以高效组织数据并实现相关算法的重要思想。

这样的思想背后的原理却非常直观、简单。

上图是IBM公司和联想公司的服务电话号码，能够看到这样的号码是由数字和字母共同组成的。字母的含义通常是公司名相关。而这些字母通过键盘输入后。仍然是数字。

循值訪问

对于訪问数据的方式，大致有例如以下分类

散列的实现原理

1. 以电话号码为例，关键码空间为存储全部电话号码的数组，比方从000000-999999。显然假设直接採用循位置訪问的方式，所占用空间将非常巨大而且实际利用率非常低。

2. 为了节省空间，散列採用一种“哈希表（散列表）”的方式存储关键码数据，称为散列地址空间。

3. 从关键码空间找到哈希表相应地址的过程称为“寻址”，这样的方式用一个“哈希函数”来实现。如图中所看到的，由关键码空间的key通过hash(key)找到哈希表中的&entry，再由此找到相应的词条entry。

4. 仅仅要哈希函数设计得当。能够使得转换过程的时间复杂度控制在常数范围。

5. 哈希表的空间M应该远小于可能空间R，同一时候稍大于实际空间N。

• 哈希函数的设计
  
  以电话号码为例，将电话号码对哈希表的长度取余，得到的余数即为哈希表的相应位置。

  

  1. 能够看到。此哈希函数的时间复杂度为O(1)
  2. 散列表的空间效率取决于实际空间N与哈希表空间M的比值，这一比值称为Load factor（装填因子）。简记为λ。

• 解决冲突
  
  因为哈希表是将一个相对较大的空间映射为一个较小的空间。那么必定存在不同的关键码在哈希表中占用同一个位置的情况。怎样解决这样的冲突呢？

  1. 精心设计散列表和散列函数。以尽可能减少冲突的概率
  2. 制定可行的预案，排解产生的冲突

散列：散列函数

散列函数设计标准

• 除余法：在除余法中，散列表长（也就是模）应该怎么选？

1. 假设将模取做2^k，这样对于数字计算是最高效的（与运算就可以），可是这样的方式的均匀性非常差。存在一个特定集合的数据经过除余后映射到散列表中的某一个特定单元。

2. 一种较为良好的策略是将模设定为素数。

此时。数据对散列表的覆盖能够达到最充分。在散列表中的分布也将达到最均匀。

3. 在訪问散列表数据时，通常是依照一个固定的“步长”S来訪问的，比方电话号码的步长为1.整个散列表长度为M。要达到均匀性的目的。就是要依照S的间隔訪问散列表的元素，能够遍历整个散列表空间。依照数论的知识，能够得到当且仅当(S,M)的最大公因子为1.因此M仅仅能为素数。

1977年。著名古生物学家史蒂芬·杰·古尔德（StephenJayGould）提出了一个新假说。觉得周期蝉这样做是为了避开自己的天敌。

他指出，非常多蝉的天敌也有自己的生命周期。假如周期蝉的生命周期不是质数，那么就会有非常多机会和天敌的周期重叠。

比方12年蝉就会和周期为2、3、4、6年的天敌重叠，被吃的可能性就要大非常多。

——蝉：生命周期为素数的进化论优势

• MAD法
  
  

  1. 由mad法的计算公式可知，b能够视为偏移量。这样能够解决不动点的缺陷。

     a相当于步长，亦即相邻元素的间隔。从而解决第二个缺陷。

  2. 散列的一个优势在于。其散列函数是能够灵活定制的。

     有些场合并不须要非常强的均匀性，比方几何计算。将高维空间的点压缩到低维空间时。仍然保持点之间的邻近位置。

     这样的方式称为Locality-Sensitive Hashing。password学也採用了特定的散列规则。比方消息摘要算法。

• 平方取中法
  
  
  
  注：取居中的数位的目的是使得原关键码每个数位都对散列地址构成接近的影响。

• 折叠法
  
  

• 伪随机数
  
  伪随机数的生成原理与散列原理非常类似，都是讲一个范围内的数随机、均匀、确定转换为还有一个范围的数。

  因此散列函数能够參考伪随机数的生成原理来设计。
  
  但注意：不同平台。或者同一平台不同版本号的伪随机数算法可能是不同的。因此假设直接套用伪随机数算法，将使得散列算法的移植性非常差。

• 多项式法
  
  原始关键码未必都是整数，也能够是字符串等其它结构。因此须要先对其进行转换。变成散列码HashCode。字符串型关键码的转换方式为多项式法：
  
  
  
  注：将字符先转换为相应的整数，将这些数分别视作为一个n次多项式的n个系数。计算出这个多项式的详细数值。并将其作为散列地址。

• 字符串折叠转换法
  
  除了多项式法之外，也有一种类似前面折叠法的转换方法。即简单讲字符代表的整数相加得到散列地址。

  这样的方法的缺点是将得到大量同样的散列地址。比方：
  
  
  
  由此能够看出：Harry Potter和VoldeMort是同一个人(HashCode转换函数必须非常复杂！

  )

散列：解决冲突

多槽位法

解决冲突的方式：在每个散列空间的bucket（桶）中，设置多个“槽位”。

假设在同一个桶中存在冲突。能够放置在不同的槽位中。



可是这样的方法的缺陷是：无法预知一个桶须要设置多少个槽位。

假设设置过多，则空间利用率将大幅减少。假设设置过少，则可能仍然存在冲突。

独立链法

使用列表：每个桶存放一个指针，冲突的词条组织成列表。



缺陷：因为不同的节点插入、删除顺序随机。因此对于不论什么一个列表而言。其节点空间可能不是连续分布。因此无法通过有效地缓存加速查找过程。当散列表的规模非常大，以至于要借助IO时，这一缺陷就更加突出了。

Question:这节中说道，独立链是动态生成的。也就是说有多少个实际关键码。就会生成多少个节点。那么，何不在刚開始就把全部实际关键码进行存储呢？

Answer：这是因为散列表的设计，是为了平衡时间和空间。假设将实际关键码进行顺序存储。那么每次查找的时间复杂度为O(n)，所需的空间最少。假设把关键码作为数组索引直接查找，那么时间复杂度仅为O(1)，可是须要可能超出有效空间几个数量级。

哈希表是一个在时间和空间上做出权衡的经典样例。假设没有内存限制，那么能够直接将键作为数组的索引。

那么全部的查找时间复杂度为O(1)。假设没有时间限制，那么我们能够使用无序数组并进行顺序查找，这样仅仅须要非常少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。仅仅须要调整哈希函数算法就可以在时间和空间上做出取舍。

——浅谈算法和数据结构: 十一 哈希表

开放定址

1. 封闭定址：在散列表中每个桶相应的列表中，其能够存放的元素仅仅能是在这个桶中发生冲突的词条。
2. 开放定址：放弃使用列表。全部的散列以及冲突排解都在一个独立、连续的封闭空间内，每个冲突词条都可能存在不论什么一个桶中。词条优先存放在其本来应该放置的桶中（即发生冲突的桶），假设本应该放置的桶已经存放了词条，则依照一定的次序查找下一个空桶进行存放（若已到达表尾，则回到表首继续查找直到不存在空桶为止）。这样的查找链称为该词条的“试探链”或者“查找链”。
3. 相应的。通过查找链查找冲突词条时。有两种结果：成功匹配；或者遇到空桶。查找失败。
4. 应用开放定址策略的散列称为“闭散列”。
5. 开放定址法Flash演示

.

• 线性试探
  
  线性试探是开放定址一种简单地实现方式。
  
  

• 懒惰删除
  
  之前说到。通过查找链查找时。假设遇到空桶，则查找失败。

  那么删除词条的方式不应该是将桶置空。而是应该使用一个删除标记。

  

• 平方试探
  
  为了解决线性试探可能导致冲突过于密集的情况。採用将间距扩大的方法。能够有效避免。平方试探即是将关键码的偏移量进行平方处理。

  
  
  平方试探的缺点是：可能存在空桶，可是试探链找不到。例如以下图所看到的
  
  
  
  这条定理的证明步骤例如以下，没看懂，就不解释了:(
  
  
  
  依据这条定理能够得出查找链在M/2取上整的各项互异。然而，有没有能够使得前M项都互异的方法呢？答案是有的。

• 双向平方试探
  
  
  
  双向平方试探也有一个缺点：正向子查找链和逆向子查找链可能存在除了起点0之外的共同元素。那么，他们的查找项之和无法全部覆盖表长。怎么解决呢？表长不仅设为素数，还设为特殊的素数：4K+3。使得查找链全部覆盖表长且互异。
  
  
  
  证明此结论须要用到双平方定理（费马提出）：
  
  
  
  详细证明步骤例如以下（呵呵，记住就好了）：
  
  

通排序、计数排序

通排序、计数排序的性能不全然取决于待排序元素的规模n。也取决于待排序元素的取值范围M。这样的算法的渐进时间复杂度为O(n+M)。这样的算法适用于M和n同阶或低阶的情况。



桶排序、计数排序的原理是利用散列，以字符排序为例：



1. 建立长度为26（字符总数）的散列表。其值包含count(计数)和accum(累计)。count表示当前字母出现的次数，accum表示当前字符在输入序列中的次序。accum是前面全部字符的count的总和。

2. count的计算能够在o(n)的时间内完毕：遍历待排序数组，在散列表相应位置累加计数就可以。

3. accum的计算能够在o(M)时间（即常数时间）内完毕，仅仅要将count累加就可以。

4. 通过count值和accum值，就可以确定当前字符在排序后的位置范围。

5. 这里仅仅是说明桶排序对散列表的应用。

很多其它桶排序、计数排序的原理參考