哈希表

目录

一、定义

二、哈希函数的构造方法

1.数字分析法：

2.平方取中法：

3.分段叠加法：

 4.除留余数法：

二.哈希冲突：

1.开放定址法(再散列法)：

1) 线性探测再散列： 

2) 二次探测再散列：

3) 伪随机探测再散列：

4) 示例：     

2.再哈希法：

3.拉链法(HashMap的冲突处理方式):

4.建立公共溢出区：

三、考点

1 求散列表

2 求查找成功的平均查找长度

3 求查找不成功的平均查找长度

---

一、定义

     哈希表（hash table）是从一个集合A到另一个集合B的映射（mapping）

 

二、哈希函数的构造方法

1.数字分析法：

   如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。
    例如，有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为：00~99。
    假设经过分析，各关键字中 d4和d7的取值分布较均匀，则哈希函数为：h(key)=h(d1d2d3…d7d8)=d4d7。例如，h(81346532)=43，h(81301367)=06。
    相反，假设经过分析，各关键字中 d1和d8的取值分布极不均匀， d1 都等于5，d8 都等于2，此时，如果哈希函数为：h(key)=h(d1d2d3…d7d8)=d1d8，
    则所有关键字的地址码都是52，显然不可取。 

2.平方取中法：

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。
    这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

    例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，

            A的内部编码为01, B的内部编码为02。

   由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。

            之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如图8.23所示。

 
关键字    内部编码     内部编码的平方值          H(k)关键字的哈希地址
KEYA     11050201      122157778355001            778
KYAB     11250102      126564795010404            795
AKEY     01110525      001233265775625            265

BKEY     02110525      004454315775625            315

3.分段叠加法：

    这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
        具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。  
        例如：key=12360324711202065,哈希表长度为1000，则应把关键字分成4位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907 
    （a）移位叠加              (b) 折叠叠加
       1   2   3                    1   2   3
       6   0   3                    3   0   6
       2   4   7                    2   4   7
       1   1   2                    2   1   1
       0   2   0                    0   2   0
——————               ——————
  1   1   0   5                    9   0   7

 4.除留余数法：

     假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为 
h（k）=k  %  p ，其中%为模p取余运算。
例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有
h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
h(46)=46 % 7=4
此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
h(46)=46 % 13=7

二.哈希冲突：

  当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是
  不可避免的，只能通过改进哈希函数的性能来减少冲突。
 Hash冲突：开地址法（线性探测、二次探测）、再哈希法、链地址法、公共溢出区法等

1.开放定址法(再散列法)：

 基本思想：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
 这种方法有一个通用的再散列函数形式：
               Hi=（H（key）+di）% m   i=1，2，…，n
 其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。 

1) 线性探测再散列： 

  dii=1，2，3，…，m-1
  冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

2) 二次探测再散列：

  di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )
  冲突发生时，在表的左右进行跳跃式探测，比较灵活。

3) 伪随机探测再散列：

  di=伪随机数序列。
  具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。  

4) 示例：     

          已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

  a): 如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，

               继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。

    0     1     2     3     4     5     6     7     8     9     10
                        47   26   60   69

  b): 如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，

               将69填入2号单元。

     0     1     2     3     4     5     6     7     8     9     10
                  69   47   26  60      

  c): 如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址

               为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

     0     1     2     3     4     5     6     7     8     9     10
                         47   26  60                  69

2.再哈希法：

         这种方法是同时构造多个不同的哈希函数：
                   Hi=RH1（key）  i=1，2，…，k
         当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3.拉链法(HashMap的冲突处理方式):

          基本思想: 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要

                            在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

         例如:  已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，

                     则用链地址法处理冲突的结果如图8.27所示：

       位置    Entry 
        0
        1  -->  40 --> 27 --> 53
        2
        3  -->  16 --> 42
        4
        5
        6  -->  32 --> 71

        7
        8
        9
        10 -->  36 --> 49
        11 -->  24
        12 -->  64
        
                本例的平均查找长度 ASL=(1*7+2*4+3*1)/13=1.38

4.建立公共溢出区：

 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

三、考点

除留取余法寻找地址、解决冲突寻找地址、平均查找长度

例如：Hash表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度。 
　　查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数； 
查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。

