開散列方法

衝突解決技術可以分為兩類：開散列方法( open hashing，也稱為拉鏈法，separate chaining )和閉散列方法( closed hashing，也稱為開地址方法，open addressing )。這兩種方法的不同之處在於：開散列法把發生衝突的關鍵碼存儲在散列表主表之外，而閉散列法把發生衝突的關鍵碼存儲在表中另一個槽內。
衝突解決策略——開散列方法
1、拉鏈法
開散列方法的一種簡單形式是把散列表中的每個槽定義為一個鍊表的表頭。散列到一個特定槽的所有記錄都放到這個槽的鍊表中。例，一個開散列的散列表，這個表中每一個槽存儲一個記錄和一個指向鍊表其餘部分的指針。這7個數存儲在有11個槽的散列表中，使用的散列函式是h(K) = K mod 11。數的插入順序是77、7、110、95、14、75和62。有2個值散列到第0個槽，1個值散列到第3個槽，3個值散列到第7個槽，1個值散列到第 9個槽。
2、桶式散列
桶式散列方法的基本思想是把一個檔案的記錄分為若干存儲桶，每個存儲桶包含一個或多個頁塊，一個存儲桶內的各頁塊用指針連線起來，每個頁塊包含若干記錄。散列函式h把關鍵碼值K轉換為存儲桶號，即h(K)表示具有關鍵碼值K的記錄所在的存儲桶號。
例，一個具有B個存儲桶的散列檔案組織。有一個存儲桶目錄表，存放B個指針，每個存儲桶一個，每個指針就是所對應存儲桶的第一個頁塊的地址。
有些存儲桶僅僅由一個頁塊組成，如下圖中的1號存儲桶。有的存儲桶由多個頁塊組成，每一個頁塊的塊頭上有一個指向下一個頁塊的指針，例如，如下圖中的第B-1號存儲桶由b4，b5，b6三個頁塊組成，每個存儲桶中最後一個頁塊的頭上為空指針。