散列学习笔记（一）

浅浅的花香味﹌ 2022-05-26 12:37 140阅读 0赞

## 一. 散列 ##

*  ## 即哈希，就是把任意长度的输入，通过散列函数，变换成固定长度的输出，该输出就是散列值。 ##
 *  **以关键字key为自变量，通过一个确定的函数h（散列函数**
    
    ## ），计算出对应的函数值h，作为数据对象的存储地址 ##
 *  **可能不同的关键字会映射到同一个散列地址上，即h(key1)=h(key2)，称为“冲突（Collision）”**

![70][]

**1. 装填因子（Loading Factor）：设散列表空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的装填因子**

**2. M为素数时，数据对散列表的覆盖最充分，分布最均匀。**

## 二. MAD法 ##

### 1. 除余法的缺陷 ###

### 1)不动点：无论表长M取值如何，总有hash(0)=0 ###

### 2) 零阶均匀：\[0，R)的关键码，平均分配至M个桶；但相邻关键码的散列地址也必相邻。 ###

### 2. MAD=multiply-add-divide ###

**取M为素数，a>0 , b>0 , a % M != 0**

**hash(key) = ((a\*key)+b)%M, b为偏移量用于消除不动点，a为步长，经过散列变换后，原本相邻的关键码，将变成间隔a，从而不再相邻。**

###  ###

### 3.特定场合下，未必需要高阶的均匀性。 ###

## 三. 其他散列函数 ##

### 1. 数字分析 selecting digits ###

**抽取key中的某几位，构成地址。比如，取十进制表示的奇数位。**

![70 1][]

### 2. 平方取中mid-square ###

**取key的平方的中间的若干位，构成地址**

**![70 2][]**

**Question：为什么取居中的数作为地址？**

**为了使得构成原关键码的各数位能够对最终的散列地址有尽可能接近的影响。**

**![70 3][]**

**CPU中的运算器最终会将乘法分解成一系列的左移操作，以及若干次加法。如图可知，如果忽略进位，每一个数位都是由原关键码中的若干数位经求和得到的。因此两侧的数位是由更少的原数位累积而得。而越是居中的数位，则是由更多的原数位累积而得。**

**-------------------------------------------------------------------------------------------------------------------**

**（有兴趣了解CPU怎样计算乘除法的盆友建议观看北大陆俊林教授的《计算机组成》中的第五章：乘法器和除法器**

**[http://www.chinesemooc.org/kvideo.php?do=course\_cware\_list&kvideoid=4392&classesid=1967][http_www.chinesemooc.org_kvideo.php_do_course_cware_list_kvideoid_4392_classesid_1967]）**

**-------------------------------------------------------------------------------------------------------------------**

### **3. 折叠法** ###

![70 4][]

### 4. 多项式法 ###

**适用的关键码类型为字符串。**

[70]: /images/20220526/eb845f2fd65f407ca9b792756e65718f.png
[70 1]: /images/20220526/849e5d3620ca4477962e683edd413569.png
[70 2]: /images/20220526/b2fcbae429ac4cdd84e9939c20620ac8.png
[70 3]: /images/20220526/ddb124ab03954bd08eba9ad29100bd1f.png
[http_www.chinesemooc.org_kvideo.php_do_course_cware_list_kvideoid_4392_classesid_1967]: http://www.chinesemooc.org/kvideo.php?do=course_cware_list&kvideoid=4392&classesid=1967
[70 4]: /images/20220526/ed6ffcca96804e28934f3b431a95dee3.png