随笔 - 62  文章 - 96  trackbacks - 0
<2007年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 231224
  • 排名 - 106

最新评论

阅读排行榜

评论排行榜

字符串hash函数,解决冲突用开放定址法,每次对哈希值加1
在下列程序中,不是按常规方法用哈希表来记录关键字,
而是用整型数组Htable记录关键字在字符串ch中的位置。
在插入时不用把关键字复制到哈希表中,只是记录一个索引,从而提高了效率。
当查询时,只要把Htable的值映射到字符串ch中就可以了。
注意ch的下标要从1开始,因为Htable中的零值认为是空,处理起来比较方便。
#include<iostream>
#include
<string>
using 
namespace std;
const int MAXN = 9973//哈希表长度
const int len = 30//字符串的最大长度
int Htable[MAX];
char ch[MAX][len]; //存储关键字的字符串
unsigned 
long Hash(char * key)
{
    unsigned 
long h = 0;
    
while(*key)
    {
        h 
= (h << 4+ *key++;
        unsigned 
long g = h & 0xf0000000L;
        
if(g)
            h 
^= g >> 24;
        h 
&= ~g;
    }
    
return h % MAX;
}
int search(char * key)
{
    unsigned 
long i = Hash(key);
    
while(Htable[i])
    {
        
if(strcmp(ch[Htable[i]], key) == 0)
            
return i;
        i 
= (i + 1) % MAX;
    }
    
return -1;
}
int insert(char * key, int j) //j为关键字在ch中的位置,即索引
{
    unsigned 
long i = Hash(key);
    
while(Htable[i])
        i 
= (i + 1) % MAX;
    Htable[i] 
= j;
    
return i;
}
posted on 2007-04-07 16:22 beyonlin 阅读(5405) 评论(3)  编辑 收藏 引用 所属分类: acm之路C++之路

FeedBack:
# re: 字符串hash函数 2007-07-04 00:45 原来如此
请教:在insert函数中,key的值没有存到ch组里面去吧?

int insert(char * key, int j) //j为关键字在ch中的位置,即索引
{
unsigned long i = Hash(key);
while(Htable[i])
i = (i + 1) % MAX;
Htable[i] = j;
return i;
}  回复  更多评论
  
# re: 字符串hash函数 2007-07-09 21:34 beyonlin
@原来如此
我是把key的值在函数外存入ch中,
看你的留言后觉得还是在insert函数里面把key存到ch组比较严谨一点。
谢谢!  回复  更多评论
  
# re: 字符串hash函数 2009-04-01 13:31 nuoshueihe
怎么没有写完啊?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理