哈希函数的哈希表的概念及作用

1. 哈希函数的哈希表的概念及作用

哈希表：根据关键码值而直接进行访问的数据结构

2. 哈希表的基本概念

散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：





散列表的主要特点：
     1.将输入映射到数字
     2. 不同的输入产生不同的输出
3. 相同的输入产生相同的输出

4. 当填装因子超过阈值时，能自动扩展。填装因子 = 散列表包含的元素数 / 位置总数，当填装因子 =1，即散列表满的时候，就需要调整散列表的长度，自动扩展的方式是：申请一块旧存储容量 X 扩容系数的新内存地址，然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置，拷贝到新申请的地址。

5. 值呈均匀分布。这里的均匀指水平方向的，即数组维度的。如果多个值被映射到同一个位置，就产生了冲突，需要用链表来存储多个冲突的键值。极端情况是极限冲突，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n)，如果水平方向填充因子很小，但某些节点下的链表又很长，那值的均匀性就比较差。

3. 哈希函数的哈希表的概念及作用

哈希表：根据关键码值而直接进行访问的数据结构

4. 哈希表算法的哈希表的概念及作用

一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。哈希表最常见的例子是以学生学号为关键字的成绩表，1号学生的记录位置在第一条，10号学生的记录位置在第10条...如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？用上述得到的数值作为对应记录在表中的位置，得到下表：上面这张表即哈希表。如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：李秋梅:lqm 12+17+13=42 取表中第42条记录即可。问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。

5. 查找算法的哈希表查找

1 基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素分类，然后将这个元素存储在相应类所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了冲突，换句话说，就是把不同的元素分在了相同的类之中。后面我们将看到一种解决冲突的简便做法。总的来说，直接定址与解决冲突是哈希表的两大特点。2 函数构造构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：a) 除余法：选择一个适当的正整数 p ，令 h(k ) = k mod p　　这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。b) 数字选择法：如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。3冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。4 支持运算哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。　　设插入的元素的关键字为 x ，A 为存储的数组。　　初始化比较容易，例如　　const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素　　p=9997; // 表的大小　　procedure makenull;　　var i:integer;　　begin　　for i:=0 to p-1 do　　A:=empty;　　End;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：　　function h(x:longint):Integer;　　begin　　h:= x mod p;　　end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate　　function locate(x:longint):integer;　　var orig,i:integer;　　begin　　orig:=h(x);　　i:=0;　　while (ix)and(A[(orig+i)mod S]empty) do　　inc(i);　　//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元　　//素存储的单元，要么表已经满了　　locate:=(orig+i) mod S;　　end;　　插入元素　　procedure insert(x:longint);　　var posi:integer;　　begin　　posi:=locate(x); //定位函数的返回值　　if A[posi]=empty then A[posi]:=x　　else error; //error 即为发生了错误，当然这是可以避免的　　end;查找元素是否已经在表中　　procedure member(x:longint):boolean;　　var posi:integer;　　begin　　posi:=locate(x);　　if A[posi]=x then member:=true　　else member:=false;　　end;

6. 哈希查找的定义

哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表；⑵根据选择的冲突处理方法解决地址冲突；⑶在哈希表的基础上执行哈希查找。

7. 哈希表的基本概念

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。  对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为碰撞（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。  若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少碰撞。

