哈希表大总结
哈希表总结
目录
哈希表
记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
因而查找时，只需根据这个对应关系f找到给定值K的像f(K）。
若结构中存在关键字和K相等的记录，则必定在f(K）的存储位置上，由此不需要进行比较便可直接取得所查记录。
在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表。
哈希表不可避免冲突（collision）现象：
- 对不同的关键字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2）。
- 具有相同函数值的关键字对该哈希函数来说称为同义词（synonym）。
- 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。
- 可如下描述哈希表：根据设定的哈希函数H(key）和所选中的处理冲突的方法，
- 将一组关键字映象到一个有限的、地址连续的地址集（区间）上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。
散列表查找步骤
散列表(也叫哈希表,Hash table) ,是根据关键码的值进行访问的数据结构.散列表的实现常常叫做散列（hasing）,散列是一种用于以常数平均时间执行插入,删除和查找的技术
整个散列过程分为两步
-
通过散列函数计算记录的散列地址,并按照散列地址储存该记录
无论什么记录我们都需要用同一个散列函数计算地址，然后再存储。
-
查找通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录.因为我们存和取的时候用的都是一个散列函数，因此结果肯定相同。
散列函数是什么呢？
- 假设某个函数为 f，使得 存储位置 = f (key) 那样我们就能通过查找关键字不需要比较就可获得需要的记录的存储位置。这种存储技术被称为散列技术。散列技术是在通过记录的存储位置和它的关键字之间建立一个确定的对应关系 f ,使得每个关键字 key 都对应一个存储位置 f(key)
这里的f就是我们所描述的哈希函数(散列函数),我们利用散列技术将记录储存在一块连续的储存空间中,这块连续的储存空间就是----(哈希)散列
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。对于这种情况我们能找到有效的方法解决
哈希函数的特殊性:
创建哈希函数是必须遵循一下原则:
-
必须一致性
无论什么记录我们都需要用同一个散列函数计算地址
-
计算简单
在保证不哈希冲突的情况下,使得计算简单,如果这个算法计算复杂，会耗费很多时间.散列函数的计算时间不应该超过其他查找技术与关键字的比较时间，不然的话我们干嘛使用哈希技术了
-
散列地址分布均匀
让散列地址尽量均匀分布在储存空间中,这样既保证了空间的有效性,有减少了处理冲突而消耗的时间
散列函数构造方法
直接定址法:
- 取关键字或关键字的某个线性函数值为散列地址。
- 即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。
- 若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
优点:
- 简单,均匀,无冲突
应用场景：
- 需要事先知道关键字的分布情况，适合查找表较小且连续的情况
数字分析法
- 该方法也是十分简单的方法，就是分析我们的关键字，取其中一段，或对其位移，叠加，用作地址
- 比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
- 因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
优点：
- 简单、均匀、适用于关键字位数较大的情况
应用场景：
- 关键字位数较大，知道关键字分布情况且关键字的若干位较均匀
折叠法
- 将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 比如我们的关键字是123456789，则我们分为三部分 123 ，456 ，789 然后将其相加得 1368 然后我们再取其后三位 368 作为我们的散列地址。
优点：
- 事先不需要知道关键字情况
应用场景：
- 适合关键字位数较多的情况
除法散列法
- 在用来设计散列函数的除法散列法中,通过取key除p的余数,将关键字映射到某一个上,对于散列表长度为 m 的散列函数公式为
- f(k) = k mod p (p <= m)
如
如果散列表长度为 12，即 m = 12 ，我们的参数 p 也设为12，那 k = 100时 f(k) = 100 % 12 = 4
我们只需要做一次除法操作,所以除法散列法非常快
由上面的公式可以看出，该方法的重点在于 p 的取值，如果 p 值选的不好，就可能会容易产生同义词(哈希冲突)。见下面这种情况。我们哈希表长度为6，我们选择6为p值，则有可能产生这种情况，所有关键字都得到了0这个地址数。
那我们在选用除法散列法时选取 p 值时应该遵循怎样的规则呢？
- m 不应为 2 的幂，因为如果 m = 2^p ，则 f(k) 就是 k 的 p 个最低位数字。例 12 % 8 = 4 ，12的二进制表示位1100，后三位为100。
- 若散列表的长度为m,通常p为小于或者等于表长(接近)的最小质数或者包含不小于20质因子的合数
合数：合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
质因子：质因子（或质因数）在数论里是指能整除给定正整数的质数。
注：这里的2，3，5为质因子
根据规则选择 5 为 p 值，我们再来看。这时我们发现只有 6 和 36 冲突，相对来说就好了很多。
优点:
- 计算效率高,灵活
应用场景:
- 不知道关键字分布情况
乘法散列法
构造散列函数的乘法散列法主要包含两个步骤
- 用关键字 k 乘上常数 A(0 < A < 1)，并提取 k A 的小数部分
- 用 m 乘以这个值，再向下取整
散列函数为:
f (k) = ⌊ m(kA mod 1) ⌋
这里的 kA mod 1 的含义是取 keyA 的小数部分，即 kA - ⌊kA⌋ 。
优点：对 m 的选择不是特别关键一般选择它为 2 的某个幂次（m = 2 ^ p ,p为某个整数）
应用场景：不知道关键字情况
平方取中法
- 这个方法就比较简单了，假设关键字是 321，那么他的平方就是 103041，再抽取中间的 3 位就是 030 或 304 用作散列地址。
- 再比如关键字是 1234 那么它的平方就是 1522756 ，抽取中间 3 位就是 227 用作散列地址.
优点：
灵活，适用范围广泛
适用场景：
不知道关键字分布，而位数又不是很大的情况
随机数法
选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。
处理散列冲突的方法
hash 函数之后发现关键字 key1 不等于 key2 ，但是 f(key1) = f(key2)，即有冲突，
开放地址法
一旦发生冲突,就会寻找下一个空的散列地址,只要列表足够大,空的散列地址总能找到,并将记录存入,为了使用开放寻址法插入一个元素,需要连续检查散列表,称为探查,我们常用的有线性探测，二次探测，随机探测。
线性探测法
我们来看一个例子，我们的关键字集合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为12，我们再用散列函数 f(key) = key mod 12。
我们求出每个 key 的 f(key)见下表
我们查看上表发现，前五位的 f(key) 都不相同，即没有冲突，可以直接存入，但是到了第六位 f(37) = f(25) = 1,那我们就需要利用上面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2，这其实就是我们的订包间的做法。下面我们看一下将上面的所有数存入哈希表是什么情况吧。
注：蓝色为计算哈希值，红色为存入哈希表
他第一次会落在下标为 10 的位置，那么如果继续使用线性探测的话，则需要通过不断取余后得到结果，数据量小还好，要是很大的话那也太慢了吧，但是明明他的前面就有一个空房间呀，如果向前移动只需移动一次即可。
二次探测法
其实理解了我们的上个例子之后，这个一下就能整明白了，根本不用费脑子，这个方法就是更改了一下di的取值
注：这里的是 -1^2 为负值 而不是 （-1)^2
所以对于我们的34来说，当di = -1时，就可以找到空位置了。
二次探测法的目的就是为了不让关键字聚集在某一块区域。另外还有一种有趣的方法，位移量采用随机函数计算得到，接着往下看吧.
随机探测法
大家看到这是不又有新问题了，刚才我们在散列函数构造规则的第一条中说
（1）必须是一致的
我们 di 是随机生成的呀，这里的随机其实是伪随机数，伪随机数含义为，我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在查找时，用同样的随机种子，它每次得到的数列是相同的，那么相同的 di 就能得到相同的散列地址。
随机种子（Random Seed）是计算机专业术语，一种以随机数作为对象的以真随机数（种子）为初始条件的随机数。一般计算机的随机数都是伪随机数，以一个真随机数（种子）作为初始条件，然后用一定的算法不停迭代产生随机数
再哈希法
这个方法其实也特别简单，利用不同的哈希函数再求得一个哈希地址，直到不出现冲突为止。
f,(key) = RH,( key ) (i = 1,2,3,4……k)
这里的RH就是不同的散列函数,可以把我们之前说的那些散列函数都用上,每当发生哈希冲突时就换一个散列函数，相信总有一个能够解决冲突的。这样的代价就是增加了计算时间
链地址法
- key 不同 f(key) 相同的情况,我们将这些同义词储存在一个单链表,这种表叫做同义词子表.散列表中只储存同义词表的头指针…
- 关键字集合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为12，
- 我们再用散列函数 f(key) = key mod 12
- 用了链地址法之后就在也不冲突,无论有多少冲突，我们只需在同义词子表中添加结点即可。下面我们看下链地址法的存储情况。
链地址法虽然不能够产生冲突,但是查找时需要遍历单链表的性能.
公共溢出区法
将有冲突的,放入到别的地方(溢出表),这样你就有地方住了。我们为所有冲突的关键字建立了一个公共的溢出区来存放。
怎样查找: 通过散列函数计算出散列地址后,先于基本表对比,如果不相等就到溢出表中顺序查找.,对于冲突很少的情况性能还是非常高的
散列表查找算法(线性探测法)
首先需要定义散列列表的结构以及一些相关常数，
- elem代表散列表数据存储数组
- count代表的是当前插入元素个数
- size代表哈希表容量
- NULLKEY散列表初始值
- 然后我们如果查找成功就返回索引，如果不存在该元素就返回元素不存在。
- 我们将哈希表初始化，为数组元素赋初值。
插入操作的具体步骤
- 通过哈希函数(除法散列法),将key转化为数组下标
- 如果该下标中没有元素,则插入,否则说明冲突,则利用线性探测法处理冲突
查找
- 通过哈希函数(同输入时一样),将key转化成为数组下标
- 通过数组下标找到key值,如果key一致,则查找成功,否则利用线性探测法继续查找
blog.csdnimg.cn/img_convert/1684f4dd64d5c14d42e6cc624f68c6d2.png)
完整代码
散列表性能分析
如果没有冲突的话,散列表查找是效率最高的,时间复杂度为O(1),
散列查找的平均查找长度取决于哪些方面呢
-
散列函数是否均匀
-
处理冲突的方法
比如我们线性探测有时会堆积，则不如二次探测法好，因为链地址法处理冲突时不会产生任何堆积，因而具有最佳的平均查找性能
-
散列表的填装因子
装填因子 α = 填入表中的记录数 / 散列表长度
实际应用
什么是文件的hash值呢?
MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。
总结:
- 一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K）。若结构中存在关键字和K相等的记录，则必定在f(K）的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
- 哈希表不可避免冲突（collision）现象：对不同的关键字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2）。具有相同函数值的关键字对该哈希函数来说称为同义词（synonym）。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key）和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集（区间）上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。
- 对于动态查找表而言，1) 表长不确定；2）在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key）作为关键字为key的录在表中的位置，通常称这个函数f(key）为哈希函数。（注意：这个函数并不一定是数学函数）
- 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。
- 现实中哈希函数是需要构造的，并且构造的好才能使用的好。
- 用途：加密，解决冲突问题。