数据结构与算法 9. 词典 2021-07-27 浏览量 874 暂无评论 [TOC] ## 9.1 散列:原理 一种重要的组织数据并实现算法的思想 循值访问 关键码取值范围大,但利用率低,通过散列对关键码空间进行压缩,保证查找速度的同时,降低存储消耗。 ### 术语 - 桶(bucket):直接存放或间接指向一个词条 - 桶数组/散列表,容量为M,$N \lt M \ll R$,空间$O(N+M)$,装填因子:$\lambda = N / M$ 根据词条的key直接确定散列表的入口,散列函数:`hash(): key -> &entry` ![在这里插入图片描述](https://img-blog.csdnimg.cn/40344c91dd104dd9a06e69df367dcad7.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 冲突 经过散列函数后,不同的关键码对应同一个桶单元 好的散列函数可以降低冲突的概率 ## 9.2 散列:散列函数 冲突是难免的 ![在这里插入图片描述](https://img-blog.csdnimg.cn/29209ca4f21447da83dc24d9b64a338b.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 除余法 与2^k除余,效果相当于截取该数的最后k位,前面的n - k位没有影响,故 `key % M = key & (M - 1)` 此种情况下,如果最后k位相同,就会发生冲突 **如果取M为素数,那么冲突概率减少,分布更加均匀**,why? 又是数论哈哈,蝉的生命周期 ### MAD法 除余法的改进。 **除余法的缺陷**: 1. 不动点:hash(0) = 0 2. 零阶均匀:相邻关键码的散列地址也必相邻,相邻会怎样?视场合 `multiply-add-divide` 取M为素数 ,a > 0, b > 0, a % M ≠ 0,`hash(key) = ((a × key) + b) % M` ### 平方取中 取$key^2$的中间若干位,构成地址,如`hash(123) = 512, `// $key^2 = 123^2 = 15129$ **疑问** 1. 为什么保留居中的数位?越是中间的数位更多的原数位累计得到的,使最终的散列地址尽可能接近 2. 关键码很大时,平方的计算开销不影响吗?甚至上溢 ### 折叠汇总 ![在这里插入图片描述](https://img-blog.csdnimg.cn/fcba421d777c4e41a22335b43db3a676.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 伪随机数 ![在这里插入图片描述](https://img-blog.csdnimg.cn/ace5f9882c92431b884d86415bc146e9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 多项式 key -> hashcode ![在这里插入图片描述](https://img-blog.csdnimg.cn/e134e9f78193411291f7604d2b66a969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 如果只是简单相加的话,很容易出现冲突 ## 9.3 排解冲突1 ### 多槽位 ![在这里插入图片描述](https://img-blog.csdnimg.cn/e0c4a411c0db47deb2cba049e2d38e7a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 独立链 改用列表,动态增长 ![在这里插入图片描述](https://img-blog.csdnimg.cn/4eb45d337c4744b89c15dc542b2fadb0.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 开放定址 独立链式封闭定址(closed addresing),让所有的散列和冲突排解都在一个封闭的空间进行。 每一个词条都有可能被防在任何一个桶中,而不是像之前那样每个词条的位置都是固定的。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/e206fce587d146518ccbc03eeda48f03.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 线性试探:策略 ![在这里插入图片描述](https://img-blog.csdnimg.cn/a706c99423f74e1c8c82e95bedd94ed2.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/54102b3b8fe3445cafd57ff3fd8742a9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 懒惰删除 按照开放定址策略,先后插入、相互冲突的一组词条,将存放在同一查找链中,若直接删除其中某个词条,查找链会被切断,后续词条丢失--明明存在,却访问不到 懒惰删除的做法就是仅做删除标记,查找链不必续接。 每一个桶单元,都同时属于多个查找链。 ## 9.4 排解冲突2 ### 平方试探 线性试探比较靠近 ![在这里插入图片描述](https://img-blog.csdnimg.cn/05e7d90027944e21b701b5e1248db167.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/34e06214f1fd488c97945eccf311ca71.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **定理**:若M是素数,且装填因子小于等于0.5,那么前$\lceil M/2 \rceil$位置一定彼此互异。 ### 双向平方试探 ![在这里插入图片描述](https://img-blog.csdnimg.cn/1a22da33ae3c4701bfed2339d3cdd1cc.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 要选合适的素数,不合适的素数会出现前向和逆向都由相同的元素组成的情况。 **4k + 3的素数必然可以保证查找链的前M项互异。** 证明:双平方定理-- ## 9.5 桶/计数排序 复杂度不完全取决于输入的规模,还取决于待排序序列的取值范围,$O(max(n + M))$ 通过每个字母的统计值和累计值,确定其在有序向量中的区间。 赞赏 微信支付 支付宝支付