下面举个例子： 
将关键字序列{7, 8, 30, 11, 18, 9, 14}散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，长度为10，即{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。散列函数为： H(key) = (key * 3) % 7，处理冲突采用线性探测再散列法。 
求等概率情况下查找成功和查找不成功的平均查找长度。

解：

1 求散列表

H(7) = (7 * 3) % 7 = 0 
H(8) = (8 * 3) % 7 = 3 
H(30) = 6 
H(11) = 5 
H(18) = 5 
H(9) = 6 
H(14) = 0

按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。

address	0	1	2	3	4	5	6	7	8	9
key	7	14		8		11	30	18	9

插入key = 18时，根据H(18) = 5应插在addresss=5的位置，但是address=5已经被key=11占据了，所以往后挪一位到address=6的位置，但是address=6被key=30占据了，再往后挪一位到address=7的位置，这个位置是空的，所以key=18就插到这个位置。 
插入key = 9时，根据H(9) = 6应插在address=6的位置，但address = 6已经被key = 30占据，所以需要往后挪一位到address = 7的位置，但是address = 7已经被key = 18占据，所以再往后挪移到address = 8的位置，这个位置是空的，所以key = 9就插到这个位置。 
插入key=14时，根据H(14) = 0应插在address=0的位置，但address=0被key=7占据，所以往后挪移一位到address=1的位置，这个位置是空的，所以key=14就插到这个位置。

2 求查找成功的平均查找长度

查找7，H(7) = 0，在0的位置，一下子就找到了7，查找长度为1。 
查找8，H(8) = 3，在3的位置，一下子就找到了8，查找长度为1。 
查找30，H(30) = 6，在6的位置，一下子就找到了30，查找长度为1。 
查找11，H(11) = 5，在5的位置，一下子就找到了11，查找长度为1。 
查找18，H(18) = 5，第一次在5的位置没有找到18，第二次往后挪移一位到6的位置，仍没有找到，第三次再往后挪移一位到7的位置，找到了，查找长度为3。 
查找9，H(9) = 6，第一次在6的位置没找到9，第二次往后挪移一位到7的位置，仍没有找到，第三次再往后挪移一位到8的位置，找到了，查找长度为3. 
查找14，H(14) = 0，第一次在0的位置没找到14，第二次往后挪移一位到1的位置，找到了，查找长度为2。

address	0	1	2	3	4	5	6	7	8	9
key	7	14		8		11	30	18	9
length	1	2		1		1	1	3	3

所以，查找成功的平均查找长度为(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7。

3 求查找不成功的平均查找长度

address	0	1	2	3	4	5	6	7	8	9
key	7	14		8		11	30	18	9

查找不成功，说明要查找的数字肯定不在上述的散列表中。 
因为这里哈希函数的模为7，所以要查找的数只可能位于0~6的位置上。 
（1）若要查找的数key对应的地址为0，有(key * 3) % 7 = 0。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 28。 
第一次查找，address = 0时key = 7，不是要找的28， 
第二次查找，往后挪移一位，address = 1时key = 14，不是要找的28； 
第三次查找，往后再挪移一位，address = 2时key为空。可知查找不成功，否则28应该放在adress = 2的位置上。 
结论：查找3次可知查找不成功。 
（2）若要查找的数key 对应的地址为1，有(key * 3) % 7 = 1。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 5。 
第一次address = 1时key = 14，不是要找的5 
第二次adress = 2时key为空。可知查找不成功，否则key = 5应该放在adress=1的位置上。 
结论：查找2次可知查找不成功。 
（3）若要查找的数key对应的地址为2，有(key * 3) % 7 = 2。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 3。 
第一次查找，address = 2时key为空。可知查找不成功，否则key = 3应该放在address = 2的位置。 
结论：查找1次可知查找不成功。 
（4）若要查找的数key对应的地址为3，有(key * 3) % 7 = 3。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 15。 
第一次查找，address = 3时key = 8，不是要找的15. 
第二次查找，往后挪移一位，address = 4时key为空。可知查找不成功，否则key = 15会放在address = 4的位置上。 
结论：查找2次可知查找不成功。 
（5）若要查找的数key对应的地址为4，有(key * 3) % 7 = 4。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 6。 
第一次查找，address = 4时key为空。可知查找不成功，否则key = 6会放在address = 4的位置上。 
结论：查找1次可知查找不成功。 
（6）若要查找的数key对应的地址为5，有(key * 3) % 7 = 5。 
因为key不属于{7, 8, 30, 11, 18, 9, 14}，可设key = 4。 
第一次查找，address = 5时key = 11，不是要找的4. 
第二次查找，往后挪移一位，address = 6时key=30，不是要找的4。 
第三次查找，往后再挪移一位，注意此时address = 0而非address = 7，因为模为7，决定了要查找的数只可能位于0~6的位置上。address = 0时key = 7，不是要找的4。 
第四次查找，往后再挪移一位，address = 1时key = 14，不是要找的4。 
第五次查找，往后再挪移一位，address = 2时key为空。可知查找不成功，否则key = 4会放在address = 2的位置上。 
结论：查找5次可知查找不成功。 
（7）若要查找的数key对应的地址为5，同理可得出结论：查找4次可知查找不成功。

综上，查找不成功的次数表如下所示

address	0	1	2	3	4	5	6
count	3	2	1	2	1	5	4

所以，查找不成功的平均查找长度为（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7