線性探測

與二次探測和雙散列一樣，線性探測是一種開放尋址的策略。在這些策略裏，散列表的每個單元都存儲一對鍵值對。當散列函數對一個給定值產生一個鍵，並且這個鍵指向散列表中某個已經被另一個鍵值對所佔用的單元時，線性探測用於解決此時產生的衝突：查找散列表中離衝突單元最近的空閒單元，並且把新的鍵插入這個空閒單元。同樣的，查找也同插入如出一轍：從散列函數給出的散列值對應的單元開始查找，直到找到與鍵對應的值或者是找到空單元。

正如Thorup和張寅在2012年所寫，…“散列表是最常用的普通數據結構，它在硬件上的標準實現中最流行的方法就是使用線性探測。線性探測又快又簡單。”線性探測能夠提供高性能的原因是因為它的良好的引用局部性，然而它與其他解決散列衝突的策略相比對於散列函數的質量更為敏感。當使用隨機散列函數，5-independent散列函數或tabulation散列函數，其用於搜索，插入或刪除的預期時間是常數。不過，藉由其他像是私語雜湊的散列函數可以在實作中達到較好的結果。 ^[1] 

雜湊衝突一般發生於雜湊函數將一個鍵丟進已經含有另一個不同鍵的單元中的時候。線性探測是一個用來解決衝突的策略，其將新鍵丟進最靠近的下一個空單元中。

為了搜索給定的鍵 x，散列表中由h(x)對應的單元開始的相鄰單元h(x) + 1,h(x) + 2, ..., 都將被檢查，直到找到了內容為空的單元或是找到了存儲給定鍵為x的單元。其中，h是散列函數。如果找到了存儲給定鍵的單元，搜索將會返回單元中存儲的鍵對應的值。否則，如果搜索遇到了空的單元，鍵在表中就不存在，因為鍵應當被存放在所有未被搜索的單元之前。此時，搜索返回表中無此鍵的結果。 ^[2] 

為了在表中插入一對鍵值對(x,v)（有可能會替換有着相同鍵的鍵值對），插入算法也會訪問搜索算法訪問的同一系列單元，直到找到一個空的單元，或是找到了存儲給定鍵為x的單元。新的鍵值對將會存儲在此單元中。

如果插入將導致表（佔用單元的比例）增長高於某個預設的閾值的負載係數，整個表可以通過一個新的表（規模大於本表規模）和一個新的散列函數來代替，如使用動態數組。設置這個的閾值接近於零，並使用表大小的高增長率來帶來更快速的哈希表的操作，但相比於接近一個閾值與低增長率，它會帶來更高的內存使用情況。一個常見的選擇是表規模擴大一倍，當負載係數將超過1/2，導致負載係數保持在1/4和1/2之間。 ^[2] 

當一對鍵值對被刪除，可能會有必要將其他的鍵值對放回到它的單元中，來防止搜索時搜索到空的單元。

散列表應當提供刪除鍵值對的功能。然而，單純地清空對應的單元是不夠的。這會影響到對於儲存時間早於該單元、但儲存位置在該單元之後的其他鍵。此單元會造成搜索獲得錯誤的結果，告訴使用者這些鍵並不存在。

相較於直接清空對應單元i，更好的做法是先清空，然後把它之後所有會造成問題的單元向前移動，來避免搜索出錯。重複直到出現空單元，則刪除動作安全完成。但是，如果有發現後續有鍵可以移到這個位置上的話，直接將該鍵取代欲刪除的單元可以加速後續的其他行為，當然，這樣也會造成後面多出一個新的空單元。搜索可用來取代的單元的動作會持續到搜索到原本就空白的單元為止。在這個將鍵移到前面的過程中，所有的鍵都會被算過一遍。因此，完成這整個過程所需的時間與該儲存位置的單元數量呈正比，與雜湊表的其他運算相符。

有一種可行的替代方案是懶惰刪除，用指向欲刪除鍵的特殊的標誌值（flag value）取代原本的鍵值配對。不過，這些標誌值在搜索上會當作非空。因此，如果一個陣列中有過多的被刪除鍵，那麼就需要清除所有的標誌值並且重新雜湊整個表。 ^[2]