轉(zhuǎn)載請注明出處?http://blog.csdn.net/yankai0219/article/details/8185847 問題： 1. hash算法主表實現(xiàn)為什么不直接用數(shù)組,而使用malloc動態(tài)申請? 2. 另外每個桶的使用 線性隊列 和 雙向隊列 以及 二級hash的區(qū)別以及好處是什么? 答案: ? ? ?1. ? ? ? ? ? 1）hash表大小如果是固定的，當(dāng)然可以采用數(shù)組； ? ? ??????struct hash_head ?*hash_list[1024]; ? ? ? ? ? 2）如果hash大小沒有確定，在程序中動態(tài)變化的，那就需要使用malloc動態(tài)申請。

int hash_size = get_hash_size(); struct? hash_head? **hash_list; *hash = malloc(hash_size); memset(*hash, 0, hash_size);

? ? ?2. ? ? ? ? ? 線性鏈表只能單相查找結(jié)點，即知道一個已知結(jié)點，不能找到它的前驅(qū)。 ?
雙向鏈表可以向前向后二個方向查找結(jié)點。
還有雙向循環(huán)鏈表，我在項目中用的比較多。直接用內(nèi)核里扒下來用的。 二級hash我到覺的沒什么必要。使結(jié)構(gòu)太復(fù)雜。可以用一級hash來代替。設(shè)計好hash算法就行了。 問題： 3. 1）已知一個線性表(38，25，74，63，52，48)，采用的散列函數(shù)為H(Key)=Key%7，將元素散列到表長為7的哈希表中存儲。若采用線性探測的開放定址法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為 ____ ； 2）若利用拉鏈法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為 ____；
答案:1）11/6 ，2）8/6.對于1）中，答案給出的是12/6=2，經(jīng)過驗證是錯誤的。 分析過程： 1）采用開放定址法

key	38	25	74	63	52	48
地址	3?	4	4	0	3	6
解決沖突過程	?	?	5	?	4 5 6	7
查找次數(shù)	1	1	2	1	4	2

平均查找長度：（1*3+2*2+4）/6=11/6 2)采用拉鏈法

拉鏈	鏈表中元素	查找次數(shù)
0	63	1
3	38 ? 52	38（1次） 52（2次）
4	25 74?	25（1次） 74（2次）
6	48	1

平均查找長度（1*4+2*2）/6=4/3
4.設(shè)一哈希表長為13，采用線性探測法解決沖突，哈希函數(shù)H(key)=key%13?
1 ）畫出在空表中依次插入關(guān)鍵字25.20.36.15.41.52.29.72.67后的哈希表? 2 ）求在等概率情況下，查找成功和查找不成功的平均查找長度

答案： 1）Hash表 ? ? ? ? ??

hash表下標(biāo)（地址）	0	1	2	3	4	5	6	7	8	9	10	11	12
hash表元素	52	?	15	41	29	67	?	20	72	?	36	?	25
解決沖突過程	?	?	?	2 3	3 4?	?2 3 4 5	?	?	7 8	?	?	?	?
查找次數(shù)	1	?	1	2	2	4	?	1	2	?	1	?	1

2）查找成功的平均查找長度：（1*5 +2*3 +4*1）/9 = 15/9 。查找成功的平均查找長度為SUM(查找次數(shù))/SUM(元素個數(shù)) 3) ?查找失敗的平均查找長度 計算長度為m的哈希表中裝填有n個記錄的查找不成功時的平均查找長度相當(dāng)于計算在這張表中填入第n+1個記錄時所需要的比較次數(shù)的期望值。
第N+1個記錄可能是0~12
若?N+1個記錄是0，由于位置0已經(jīng)被占用，位置1沒有占用，所以比較2次，依次類推。

hash表下標(biāo)	0	1	2	3	4	5	6	7	8	9	10	11	12
hash表元素	52	?	15	41	29	67	?	20	72	?	36	?	25
解決沖突過程	?	?	?	2 3	3 4?	?2 3 4 5	?	?	7 8	?	?	?	?
查找次數(shù)	1	?	1	2	2	4	?	1	2	?	1	?	1
查找不成功	2	1	5	4	3	2	1	3	2	1	2	1	3

故查找不成功的平均查找長度為（2+1+5+4+3+2+1+1+2+2+1+2+1+3）/13=30/13

5. 將關(guān)鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中。散列表的存儲空間是一個下標(biāo)從0開始的一維數(shù)組，散列函數(shù)為： ? ? ?H(key) = (keyx3) MOD 7，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。 (1) 請畫出所構(gòu)造的散列表。 (2) 分別計算等概率情況下查找成功和查找不成功的平均查找長度。

答案： （1） （2）查找成功的平均查找長度

(表3)

所以ASLsuccess= （1+1+1+1+3+3+2）/ 7 = 12/7 ? ??查找不成功的平均查找長度 計算查找不成功的次數(shù)就直接找關(guān)鍵字到第一個地址上關(guān)鍵字為空的距離即可， 但根據(jù)哈希函數(shù)地址為MOD7，因此初始只可能在0~6的位置

? ? 因此查找不成功的次數(shù)表如下表所示

(表4)

? ? ? ?所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。

參考文獻
http://zhan.renren.com/astart?gid=3602888498031032593? http://shijuanfeng.blogbus.com/logs/172381700.html? 轉(zhuǎn)載請注明出處http://blog.csdn.net/yankai0219/article/details/8185847

總結(jié)

以上是生活随笔為你收集整理的数据结构-Hash总结（三）：实践基础篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。