有點意思5792
哈希表是根據關鍵值(key)來直接訪問目標值(value)的一種數據結構。其特點就在於能夠快捷的實現信息的查詢和檢索。
比如我們在手機中存放的通訊錄就是用哈希表來實現的，即我們輸入一個聯繫人的姓名，就能返回相應的電話號碼。用哈希表實現的過程就是，將聯繫人姓名的字符通過一個哈希函數，映射成一個整數（哈希碼），然後根據哈希碼來索引出電話號碼。比如哈希碼為5，就表示是在存儲位置為5，因此我們就能直接取出該位置的值，並返回結果。
那麼實現哈希表的關鍵就在於哈希函數的構建，也就是如何建立一個合適的索引來滿足如下條件：
1）同一個鍵每次輸入到哈希函數中，其對應的哈希碼也必須相同；
2）不同鍵對應的哈希碼不能相同。
第一個條件意味著哈希函數必須是確定性的；第二個條件則要求不能出現哈希衝突。當兩個或更多個鍵產生相同的哈希碼時就會發生衝突（hash collisions）。
比如我們現在考慮建立一個簡單的哈希表來查詢年齡,{Jim：5, Davis：7, Taylor:12, Bob:3}，如果我們選擇哈希函數為輸入鍵值的字符個數。那麼在建立哈希表時，就講Jim存放在位置3處，Jack存放在位置4處。而這樣的話Jim和Bob的存儲位置就會發生衝突，不符合哈希函數的要求。但是如果我們將哈希函數替換為首字母順序存放，在這個數據中就沒有哈希衝突了。
然而萬一無法避免哈希衝突的話，我們可以用鏈接和線性探測的方法來避免哈希值發生碰撞。
鏈接就是將發生衝突的鍵值直接鏈接在鏈表的尾部；線性探測則是，如果在位置i處發生衝突，那麼就檢查i+1處是否為空，為空的話就將衝突鍵值放入其中，否則繼續檢查下一個。
分享到:
