欢迎来到天天文库
浏览记录
ID:24768892
大小:60.50 KB
页数:14页
时间:2018-11-15
《算法之个人总结:hash表之简单应用 》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、算法之个人总结:Hash表之简单应用[算法之个人总结:Hash表之简单应用]前段时间看了个微软编写的C库函数,在这个库函数里学到一个自我感觉相当牛比的小算法,说白了是Hash表的应用,算法之个人总结:Hash表之简单应用。大家都知道,Hash表最主要是用来实现查找功能的,再具体点是用常量级时间复杂度找到你想查找的东西。首先,我以一个小问题引入将要介绍的Hash算法,问题如下:现有字符串str1,str2,编写一个函数返回str1中有多少个字符在str2字符串中。其实这个函数也很简单(假如我们不考虑时间复杂度的话),遍历str1字符串,其中对于str1中的
2、每一个字符都要去判断是否在str2字符串中,如果在统计变量加1,即需要两个for循环,即时间复杂度为0(LenA*LenB),程序也很简单,如下://返回字符串str1中有多少个字符在str2字符串中intCharCount(constchar*str1,constchar*str2){intct=0;constchar*ptr;for(;*str1!=' ';++str1){//每次从str2的开头开始遍历for(ptr=str2;*ptr!=' ';++ptr){if(*str1==*ptr)//如果发现str1当前字符在str2字符串中{++c
3、t;break;}}}returnct;}这个程序每次判断str1中的字符是否在字符串str2中时,str2字符串均需要从开头遍历,即每次需要回溯,从而使得整个算法的时间复杂度很高,那么我们是否可以用常量级时间复杂度来执行上面程序的内循环?即我们是否可以用常量级时间复杂度来判断某字符是否在字符串str2中?答案是肯定的,此时就需要Hash表。首先我先叙述下关于素的数组,编号相同的8个字符存放在一个单元,在一个单元里如何来区分这8个字符呢?如果接着分析下去,易知,每一组中的8个字符除以8的余数均是0-7,因此,我们可以根据这8个字符除以8的余数来分别区分它
4、们,具体办法如下:用一个char类型数据,char类型数据的最低位来表示除以8余数是0的那个字符,倒数第二位表示除以8余数是1的字符,从而可以将每一组中的8个字符用一个char类型数据的每一位表示。例如:ASCII值是49的字符应该这样存放在Hash表中(含有32个元素的数组),首先49/8等于6即编号是6,其次49%8等于1,即这个单元的char数据的bit1位是1,即arr[6]中的char数据的二进制应该为00000010;有了上述算法的思想,那么我们就可以用chararr[32]来存放一个字符串str2了,依次遍历这个字符串,按照上述原则依次标记
5、数组中相应位置,字符串str2中每一个字符c的位置是arr[c/8],其次使得该char数据的第c%8bit置1,假如arr数组中每一个元素初始值均为0,那么可以这样实现://使得编号为c/8的单元中的char数据的第c%8bit置1arr[c/8]=arr[c/8]
6、(1(c%8));如果将str2中的每一个字符按照上述原则标记好了,假如我们要在str2中查找字符a,那么可以判断编号为a/8的单元中的char数据的第a%8bit是否为1,如果是说明字符a在str2中,即:if((arr[a/8](1(a%8)))!=0)//说明字符a存在的看看利用这种
7、方法是不是实现了常量时间复杂度查找某字符是否在字符串中?嘿嘿!重新回到开头的那个问题,判断str1中的字符是否在str2中,查找算法就可以用上述思路来实现,即只需要遍历str1字符串,之后用上述常量时间复杂度的查找算法判断str1当前字符是否在str2中,易知时间复杂度是O(LenA),算法如下:intCharCount_(constchar*str1,constchar*str2){charhash[32];//hash表的初始化for(inti=0;i32;++i)hash=0;//用hash保存str2中所有字符constchar*pstr2=st
8、r2;for(;*pstr2!=' ';++pstr2){hash[*pstr2/8]
9、=(1(*pstr2%8));}intct=0;//遍历str1字符串,判断每个字符是否在hash表中(是否在str2字符串中)for(;*str1!=' ';++str1){if(hash[*str1/8](1(*str1%8)))++ct;}returnct;}其实上述算法还可以加快,我们都知道计算机在处理除法以及取模运算时相对是较慢的,因此我们可以用位运算来实现上面的除法和取模运算,*str1/8等价于*str13,另外r2){hash[*pstr23]
10、=
11、(1(*pstr27));//优化之一}intct=0;//遍历str1字符串,
此文档下载收益归作者所有