skyli
C++之夢

隨筆 - 62 文章 - 96 trackbacks - 0

2007年4月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

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

積分與排名

積分 - 237248
排名 - 108

閱讀排行榜

評論排行榜

字符串hash函數(shù)

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

#include<iostream>

#include<string>

using namespace std;

const int MAXN = 9973; //哈希表長度

const int len = 30; //字符串的最大長度

int Htable[MAX];

char ch[MAX][len]; //存儲關(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) 評論(3) 編輯收藏引用所屬分類: acm之路、C++之路

FeedBack:

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

請教：在insert函數(shù)中，key的值沒有存到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ù) 更多評論

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

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

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

怎么沒有寫完啊？回復(fù) 更多評論

刷新評論列表

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


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

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

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

<rt id="acac4"></rt>