線性開型定址散列，也稱開放定址法，有的元素都存放在散列表里，每個表項或包含動態集合的一個元素或者NIL。當查找某個元素時，要系統的檢查所有表項，直到找到所有的元素或者最終查明元素不在表中。為了使用開放定址法插入一個元素，需要連續的檢查散列表，或稱為探查(probe)，直到找到一個空槽來放置待插入的關鍵字為止。檢查的順序不一定是0,1,2…m的順序序列，而是依賴於待插入的關鍵字。
基本介紹
- 中文名：線性開型定址散列
- 外文名：linear probing
- 學科：數據結構
- 別名：開放定址法
- 目的：解決散列衝突
- 方法：線性探查、雙重散列
簡介,方法,衝突,
簡介
散列表也稱作哈希表，是根據記錄的關鍵字進行直地址運算，進而進行數據訪問的一種數據結構．散列表地址轉換的基本思路為：定義一個記錄的關鍵字與地址之間的一種映射關係，通過這個映射關係，根據關鍵字直接計算出記錄的地址．通常，記錄關鍵字用key表示，用h表示關鍵字和記錄地址間的函式關係，即為散列函式，記錄的地址用h(key)表示。兩個不同的關鍵字，由於散列函式值相同，因而被映射到同一表位置上，該現象稱為衝突或碰撞發生衝突的兩個關鍵字稱為該散列函式的同義詞。線性開型定址散列是一種處理散列碰撞的方法，當發生碰撞時，線性探測法檢查散列表中的下一個位置是否為空。如果為空，就將數據存入該位置；如果不為空，則繼續檢查下一個位置，直到找到一個空的位置為止。
該散列方法的思想在於：插入一個關鍵字k，如果k被占用，則往後一個位置插入， 直到沒有空間。與連結法相比，不需要指針，所以可以將指針所占用的空間存放更多的槽。缺點在於：該方法的刪除操作，如果刪除了某個關鍵字後，無法檢索到以後的關鍵字了。如果用一個特定的值代替，查找時間就不依賴於轉載因子α了。定義一個均勻散列的假設：每個關鍵字的探查序列等可能的為0，1…,m-1中的m!中排列的一種。
當查找一個元素時，要檢查所有的表項，直到找到所需的元素，或者最終發現元素不在表中。不像在連結法中，這裡沒有鍊表，也沒有元素存放在散列表外。在這裡散列表有可能會被填滿，但是裝載因子（動態集合元素/散列槽數）絕對不會大於1。在開放定址法中，當要插入一個元素時，可以連續地檢查散列表的個各項，直到找到一個空槽來放置這個元素為止。檢查順序可以是線性的，可以是二次的，也可以是再次散列的。
查找關鍵字和插入關鍵字的算法基本上是一樣的。
在開放定址法中，對散列表元素的刪除操作執行起來比較困難。當我們從槽i中刪除關鍵字時，不能僅將NIL置於其中來標識它為空。因為這樣做的話，會導致在插入另外的關鍵字探查過程中，有可能無法檢索某些關鍵字。這裡有一個解決方法，就是在槽i中置一個特定的槽當作空槽，從而可以插入新元素。
1.線性探查給定一個普通的散列函式h’:U->{0,1,2…m-1}(稱為輔助散列函式)，線性探查方法採用的散列函式為：h(k,i)=(h’(k)+i) mod m , i=0,1,2,…m-1
給定一個關鍵字k，第一個探查的槽是T(h’(k)),接下來探查下一個槽，直到T[m-1]。
線性探查方法比較容易實現，但存在一個問題，成為一次群集。隨著時間的推移，連續被占用的槽不斷增加，平均查找時間也隨著不斷增加。群集現象很容易出現，這是因為當一個空槽前有i個滿的槽時，該空槽為下一個將被占用的槽的機率是(i+1)/m，連續被占用的槽的序列將會變得越來越長，因而平均查找時間也會隨之增加。2.二次探查（quadratic probing）採用的形式如下：
h(k,i)=(h’(k)+c1i+c2i^2)modm
其中h’是一個輔助散列函式，c1和c2為輔助常數，i=0,1,…m-1。初始的探查位置為T[h’(k)],後續的探查位置要在此基礎上加上一個偏移量，該偏移量是以二次的方式依賴於探查號i的。如果兩個關鍵字的初始探查位置是相同的，那么他們的後續二次探查的序列也是相同的。這種性質會導致一種程度較輕的群集現象，成為二次群集。3.雙重散列是用在開放定址法的最好方法之一，因為它所產生的排列具有隨機選擇的排列的許多特性。它採用如下形式的散列函式：
h(k,i)=(h1(k)+i*h2(k))modm
其中h1和h2是輔助散列函式。初始探查位置為T[h1(k)],後續的探查位置在此基礎上加上偏移量h2(k)模m。與線性探查和二次探查不同的是，這裡的探查序列以兩種方式依賴於k，因為初始探查位置和偏移量都可能發生變化。
方法
線性探測是電腦程式解決散列表衝突時所採取的一種策略。散列表這種數據結構用於保存鍵值對，並且能通過給出的鍵來查找表中對應的值。線性探測這種策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所發明，並且最早於1963年由Donald Knuth對其進行分析。
John Smith和Sandra Dee（都被雜湊映射到了單元873）的衝突，藉由把後者放在下一個空閒單元（單元874）而解決
與二次探測和雙散列一樣，線性探測是一種開放定址的策略。在這些策略里，散列表的每個單元都存儲一對鍵值對。當散列函式對一個給定值產生一個鍵，並且這個鍵指向散列表中某個已經被另一個鍵值對所占用的單元時，線性探測用於解決此時產生的衝突：查找散列表中離衝突單元最近的空閒單元，並且把新的鍵插入這個空閒單元。同樣的，查找也同插入如出一轍：從散列函式給出的散列值對應的單元開始查找，直到找到與鍵對應的值或者是找到空單元。正如Thorup和張寅在2012年所寫，…“散列表是最常用的普通數據結構，它在硬體上的標準實現中最流行的方法就是使用線性探測。線性探測又快又簡單。”線性探測能夠提供高性能的原因是因為它的良好的引用局部性，然而它與其他解決散列衝突的策略相比對於散列函式的質量更為敏感。當使用隨機散列函式， 5-independent散列函式或tabulation散列函式，其用於搜尋，插入或刪除的預期時間是常數。不過，藉由其他像是私語雜湊的散列函式可以在實作中達到較好的結果。
二次探測是計算機編程中用於解決哈希表中衝突的開放定址方案- 當傳入數據的哈希值表明它應該存儲在已占用的槽或桶中時。二次探測通過獲取原始哈希索引並添加任意二次多項式的連續值直到找到開放時隙來進行操作。二次探測在封閉散列表中可以是更有效的算法，因為它可以更好地避免線性探測可能發生的聚類問題，儘管它沒有免疫力。它還提供了良好的記憶體快取，因為它保留了一些引用的位置 ; 然而，線性探測具有更大的局部性，因此具有更好的高速快取性能。
雙散列是一種計算機編程技術，用於散列表中以解決散列衝突，在要搜尋的兩個不同值產生相同散列鍵的情況下。它是開放式地址哈希表中一種流行的衝突解析度技術。雙散列在許多流行的庫中實現。與線性探測一樣，它使用一個哈希值作為起始點，然後重複前進一個間隔，直到找到所需的值，到達空位置，或者搜尋整個表格; 但是這個間隔是使用第二個獨立的散列函式決定的（因此名稱為雙重散列）。與線性探測和二次探測不同，間隔取決於數據，因此映射到同一位置的偶數值具有不同的桶序列; 這可以最大限度地減少重複碰撞和聚類的影響。
衝突
兩個不同的關鍵字，由於散列函式值相同，因而被映射到同一表位置上。該現象稱為衝突(Collision)或碰撞。發生衝突的兩個關鍵字稱為該散列函式的同義詞(Synonym)。
安全避免衝突的條件
最理想的解決衝突的方法是安全避免衝突。要做到這一點必須滿足兩個條件：
①其一是|U|≤m
②其二是選擇合適的散列函式。
這隻適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函式h有可能完全避免衝突。
衝突不可能完全避免
通常情況下，h是一個壓縮映像。雖然|K|≤m，但|U|>m，故無論怎樣設計h，也不可能完全避免衝突。因此，只能在設計h時儘可能使衝突最少。同時還需要確定解決衝突的方法，使發生衝突的同義詞能夠存儲到表中。
衝突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿，衝突的機會也越大。通常取α≤1。對於大多數應用程式來說，裝填因子為0.75是比較合理的。
