【常用算法】散列(hash)_C

散列（hash）定义
将元素通过一个函数（H（key））转换为整数，使得该整数可以尽量唯一的代表这个元素

散列最基本的对应关系就是对应其本身H（key）=key（很常用）

先看一个简单的问题
随机给一串数字（0-9），统计每个数字出现的次数。

如果采用传统的遍历，每个数字都要遍历一遍时间复杂度约为O（N*N）

如果采用散列，我们定义一个int数组a[10]={0},遍历该串数字，把遍历到的当前数字n作为数组下标，直接a[n]++，遍历完最后输出，就完成了，时间复杂度为O（N）
int a[10] = {0};  //散列表，记录数字出现的次数，初始化为0                  
int b[100] = {1,5,3,2,6,7,0,0,，7,9};   //要统计的数字串
for(int i = 0;i<10;i++)
{
    a[b[i]]++;   //把该数字（b[i]）作为数组下标，其相对应的值（a[b[i]]）++
}
for(int t = 0;t<10;t++)
{
    cout< 

 
 
 数组的局限性 
 如果要查询的数字超过10的5次方的话，就不能用数组来储存了，统计对象是字符串的话也不能直接用数组下标，所以有没有一种办法把这些特殊的情况转化为可以用数组来统计？有！ 
 散列函数 H（） 
 我们可以通过散列函数把超过界限的数字转化为数组可表示范围内的整数，也可以通过散列函数把一个字符或者字符串转化为整数（字符串hash）。 
 总结一下就是元素转换前为key，转化后就是H(key) 
 
 
 对于key是整数来说，常见的有那些散列函数？ 
 1.直接定址法（恒等变换/线性变换） 
 刚开始的统计数字的问题就是用了直接定址法，直接把key作为数组下标，直接定址法是指恒等变换，即H（key）=key，线性变换是指H(key)=a*key+b 
 2.平方取中法（很少用） 
 一般指取key的平方之间的若干位作为hash值。 
 3.除留余数法（比较实用） 
 指把key除以一个数mod得到的余数作为hash值，即 
 H(key)=key%mod 
 通过这个散列函数可以把很大的书转换为不超过mod的整数，这样就可以作为数组下标了（数组长度Tsize不能小于mod，一般取mod=Tsize） 
 
 
  想必大家肯定会有疑问，照上面的方法hash值肯定会有重复的呀，那么重复又该如何避免那？ 
 1.线性探查方法 
 方法如其名，如果当前的H(key)被占用了就+1，看下一个有没有被占用，反复如此，如果超出表长就回到表首继续，显然这个方法很容易扎堆，还会降低效率 
 2.平方探查法 
 如果当前的H(key)被占用了将按照固定顺序检查表的位置：H(key)+1*1、H(key)-1*1、H(key)+2*2、H(key)-2*2以此类推，如果超过了表长就对表长Tsize取模，如果出现了负数就一直＋表长Tsize，直到出现第一个非负数 
 3.链地址法（拉链法） 
 这个不用重新找新的hash值，而是直接把H(key)相同的key连接成一个单链表，就是数组存放的是单链表。这个好用 
 一般可以用STL库的map来直接使用hash的功能。 
 
 
 字符串hash 
 鸽了 
 
 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/3002541.html

【常用算法】散列(hash)

发表评论

评论列表（0条）