8. 哈希表详解

 哈希表：即散列存储结构。   散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。   这样，不经过比较，一次存取就能得到所查元素的查找方法   优点：查找速度极快（O(1)）,查找效率与元素个数n无关！
   哈希方法(杂凑法)   选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。
   哈希函数(杂凑函数)   哈希方法中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储地址之间建立的一种对应关系
   有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k ，   H(k)称为散列函数,画出存储结构图。
                                           根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，
   根据存储时用到的散列函数H(k)表达式，迅即可查到结果！   例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；   若查不到，应当设法返回一个特殊值，例如空指针或空记录。   很显然这种搜索方式空间效率过低。
   哈希函数可写成：addr(ai)=H(ki)
   选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储地址之间建立的一种对应关系。
   通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。
   有6个元素的关键码分别为：（14，23，39，9，25，11）。   选取关键码与元素位置间的函数为H(k)=k  mod  7
                                           根据哈希函数算出来发现同一个地址放了多个关键码，也就是冲突了。   在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。   所以，哈希方法必须解决以下两个问题：
   1）构造好的哈希函数   （a）所选函数尽可能简单，以便提高转换速度；   （b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。
   2）制定一个好的解决冲突的方案   查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。
   从上面两个例子可以得出如下结论：   哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可   冲突：key1≠key2，但H(key1)=H(key2)   同义词：具有相同函数值的两个关键码   哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：   构造好的哈希函数；
   制定解决冲突基本要求：   要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。   要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
   Hash(key) = a·key + b    (a、b为常数)   优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.   缺点：要占用连续地址空间，空间效率低。
   例.关键码集合为{100，300，500，700，800，900}，   选取哈希函数为Hash(key)=key/100，   则存储结构（哈希表）如下：
                                           Hash(key)=key  mod  p    (p是一个整数)   特点：以关键码除以p的余数作为哈希地址。   关键：如何选取合适的p？p选的不好，容易产生同义词   技巧：若设计的哈希表长为m，则一般取p≤m且为质数   （也可以是合数，但不能包含小于20的质因子）。
   Hash(key)= ⎣ B ( A key  mod  1 ) ⎦   (A、B均为常数，且0<A<1，B为整数)   特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。   例：欲以学号最后两位作为地址，则哈希函数应为：   H(k)=100 (0.01 k % 1 )   其实也可以用法2实现： H(k)=k % 100
   特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。   例：有一组（例如80个）关键码，其样式如下：
                                           讨论：   ① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。
   ② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。
   特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。(适于不知道全部关键码情况)   理由：因为中间几位与数据的每一位都相关。   例：2589的平方值为6702921，可以取中间的029为地址。
   特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。   适用于：关键码位数很多,且每一位上各符号出现概率大致相同的情况。   法1：移位法 ── 将各部分的最后一位对齐相加。   法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。   例：元素42751896,   用法1： 427＋518＋96=1041   用法2： 427 518 96—> 724+518+69 =1311
   7、随机数法   Hash(key) = random ( key )  (random为伪随机函数)   适用于：关键字长度不等的情况。造表和查找都很方便。
   小结：构造哈希函数的原则：   ① 执行速度（即计算哈希函数所需时间）；   ② 关键字的长度；   ③ 哈希表的大小；   ④ 关键字的分布情况；   ⑤ 查找频率。
   设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。   1）线性探测法   Hi=(Hash(key)+di) mod m       ( 1≤i < m )   其中：   Hash(key)为哈希函数   m为哈希表长度   di 为增量序列 1，2，…m-1，且di=i
   关键码集为 {47，7，29，11，16，92，22，8，3}，   设：哈希表表长为m=11；   哈希函数为Hash(key)=key mod 11；   拟用线性探测法处理冲突。建哈希表如下：
                                           解释：   ① 47、7是由哈希函数得到的没有冲突的哈希地址；   ② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。   ③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。   其中3 还连续移动了（二次聚集）
   线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；   线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，   因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。   解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。
   2） 二次探测法   仍举上例，改用二次探测法处理冲突，建表如下：   Hi=(Hash(key)±di) mod m   其中：Hash(key)为哈希函数   m为哈希表长度，m要求是某个4k+3的质数；   di为增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2
                                           注：只有3这个关键码的冲突处理与上例不同，   Hash(3)=3，哈希地址上冲突，由   H1=(Hash(3)+1 ^2) mod 11=4，仍然冲突；   H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希地址，存入。
   3） 若di＝伪随机序列，就称为伪随机探测法
   基本思想：将具有相同哈希地址的记录(所有关键码为同义词)链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
   设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：   Hash(key)=key mod 11，   用拉链法处理冲突，则建表如图所示。
                                           Hi=RHi(key)       i=1, 2,  …，k   RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。   优点：不易产生聚集；   缺点：增加了计算时间。
   思路：除设立哈希基本表外，另设立一个溢出向量表。   所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。
   明确：散列函数没有“万能”通式（杂凑法），要根据元素集合的特性而分别构造。   讨论：哈希查找的速度是否为真正的O（1）？   不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。   一般地，ASL依赖于哈希表的装填因子α,它标志着哈希表的装满程度。
                                           0≤α≤1   α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。
   例    已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)   哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，   设每个记录的查找概率相等   (1)  用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m
                                           (2)  用二次探测再散列处理冲突，即Hi=(H(key)+di) MOD m
                                           (3)  用链地址法处理冲突   
                                           
   1） 散列存储的查找效率到底是多少？   答：ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)   2）“冲突”是不是特别讨厌？   答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。   利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。