標籤: 暫無標籤

哈希表中元素是由哈希函數確定的。將數據元素的關鍵字K作為自變數,通過一定的函數關係(稱為哈希函數),計算出的值,即為該元素的存儲地址。

1 哈希函數 -哈希函數簡介

哈希表中元素是由哈希函數確定的。將數據元素的關鍵字K作為自變數,通過一定的函數關係(稱為哈希函數),計算出的值,即為該元素的存儲地址。表示為:
                   Addr = H(key)

2 哈希函數 -兩個主要問題



  ⑴構造一個合適的哈希函數
    均勻性  H(key)的值均勻分佈在哈希表中;
    簡單   以提高地址計算的速度
  ⑵衝突的處理
    衝突:在哈希表中,不同的關鍵字值對應到同一個存儲位置的現象。即關鍵字K1≠K2,但H(K1)= H(K2)。均勻的哈希函數可以減少衝突,但不能避免衝突。發生衝突后,必須解決;也即必須尋找下一個可用地址。



若已知哈希函數及衝突處理方法,哈希表的建立步驟如下:

  Step1. 取出一個數據元素的關鍵字key,計算其則哈希表中的存儲地址D=H(key)。若存儲地址為D的存儲空間還沒有被佔用,則將該數據元素存入;否則發生衝突,執行Step2。
  Step2. 根據規定的衝突處理方法,計算關鍵字為key的數據元素之下一個存儲地址。若該存儲地址的存儲空間沒有被佔用,則存入;否則繼續執行Step2,直到找出一個存儲空間沒有被佔用的存儲地址為止。
上一篇[台灣戲劇館]    下一篇 [台北廣播電台]

相關評論

同義詞:暫無同義詞