一系列用於雜湊查詢的簡潔演算法

本節是順序查詢和二分法的延續。 本節相對獨立，因此，如果您只想了解雜湊表和雜湊查詢，請閱讀此部分。 如果您想對搜尋演算法有乙個系統的了解，我們建議您先閱讀上一節。

本文前三段都是基礎介紹，沒有具體的演算法問題，如果對這部分知識有一定的了解，可以直接跳到第四部分。

正如我們前面提到的，使用順序查詢方法來確認未排序陣列中元素的存在的時間複雜度為o(n)。基本類似於蠻力查詢，沒有什麼特殊技能可言，具體時間取決於運氣，但平均而言，它與陣列的大小呈線性關係。 如果陣列被排序，我們可以使用時間複雜度為o(log(n))。但分揀本身是有代價的。 正如我們將在接下來的幾節中看到的那樣，排序是乙個相當昂貴的過程。 因此，僅僅為了更容易找到陣列而對陣列進行排序是非常不經濟的。

那麼有沒有一種搜尋方法，既不要求陣列排序好，又能達到很高的搜尋效率呢？

正如標題所暗示的那樣，這種方法是存在的。

對於我們前面討論的兩次查詢，給定乙個任意值，例如整數 4，可以存在於陣列中的任何位置。 例如，對於長度為 8 的陣列a[8]，4 此值可能不存在，或者可能儲存在a[0]a[7]介於兩者之間。 這使得我們很難找到它：我們事先不知道它可能在哪裡，所以我們需要使用各種愚蠢的方法來列舉、探測和縮小它的範圍。

這給了我們乙個新想法：如果我們能在乙個值和它可能儲存的位置之間建立關係，那麼當我們想要找到乙個值時，我們只需要看一眼可能的位置。 如果沒有，則該元素不在陣列中。 這樣，我們就可以完成查詢，而不必遍歷整個陣列。

讓我們舉乙個最簡單的例子：假設我們有乙個大小為 5 的陣列a[5]用於儲存整數，陣列起初是空的。

此時，需要儲存乙個新值 38。 這一次我們沒有把它放在先到先得的基礎上a[0]取而代之的是，我們事先商定了乙個規則：傳入值儲存在等於該數字除以 5 的餘數的位置。 。所以我們把 38 放進去a[3]

後來又出現了幾個數字，我們遵循取 5 的餘數並將它們分開放置的規則a[1] a[0] a[4] a[2]

儲存任務完成。

如果我想找到它，我該怎麼辦？假設我們想檢視陣列中是否存在 4，我們不必遍歷整個陣列。 我們知道每個數字的儲存位置等於其除以 5 的餘數，因此我們只需要遵循此規則a[4]看看那裡。 “是”就是“是”，“否”就是“否”。 請注意，時間複雜性是o(1)！這意味著，在理想情況下，無論陣列有多大，我們都可以將其淘汰，因為我們知道儲存規則乙個相應的門，只要開啟這扇門我們就可以判斷結果。 此過程的時間損失是恆定的，與陣列大小無關。

這是最簡單的雜湊表。 除其他外x%5它是它的雜湊函式，通過雜湊函式，我們將每個傳入的值對映到它應該去的地方。 這使我們非常方便地找到它：現在我們知道它要去哪裡，我們只需要去這個位置看一看。

以上是乙個理想的基本雜湊表。 您可能發現了很多問題：

例如，如果出現兩個數字，則餘數除以 5 相等跟此時如何分配房間？

除以 5 是心血來潮嗎，為什麼不除以 6？

好吧，便利並非沒有代價。 乙個被選中了o(1)方式，有必要打包並承擔它帶來的所有問題。

上述雜湊函式的最大問題是它們會導致衝突。 當兩個數字到 5 的餘數相等時，它們爭奪相同的位置。 因此，如何將每個傳入號碼對映到乙個唯一的位置是設計雜湊函式時的乙個大問題。

一種可能的解決方案是使餘數除數非常大，以便在一定程度上避免衝突。 假設如果除數設定為 10000000，那麼 10000000 以內的整數可以通過取它的餘數來獲得乙個唯一值，並且它們都會被分配到不同的房間，所以不會發生衝突。

但以成本計算，您必須相應地準備 10,000,000 個房間。 這對記憶來說是乙個巨大的挑戰。 除非我們有很多元素，否則你可以想象這種記憶體利用率是極低的。

另一種方法是拆解乙個大數字，例如，如果我們想儲存乙個**數字 135-234-232-10。 我們可以把它拆成乙個三位一體，總結一下：。在這種情況下，如果陣列大小為 12，則餘數為 11。

另一種常用的方法是所謂的中方法。 假設我們要儲存的數字是 35，求其平方，取中間兩位數得到 22，然後根據陣列的大小取餘數。

如果我們儲存的不是整數，而是乙個字元，那麼我們也可以通過獲取 ASCII 程式碼來獲取該值的值，然後設計雜湊函式。

