Zi 字媒體
2017-07-25T20:27:27+00:00
此篇文章瀏覽量:
1,934
雜湊表是非常實用的資料結構之一,有三個主要的面向需要學習,分別是:實作(Implementation)、碰撞(Collision)、雜湊函數。
雜湊函數
是一種輸入字串,然後輸出數字的函數。也就是「將字串對應至數字」。
例:
“Apple” → 雜湊函數 → 3
作用原理:
1、雜湊函數始終將一個特定的名稱對應於相同的數字,每次輸入 “Apple”,都會得到相同的數字(例如 3)。
2、雜湊函數將不同的字串對應至不同的索引值。例: “Apple” 對應至 3;”Milk” 對應至 4。
3、雜湊函數知道陣列的大小,而且只傳回有效的索引值。
透過雜湊函數與陣列的結合,可得到一個 雜湊表(Hash Table) 資料結構。雜湊表又稱為雜湊地圖(Hash Map)、字典(Dictionary)、關聯式陣列(Associative Array)。例:
book['apple'] = 0.65
book['milk'] = 1.43
使用案例:手機內建電話簿、網址對應至 IP、用在網頁快取(Cache)的應用(URL對應至網頁內容)。
碰撞
使用者必須瞭解雜湊表的效能,也就是碰撞。如果碰撞的問題過多,那將會導致雜湊表的效能變慢,所以應該儘可能避免,好的雜湊函數,會儘量避免碰撞的問題發生。
什麼是碰撞?先前提到,雜湊函數必定將不同的鍵對應至不同的陣列儲存槽。但事實上,還是有可能發生同一個鍵對應到相同的陣列儲存槽情況,例如:一個雜湊函數的定義,將字母為 A 開頭的,對應至第1個儲存槽,則 Apple 的價格會被放到第1個儲存槽,然後 Almond 的價格也會被放到第1個儲存槽,因為都是以 A 開頭,那 Apple 的價格就被 Almond 覆寫了,這就是碰撞。解決辦法是在此儲存槽啟用連結串列。如果項目不多,啟用連結串列是還ok,但如果項目很多,效能就會因此而降低了。
所以一般來說:
1、理想的雜湊函數是將在雜湊表上均勻的完成鍵的對應。
2、連結串列過長會導致雜湊表變慢,所以好的雜湊函數,將不致於發生連結串列過長的問題。
雜湊表的效能
平均情況:搜尋、插入、刪除,皆為 O(1)
最壞情況:搜尋、插入、刪除,皆為 O(n)
O(1) 稱為常數時間(Constant Time),代表不論雜湊表多麼大,耗費的時間皆維持不變的意思。
註:雜湊表一般來說,不需要自己實作,因為通常程式都會內建了,例如:關聯式陣列、字典。
若覺得文章有幫助,請多分享,讓其他同好也能吸收網站技能知識。
Facebook
Twitter
寫了
5860316篇文章,獲得
23313次喜歡