字符串hash函数 - skyli

友情链接

最新评论

1. re: 优先队列用法
评论内容较长,点击标题查看
--tanti
2. re: 优先队列用法
给力！！
--***
3. re: pow函数的性能测试
Pow 函数要处理各种非整数次幂情况，比如0.5就等于开根号了，0.2就等于开5次方了。当然比直接乘慢的多。
--YYX
4. re: istringstream用法[未登录]
@gong
cin是标准输入，在std中已经声明了。
--mm
5. re: istringstream用法[未登录]
您好，为什么这里的getline(cin, line）中的cin没有定义就直接使用了呢？
--gong

阅读排行榜

评论排行榜

字符串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 阅读(5473) 评论(3) 编辑收藏引用所属分类: acm之路、C++之路

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: pow函数的性能测试一道算法题引发的动态内存管理的思考筛法求素数字符串hash函数插入排序泛型算法最大匹配匈牙利算法最小生成树Prim算法 itoa函数归并排序求逆序数单源最短路径Dijkstra算法

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