總之，設計雜湊函式有許多常用的方法，但沒有系統的一刀切方法。 這裡的要點是：

盡量避免衝突，盡量提高空間利用率，根據儲存物件的性質設計不同的雜湊函式例如，如果我們儲存的數字都是 5 的倍數（比如網球比賽的比分，那麼使用餘數就不合適了），這裡可以參考一些雜湊函式的設計。 基本上，無論雜湊函式設計得多麼巧妙，衝突在某種程度上總是不可避免的。 那麼，如果發生衝突怎麼辦？如果陣列已滿，每個位置都有人，那麼當然沒有別的辦法了。 即使對於一般陣列也是如此，因此我不會在這裡討論它。 要考慮的情況是，如果陣列中仍有空白空間，那麼自然的選擇是為新元素找到乙個次優位置。

問題是如何找到它

我們使用empty指示陣列的空插槽中沒有人。 假設取了 7 的盈餘，陣列當前如下所示：

a[7] = [35, empty, empty, 3, 11, 19, 34];

一種方法是儲存在附近，如果該位置中已經有餘數為 0 的人，則將其儲存到餘數為 1 的位置，如果仍然不起作用，則將其儲存到下乙個位置，依此類推。 這種方法稱為線性探測。

這種方法的優點是它很簡單，但潛在的問題是，如果某個位置有很多衝突的值，除了最先佔據的元素外，所有元素都會被推遲。 請注意，此線性探測是 ***。 與上面的示例一樣，儲存了 7 個a[1]，這也使得那些餘數為 1 的數字必須找到另乙個位置，這可能會產生連鎖效應：在a[0]在這個街區附近，所有的數字都不在它們應該在的地方。

一種方法是一次移動乙個以上的位置，以確保整個陣列均勻分布。 這樣，它就不會糾纏在乙個角落（聚類）。 所以，除了加乙個，我們也可以加三，加五。 此過程以下列方式表示：

new_position = (original_positon + offset) %array_size

另一種方法是用它設定乙個固定的offset我們可以更改這個值，例如，在開始時通過新增乙個來查詢空缺位置，如果它不起作用，則新增 4，如果它不起作用，則新增 9、16、25......

處理衝突的另一種方法是鏈定址。 這意味著原始陣列不是儲存特定值，而是在每個房間中放置乙個對映（指標），該對映指向導致相同餘數的元素集。 這聽起來很複雜，但讓我們用下圖（除以 5）來說明它：

第一行用於儲存指標，如果出現相應的元素，則將其放入相應的鏈中。 這種方法的優點是我們可以確定乙個元素在哪個鏈中，例如，與啟發式不同，我們不必擔心餘數為 2 到 3 的數字。 但是，缺點也是可想而知的，隨著鏈長的增加，查詢的難度也隨之增加，地圖本身的儲存也占用了一定的記憶體量。

那麼這兩種方法哪一種更好呢？這個問題這裡就不贅述了，有興趣的可以參考這裡。 示例 1創業公司一直堅持小而美的理念，員工人數一直保持在11人以下。 設計一種資料型別來儲存每個員工的工作編號和工資，並要求在給定某個員工編號時，可以在o(1)（或返回：員工編號不存在）。 作業編號的格式為：yyyymmdd，輸入日期，例如，工資以美元計量，例如：。具體需要的實現類如下：

類員工資訊： def init （self，size）： 定義**的大小，以及兩個專案：工作編號和工資 selfsize = size self.id = [none]*self.size self.salary = [none]*self.size def set（self，id，salary）： 該函式用於輸入資料，輸入員工編號和工資，並儲存在資料表中 def get（self，id）： 此函式返回具有員工 ID 的員工工資 def hash function（self，id）： 定義雜湊函式 def collision resolve（self， origin， offset）：定義衝突解決方案，無論此處可以使用哪種方法

class employee_info: def __init__(self,size): self.size = size self.id = [none]*self.size self.salary = [none]*self.size def set（self，id，salary）： 找到職位編號對應的雜湊值，這裡用的餘數方法是員工編號 %selfsize hash_value = self.hash function（id） 如果對應房間沒有人，很簡單，如果自己id[hash_value] == none: self.id[hash_value] = id self.salary[雜湊值] = salary 如果房間裡有人，則應進行衝突解決 否則： time = 1 這用於測試位址，直到 self 出現空缺id[hash_value] != none：二次探測偏移量 = time**2 用於通過衝突解決函式確定下乙個暫定房間 hash 值 = self碰撞解析（雜湊值，偏移量） 時間 += 1 到自身id[hash_value] = id self.salary[hash value] = salary def get（self，id）： 或者找到對應的雜湊值 = selfhash_function(id) if self.id[hash_value] == none: return '作業編號不存在！'否則，開始尋找它，如果進展順利，就找到一次，否則你必須遵循二次探測的可能位置，直到工作編號的值與 time = 1 匹配，而 selfid[hash_value] != id: offset = time*2 hash_value = self.衝突 resolve（hash value，offset） time += 1 被找到，返回對應的工資返回 selfsalary[hash value] def hash function（self， key）： 餘數返回 key%self。size def collision resolve（self， origin， offset）： 衝突解決返回 （origin+offset）%self。size

