每周学习日志（六）

计算式查找法——哈希法（散列法） 首先在元素关键字K和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为哈希函数。 创建哈希表时，把关键字为K的元素直接存入地址为f（k）的单元。

当关键字集合很大时，不同元素可能占同一地址，既K1不等于K2，但H（k1）=H（k2）这种现象成为冲突。

除留余数法 设哈希表长为m，p为小于等于m的最大素数，则哈希函数为H(k)=k%p。

处理冲突的方法 开放定址法（再散列法） 1、线性探测再散列 2、二次探测再散列 3、伪随机探测在散列 再哈希法 链地址发 建立公共溢出区

Hi=（H（key）+di）%m i=1.2.3....n

1、线性探测再散列 di=1、2、3......n

2、二次探测再散列 di=1^2、-12、2^2、-22.。。k^2、-k2.（k<=m/2）

3、伪随机探测再散列 di=伪随机数序列。

哈希表查找过程 1、采用散列函数：取第一个冲突字母在字母表中位置再除以2. 2、采用线性探查法处理 3、按上述思路找关键字key

平均查找长度ASL 各元素被查找的次数/元素个数 成功平均查找长度为：ASL=1/表中元素个数n N总数i=1 Ci 不成功平均查找长度为：ASL=1/哈希函数取值个数r R总数i=1 Ci

每周学习日志（六）

原文：https://www.cnblogs.com/wananouo/p/13032383.html