資料結構 雜湊(Hashing)

Question

For hashing search:
(a) What\'s a perfect hashing?
(b) Considering solutions for the hashing collision, find the hashing tables of using (i) linear probing method and (ii) linked list method, with a circular space of 11 vacancies and a data sequence of 9, 16, 27, 34, 42, 69, 75, 82, 95
請大家幫幫我解答...我不了解雜湊的意義是什麼
所以不知道怎麼解答它...希望大家幫我...謝謝喔

Answer 1

不會呀!只是第二題看不大懂!不過hash的概念說明的很清楚!真的很謝謝你喔^^~呵呵

Answer 2

(a) 經hashing function計算後無collision及overflow稱之
(b) linear:
0　１　２　３　４　５　６　７　８　９　 10
75　34　　　69　　　16　27　82　95　9　　42
首先9的位置為:H(9)=9%11=9,放在9的位置,其後類推. 之後27位置為
H(27)=27%11=5,(發生collision),所以往後找有空位的地方,所以放在6的位置

linked list:
０　１　２　３　４　５　６　７　８　９　10
　　34　　　69　　　16　　　95　　　９
　　　　　　　　　　27　　　　　　　42
　　　　　　　　　　82　　　　　　　75
hashing方法同上,而當發生collision時,則以link連結至下一位置