作者:我爱汇编 此贴贴于2010-1-30 10:06:35,已被阅读1037次/回复2 
其实我一直在想,二分与hash可不可以结合起来。进。。
我在这讨论都是关于字符串的查找,不涉及数值.

字符串的搜索,用二分时,很显然的在二分过程中,都要进行比较,一般都要比较至少2次,除非只有一个数组,hash的好处,是基本上只需要一次,但是需要占用大量空间,那可不可以结合两者特点,二分+hash呢?

我的想法是,使用hash函数,得到每一个字符串的hash值,然后存取这个值到数组中,这个数组每个元素占用8字节,前4字节为hash值,后4字节为一个地址,指向原来的真实字符串地址,依此下去将所有需要的字符串都添加,之后,占用(字符串个数+1*8)个字节的数组,然后,将此数组以前4字节数值大小进行排序,以后,在需要查找某个字符串时,得到字符串的hash值,再使用二分的方法查找这个值,因为仅在每次搜索前得到hash值时访问一次内存,之后只比较最多(组数集/2)到为0的个数,速度非常快。

我有实现过这个方法,感觉在速度与空间占用上都很折中,唯一的一点,就是大量随机字符串时,还是会存在不少冲突情况,并且如果字符串还要区分大小写时,每次要多比较真实字符串。如果能有一个完全不会重复的hash函数就好了...


以汇编编写单片机控制机器操纵世界!

此贴的父贴(直接):
昨天没写完,补上。写了俩钟头,效率别说hash了,二分也比不上,就一个顺序查找的水平,cacaca1101 hhh2000 2010-1-29 23:36:17 817 正常
此贴的回复贴(直接):
你这个算法的本质是加速处理冲突。803 zoologist 2010-1-30 10:50:57 0 正常
老兄,你看帖子不会只看标题吧。没有冲突的hash函数, 我帖子里有提到啊,也是很成熟的东西了,完美hash/最小完美hash/保序最小完美hash ->1122 hhh2000 2010-1-30 21:28:46 700 正常