<hr> <div id="div1"><h3> <font color=red > 哈希函数，哈希表 </font><h3></div> ==建立哈希表==操作步骤 - 1，取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 - 2， 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止 <hr> ### 哈希函数 原则尽可能将关键字集合空间均匀的映射到地址集合空间中，同时尽可能降低冲突发生的概率。 - 1， **除留余数法**：H(Key) = key % p (p ≤ m) 取关键字除以p的余数作为哈希地址，p最好选择一个 <= m（哈希地址集合的个数）的某个最大素数 - 2、**直接地址法**: H(Key) = a * Key + b； 这个“a，b”是常量。 - 3、**数字分析法**: 比如有一组key1=112233，key2=112633，key3=119033， 针对这样的数我们分析数中间两个数比较波动，其他数不变。那么key设为： key1=22,key2=26,key3=90。 - 4、**折叠法**： 比如key=135790，要求key是2位数的散列值。那么我们将key变为13+57+90=160，然后去掉高位“1”, 此时key=60， <hr> ### 冲突处理方法 ①.线性探测法 依次探测下一个地址，直到有空的地址后插入，若整个空间都找遍仍然找不到空余的地址，产生溢出。 Hi =(H(Key) + di) % m ， (i = 1, 2, 3, ..., k, k ≤ m-1 )， 地址增量 di = 1,2,...,m-1 , 其中 i 为探测次数  Hash（key） = key % 10（表长）； 89放入9的位置；18放入8的位置；49与89冲突，往后加到尾了就再回到头，0的位置为空放入；58与18冲突，往后加有89，再加有49，再加就放入1的位置；9与89冲突一直加到2的位置放入。 ②.二次探测法， 地址后偏移量为（1,2,3...）的二次方地址处 ```javascript 地址增量序列为：di = 1^2 ， -1^2， 2^2 ， -2^2 ，...，q^2，-q^2， （q ≤ m/2） ``` Python字典dict的实现是使用开放寻址法中的二次探查来解决冲突的。  ```javascript Hash（key） = key % 10（表长）； 89放入9的位置；18放入8的位置；49与89冲突，加1^2，到0的位置；58与18冲突，加1^2,到了9的位置，有数继续加2^2到2的位置；9与89冲突，加1^2，在0的位置，继续加2^2，到3的位置放入。 Hash（key）+ i^2 （i= 1、2、3……不算第一放入的数 ``` ③.双哈希函数探测法 Hi =(H(Key) + i * RH(Key)) % m ( i = 1,2,3,..., m-1 )， H(Key) , RH(Key) 是两个哈希函数，m为哈希表长度。 先用第一个哈希函数对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数确定移动的步长因子，最后通过步长因子序列由探测函数寻找空余的哈希地址。 H1 = (a+b) % m， H2 = ( a + 2b )%m , ... , Hm-1 = ( a+(m-1)*b )%m (2) 链地址法 将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法