我們輸入一組資料來執行測試：

t = employee_info(11)t.set(20131225,180000)t.set(20140825,90000)t.set(20141110,112300)t.set(20141121,112300)print t.idprint t.salaryprint t.get(20131225)print t.get(20111220)

[20141110、20140825、無、無、20131225、20141121、無、無][112300、90000、無、無、180000、112300、無、無] 180000 不存在

上述實現是乙個最小化的類，僅用於說明目的。 即使只是為了習修煉，也有一些基本的事情需要考慮。

西在上面的**中，假設有人加薪，工號為20140824的員工的工資從96,000漲到了112,200，這個時候我們該如何更新呢？與現有的set該功能能解決問題嗎？如果沒有，請修改set功能可以滿足這一需求。 或者再新增乙個update功能。

例如，如果有人離開了公司，資料自然被刪除，那麼是否應該定義乙個？del像這樣的功能？這是如何工作的？

此外，如果我們定義乙個包含 11 個資料的表並輸入 12 條資料，此時會發生什麼？如何修改上面的**，保證輸入的資料不超過資料表的大小？

這些問題留給大家，如果寫出相應的**（不管是什麼語言），請記得分享給我！

Python 自帶dict此資料型別可以方便地用於儲存鍵值等資料。 在下面的示例中，我們將使用它。 當然，你也可以用它來代替它，但稍微改變一下你在上一節寫的雜湊表，你也可以用它來解決下面的問題。 dict使用方法非常簡單，詳情可以看這裡。 示例 2給定乙個陣列和乙個目標值，從陣列中找到兩個數字，使它們的總和等於目標值，返回陣列中兩個數字的下標（從開頭開始）。

比如，給定跟，則返回兩個下標 1 和 3，注意這裡的下標從 1 開始。

這是 leetcode 的第 1 個問題，難度中等。 這裡的假設是答案必須存在並且是唯一的。 乙個自然愚蠢的方法是，每次我們輪詢乙個數字時，我們都會遍歷陣列的其他元素，看看是否有任何可以匹配的元素。 但在這種情況下，在最壞的情況下可以達到時間複雜度o(n^2)。更好的方法是利用雜湊表的強大功能，通過快速查詢元素的存在與否來降低複雜性。 因此，可能的流程是這樣的：1使用雜湊表來儲存陣列的元素和下標; 2.迴圈訪問新建立的雜湊表，從第乙個元素開始，檢視是否有另乙個可以匹配的元素，直到找到它。 由於我們有雜湊表，因此該過程的第二步在最壞的情況下會很複雜o(n)

再進一步想想，第一步和第二步其實是可以組合起來的：每次有元素進來的時候，我們先看看雜湊表是否已經有匹配的元素，如果有，我們可以直接返回結果。 如果沒有，請將新元素儲存在雜湊表中。 如果你這樣想，它可能是這樣的：

num 是陣列，target 是目標值 def two sum（num， target）： 建立乙個新的 python dict 資料型別 d = {}for i in range（len（num））：if target-num[i] in d 如果匹配值已經在雜湊表中，則只需返回兩個下標 返回 i+1， d[target-num[i]] else： 以數值為鍵， 並將以下內容標記為值，以便我們可以通過數值快速找到 d[num[i]] = i + 1

這是 leetcode 的第 3 個問題，難度中等。 不難看出，這是另乙個需要我們經常判斷的問題if a is in b標題。 通常，在這種情況下，雜湊表可能會派上用場。 基本思想是，由於它是乙個子字串，我們需要有兩個指標（或標記變數）來標識子字串的開始和結束。 基本過程是我們對整個字串進行遍歷，如果在當前子字串中遇到新字元和其他重複項，我們停下來檢視當前字串的長度，與當前最長的長度相比，如果它比最長的長度長，我們更新它，否則我們繼續向下走。

def lengthoflongestsubstring(self, s): if s == ''：如果是空字串，不要費心返回 0 slist = 列表 定義乙個雜湊表來記錄字元出現的最近位置 dict = {} 記錄最大長度 len = 0 記錄每個子字串的起始下標 start = 0 for i in range（len（slist））： 遍歷所有字串 if slist[i] in dict： 當前角色至少出現過一次。但是，如果它不在當前字串中，請不要在意，如果它在當前字串中 將當前子字串的長度與最大 len 進行比較，其長度為 if（dict[slist[i]] = start）： max len = max（max len， i-start） 重置新子字串的開頭 請注意，這裡不能將其設定為 i+1， 但應該是 dict[slist[i]]+1，為什麼？start = dict[slist[i]]+1 如果不存在，則記錄 dict[slist[i]] = i max len = max（max len，len（slist）-start） return max len