第九章：词典
第九章：词典
散列：循值访问
散列：原理
用数组来存储电话号码，可能需要R = 10^8的空间来存储仅仅25000个电话号码，空间利用率很低。
采用散列表将N个数映射到容量为M的空间。
定址也就是散列，装填因子 = N / M，即存放的词条 / 桶数组容量。
当两个不同的key能够映射到同一个hash值的时候，称这两个key为同义词，此时发生了冲突。
在一般情况下，我们无法避免冲突。
散列：散列函数
好的散列函数应该做到确定、快速、满射和均匀。
聚集：词条集中到散列表内少数若干桶中，好的散列函数应该尽可能的映射均匀，避免聚集现象。
最常用的是除余法，即将key对M取模，一般M取素数，因为如果M取2的k次幂，此时对M取模操作等价于截取key的最后k位，前面的n-k位对地址没有影响。也就是说，只要最后k为相同就会发生冲突。
考察常用的以T为间隔的数字序列，如果以M为除余法的模数，不妨设第序列中第一个元素恰好是0，则序列为0，T，2T，3T，…。0被映射到散列表中秩为0的位置，只要序列足够长，当循环遍历到某个数kT时，kT也会被映射到秩0的位置，此时（kT） % M = 0，不难理解，在0被映射到秩为0的位置后下一个被映射到该位置的数kT必然是lcm（T，M），在kT之前没有发生冲突，已经成功将k个数映射到0到M-1的空间内，由kT = lcm（T，M），lcm（T，M）*gcd（T，M）=T*M得到kT = T*M/gcd（T，M），即k = M / gcd（T，M）。说明在首次冲突前，散列表中元素的个数是M除以T和M的最大公约数，当gcd（T，M）=1，时，冲突前表中已有M个元素，即装填因子为百分之百，实际生活中间隔T不固定，但只要M为素数，不论T取多少，他们的最大公约数始终是1，此时除余法也就能实现均匀的映射。
除余法的缺陷：有不动点0，以及是零阶均匀的，相邻的关键码散列地址必相邻。
一阶均匀：邻近的关键码散列地址不再邻近。
MAD法：hash（key） = （a*key + b） % M，满足一阶均匀。
平方操作可以看作一系列的左移位操作和加法操作（快速幂算法），因此如上图所示，平方结果的中间位是key中更多位数字共同作用的结果，所以平方取中法取中间几位数而不取左右的数。
多项式法经常用于字符串哈希，一般将字符串看作一个131进制的数来计算其在十进制表示下的值。由于涉及乘法运算较为复杂，可以用近似的方法实现，如上图所示，将字符串的每个字符都转化为int类型累加起来，然后将h的前5位与后27位互换位置。
散列：排解冲突
独立链法这里出现冲突采用头插法，缺点主要是空间不连续，系统缓存失效。
像独立链法那样只允许在映射到的地址开辟多余空间来排解冲突的叫做开散列，又叫做封闭定址；如果词条冲突时允许在散列表内部寻找另一空间存放，散列地址对所有词条开放的策略称为开放定址，又称闭散列。（PS：这样的别名真的不会引起歧义吗？）
这里给出了开放定址法相对与封闭定址法的优缺点：开放定址法的优点是简洁性，无须附加指针，查找链具有局部性，可以充分利用系统缓存，有效减少IO；缺点是已经发生过的冲突会导致本不必发生的冲突。
对于散列表的删除，如果直接删除会导致查找链被切断，后序词条可能访问不到，因此，需要采用懒惰删除的办法。
对于查找操作而言，遇见被懒惰删除的桶不应该停止，应该跳过它继续查找；对于插入操作而言，遇见懒惰删除的桶应该视为空桶，就地插入。
平方试探的优点在于没有线性试探的那种数据聚集现象，冲突时可以很快的找到合适的位置。
但是可能会导致IO激增，当然这种情况可能性也并不高，一页1M大小，每个数据块4K，每页有256个数据块，当连续冲突16次才可能引起IO。
如果M是合数，n^2 % M的取值必然少于M / 2的上取整种；
如果M是素数，n^2 % M的取值必然等于M / 2的上取整种，并且恰好由查找链的前M / 2项取遍。这也就意味着，只要装填因子不超过0.5，平方探测就一定可以找到空桶。
证明如上图所示，如果查找链前M / 2项不是彼此互异的，必然存在两项相互冲突。按照上面的推理（b + a）*（b - a）可以被M整除，然而M是素数，要想被M整除，a + b或者b – a中一定要包含M这个因子，然而，即使是最大的b + a，也必然是小于M的，因此不可能被M整除，所以可以证明查找链的前M / 2上取整项恰好取遍平方探测的所有取值。
双向平方试探：
观察上表知，当表长M = 4k+3时，双向平方试探前M项必互异，而M取4k+1时，则做不到。
费曼提出过双平方定理：即任一素数p可表示为一对整数的平方和，当且仅当p % 4 = 1.
并且观察上图的公式知平方和之积也可表示为一对整数的平方和。对于任意的整数X，由算术基本定理知X可分解为若干个素数之积，设yi表示除4模1的素数，zi表示除4模3的素数。X = (y1^p1 * y2^p2 * … * ym^pm) * (z1^q1 * … * zn^qn),由平方和之积也可表示为平方和知，(y1^p1 * y2^p2 * … * ym^pm)必然可以表示为一对整数的平方和，而对于zi而言，由于其本身无法表示为一对整数的平方和，当其幂次qi为偶数时(z1^q1 * … * zn^qn)也可表示为某数的平方。比如5 * 7^2 = （1^2 + 2^2）*7^2 = 7^2 + 14^2,故任一自然数n可以表示为一对整数的平方和，当且仅当其中模4为3的素因子均为偶次方。
不妨设在第a次正向平方探测和第b次负向平方探测时发生了冲突（1 <= a,b<=M/2），有a^2与 –b^2同余，即a^2 % M = -b^2 % M.有(a^2 + b^2) % M = 0，即a^2 + b^2可以被M整除，当M = 4k + 3时，由于M是某个平方和数的因子，其幂次必然是偶数，故(a^2 + b^2)可以被M^2整除，而(a^2 + b^2)必然小于M^2,矛盾，故前M次探测不可能发生冲突。
再散列：
桶/计数排序
在待排序序列的规模n远小于数的最大值m时，可以用哈希的办法来实现O（n + m）范围内的排序。
最大缝隙问题
采用直接排序的办法可以在O（nlogn）的范围内解决该问题。
也可以一遍扫描将各个元素放进散列表，自左向右遍历散列表实现线性的算法。
基数排序：
计数排序：
以对仅包含26个大写字母的序列为例，使用哈希表统计每个字母出现的次数count，然后再对count进行积分，即count的前缀和accum，比如C的accum表示序列中A、B、C一共出现了多少次，由accum可确定出排好序的序列中各个字母的分布范围，比如I应该在有序序列中下标从8到11的位置。