skyli
C++之夢(mèng)

隨筆 - 62 文章 - 96 trackbacks - 0

2006年10月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

30

1

2

3

4

5

6

7

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內(nèi)網(wǎng)

積分與排名

積分 - 237373
排名 - 108

閱讀排行榜

評(píng)論排行榜

字符串hash函數(shù)

字符串hash函數(shù)，解決沖突用開(kāi)放定址法，每次對(duì)哈希值加1
在下列程序中，不是按常規(guī)方法用哈希表來(lái)記錄關(guān)鍵字，
而是用整型數(shù)組Htable記錄關(guān)鍵字在字符串ch中的位置。
在插入時(shí)不用把關(guān)鍵字復(fù)制到哈希表中，只是記錄一個(gè)索引，從而提高了效率。
當(dāng)查詢時(shí)，只要把Htable的值映射到字符串ch中就可以了。
注意ch的下標(biāo)要從1開(kāi)始，因?yàn)镠table中的零值認(rèn)為是空，處理起來(lái)比較方便。

#include<iostream>

#include<string>

using namespace std;

const int MAXN = 9973; //哈希表長(zhǎng)度

const int len = 30; //字符串的最大長(zhǎng)度

int Htable[MAX];

char ch[MAX][len]; //存儲(chǔ)關(guān)鍵字的字符串

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為關(guān)鍵字在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 閱讀(5547) 評(píng)論(3) 編輯收藏引用所屬分類: acm之路、C++之路

FeedBack:

# re: 字符串hash函數(shù) 2007-07-04 00:45 原來(lái)如此

請(qǐng)教：在insert函數(shù)中，key的值沒(méi)有存到ch組里面去吧？

int insert(char * key, int j) //j為關(guān)鍵字在ch中的位置，即索引
{
unsigned long i = Hash(key);
while(Htable[i])
i = (i + 1) % MAX;
Htable[i] = j;
return i;
} 回復(fù) 更多評(píng)論

# re: 字符串hash函數(shù) 2007-07-09 21:34 beyonlin

@原來(lái)如此
我是把key的值在函數(shù)外存入ch中，
看你的留言后覺(jué)得還是在insert函數(shù)里面把key存到ch組比較嚴(yán)謹(jǐn)一點(diǎn)。
謝謝！回復(fù) 更多評(píng)論

# re: 字符串hash函數(shù) 2009-04-01 13:31 nuoshueihe

怎么沒(méi)有寫完啊？回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: pow函數(shù)的性能測(cè)試一道算法題引發(fā)的動(dòng)態(tài)內(nèi)存管理的思考篩法求素?cái)?shù) 字符串hash函數(shù) 插入排序泛型算法最大匹配匈牙利算法最小生成樹(shù)Prim算法 itoa函數(shù) 歸并排序求逆序數(shù) 單源最短路徑Dijkstra算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品