回覆列表
-
1 # 使用者9213846046785
-
2 # 使用者2071604482426
關鍵字K1≠K2,但H(K1)= H(K2)。均勻的雜湊函式可以減少衝突,但不能避免衝突。發生衝突後,必須解決;也即必須尋找下一個可用地址。在雜湊表中,不同的關鍵字值對應到同一個儲存位置的現象。 開始插入59,i=0,h(59,0)=(59 mod 11 + 0*(1+59 mod 9)) mod 11=4,位置4與37衝突,繼續計算。 衝突1次,i=1,h(59,1)=(59 mod 11 + 1*(1+59 mod 9)) mod 11=10,位置10空,59插入到位置10。 如果再衝突,那麼i=2,繼續計算,以此類推。 25和72類似。
關鍵字K1≠K2,但H(K1)= H(K2)。均勻的雜湊函式可以減少衝突,但不能避免衝突。發生衝突後,必須解決;也即必須尋找下一個可用地址。在雜湊表中,不同的關鍵字值對應到同一個儲存位置的現象。開始插入59,i=0,h(59,0)=(59 mod 11 + 0*(1+59 mod 9)) mod 11=4,位置4與37衝突,繼續計算。衝突1次,i=1,h(59,1)=(59 mod 11 + 1*(1+59 mod 9)) mod 11=10,位置10空,59插入到位置10。如果再衝突,那麼i=2,繼續計算,以此類推。25和72類似。擴充套件資料:選擇一個隨機函式,取關鍵字的隨機函式值為它的雜湊地址,即H(key)=random(key),其中random為隨機函式。通常用於關鍵字長度不等時採用此法。若已知雜湊函式及衝突處理方法,雜湊表的建立步驟如下:Step1、取出一個數據元素的關鍵字key,計算其在雜湊表中的儲存地址D=H(key)。若儲存地址為D的儲存空間還沒有被佔用,則將該資料元素存入;否則發生衝突,執行Step2。Step2、根據規定的衝突處理方法,計算關鍵字為key的資料元素之下一個儲存地址。若該儲存地址的儲存空間沒有被佔用,則存入;否則繼續執行Step2,直到找出一個儲存空間沒有被佔用的儲存地址為止。