知識總覽：

拉鏈法：

開始散列表中沒有存儲任何數據元素即散列地址上的元素是空的，散列地址可以視為鏈表的頭指針，即沒有插入任何元素前鏈表的頭指針是空的。一個散列地址對應一個鏈表，散列地址上實際沒有存數據元素，所有的數據元素都存儲在鏈表上了。

散列表使用拉鏈法插入元素步驟：

1.根據散列函數算出數據元素要插入的散列地址

2.將新元素插入散列地址對應的鏈表，可使用頭插法(即把元素每次都插入在鏈表的頭部)或尾插法(即把元素每次都插入在鏈表的尾部)。以下例子默認使用頭插法

如開始插入19元素，散列函數計算得出散列地址=6,頭插法插在鏈表頭部，后來又插入84數據元素，散列函數計算出的散列地址也是6，頭插法則把84插入在鏈表頭部，即84在19上部。。。。。。

散列表使用拉鏈法查找元素：

?步驟：

1.根據散列函數，計算目標元素的散列地址，找到對應鏈表

2.順序查找鏈表，開始進行關鍵字比較

如查找目標元素27，由散列函數計算出的散列地址為1，從1對應上的鏈表從頭開始順序查找，先比較79，不相等繼續比較27，相等，關鍵字比較2次查找成功，即查找長度為2

如查找目標元素66，由散列函數計算出的散列地址為1，從1對應上的鏈表從頭開始順序查找，先比較79，不相等繼續比較27，不相等繼續比較1，不相等繼續比較14，鏈表上的元素比較完了也沒找到66，則查找失敗，關鍵字比較次數4次，查找長度=4

如查找目標元素21，由散列函數計算出的散列地址為8，8位置上對應的空鏈表即NULL，則查找失敗，因為是空鏈表NULL沒有任何關鍵字即沒有值，所以關鍵字的比較次數為0次，即查找長度為0，有的教材上也說是1次，在考試中如果么有特別說明就認為是比較0次

散列表使用拉鏈法刪除元素：

?步驟：

1.根據散列函數，計算目標元素的散列地址，找到對應鏈表

2.順序查找鏈表，開始進行關鍵字比較，在鏈表中找到目標元素了，再根據鏈表特性刪除

只要能在鏈表中找到這個元素都能刪除。

如下刪除目標元素27，由散列函數計算出的散列地址為1，從1對應上的鏈表從頭開始順序查找，先比較79，不相等繼續比較27，相等，關鍵字查找成功，然后再刪除27(跟鏈表的刪除一樣)，修改對應的指針

如下刪除目標元素20，由散列函數計算出的散列地址為7，從7對應上的鏈表從頭開始順序查找，先比較20相等，刪除20元素，然后把7位置上的鏈頭指針置為空

如下刪除目標元素66，由散列函數計算出的散列地址為1，從1對應上的鏈表從頭開始順序查找，找完了也沒找到66，刪除失敗

?知識回顧：

拓展：

散列表中頭插法插入元素時，每次插入的元素都是無序的，導致在散列表查找元素時，只能順序的在鏈表一個一個元素挨個比較，效率低，則在鏈表插入時可以比較元素大小，讓鏈表插入的時候保持一個有序的狀態，根據大小把元素插入到鏈表對應位置，即在插入時也排序，則在查找時效率會高一些

?

又水一篇。。。。。。。。。。以上純屬個人理解。。。。。。。。 。。。。。