散清單
假設你在一家雜貨店上班。有顧客來買東西時，你得在一個本子上查找價格。如果本子的内容不是按字母順序排列的，你可能為查找蘋果（apple）的 價格而浏覽每一行，這需要很長時間。此時你使用的是簡單查找，如果本子的内容是按照字母順序排序的，可使用二分查找來找出蘋果的價格，你知道，二分查找的速度非常快，但是作為收銀員，在本子中查找價格是一件很痛苦的事情，哪怕本子的内容是有序的，在查找價格時，你都能感覺到顧客的怒氣。看來真的需要一名能夠記住所有商品價格的雇員，這樣你就不用查找了：問她就能馬上知道答案。
不管商品有多少，這位雇員（假設她的名字為Maggie）報出任何商品的價格的時間都為O(1)，速度比二分查找都快。
你希望查找商品價格的時間為O(1)，即你希望查找速度像Maggie那麼快，這是散列函數的用武之地。
散列函數
散列函數是這樣的函數，即無論你給它什麼資料，它都還你一個數字。
如果用專業術語來表達的話，我們會說，散列函數“将輸入映射到數字”。你可能認為散列函數輸出的數字沒有什麼規律，但其實散列函數必須滿足一些要求。
❑ 它必須是一緻的。例如，假設你輸入apple時得到的是4，那麼每次輸入apple時，得到的都必須為4。如果不是這樣，散清單将毫無用處。
❑ 它應将不同的輸入映射到不同的數字。例如，如果一個散列函數不管輸入是什麼都傳回1，它就不是好的散列函數。最理想的情況是，将不同的輸入映射到不同的數字。
散列函數将輸入映射為數字，這有何用途呢？你可使用它來打造你的“Maggie”！
為此，首先建立一個空數組。
你将在這個數組中存儲商品價格。下面來将蘋果的價格加入到這個數組中，為此，将Aapple作為輸入交給散列函數。
散列函數的輸出為3，是以我們将蘋果的價格存儲到數組的索引3處。
下面将牛奶（milk）的價格存儲到數組中。為此，将milk作為散列函數的輸入。
散列函數的輸出為0，是以我們将牛奶的價格存儲在索引0處。
不斷地重複這個過程，最終整個數組将填滿價格。
現在假設需要知道鳄梨（avocado）的價格。你無需在數組中查找，隻需将avocado作為輸入交給散列函數。
它将告訴你鳄梨的價格存儲在索引4處。果然，你在那裡找到了。
散列函數準确地指出了價格的存儲位置，你根本不用查找！之是以能夠這樣，具體原因如下。
❑散列函數總是将同樣的輸入映射到相同的索引。每次你輸入avocado，得到的都是同一個數字，是以，你可首先使用它來确定将鳄梨的價格存儲在什麼地方，并在以後使用它來确定鳄梨的價格存儲在什麼地方。
❑ 散列函數将不同的輸入映射到不同的索引。avocado映射到索引4, milk映射到索引0。每種商品都映射到數組的不同位置，讓你能夠将其價格存儲到這裡。
❑ 散列函數知道數組有多大，隻傳回有效的索引。如果數組包含5個元素，散列函數就不會傳回無效索引100。
剛才你就打造了一個“Maggie”！你結合使用散列函數和數組建立了一種被稱為散清單（hashtable）的資料結構，散清單由鍵和值組成。
應用案例
将散清單用于查找
手機都内置了友善的電話簿，其中每個姓名都有對應的電話号碼。
假設你要建立一個類似這樣的電話簿，将姓名映射到電話号碼。該電話簿需要提供如下功能。
❑ 添加聯系人及其電話号碼。
❑ 通過輸入聯系人來獲悉其電話号碼。這非常适合使用散清單來實作！在下述情況下，使用散清單是很不錯的選擇。
❑ 建立映射。
❑ 查找。
建立電話簿非常容易。首先，建立一個散清單。
順便說一句，Python提供了一種建立散清單的快捷方式——使用一對大括号。
下面在這個電話簿中添加一些聯系人的電話号碼。
這就成了！現在，假設你要查找Jenny的電話号碼，為此隻需向散清單傳入相應的鍵。
防止重複
假設你負責管理一個投票站。顯然，每人隻能投一票，但如何避免重複投票呢？有人來投票時，你詢問他的全名，并将其與已投票者名單進行比對。
如果名字在名單中，就說明這個人投過票了，是以将他拒之門外！否則，就将他的姓名加入到名單中，并讓他投票。現在假設有很多人來投過了票，是以名單非常長。
每次有人來投票時，你都得浏覽這個長長的名單，以确定他是否投過票。但有一種更好的辦法，那就是使用散清單！
為此，首先建立一個散清單，用于記錄已投票的人。
有人來投票時，檢查他是否在散清單中。
如果“tom”在散清單中，函數get将傳回它；否則傳回None。你可使用這個函數檢查來投票的人是否投過票！
将散清單用作緩存
來看最後一個應用案例：緩存。如果你在網站工作，可能聽說過進行緩存是一種不錯的做法。下面簡要地介紹其中的原理。假設你通路網站facebook.com。
(1) 你向Facebook的伺服器送出請求。
(2) 伺服器做些處理，生成一個網頁并将其發送給你。
(3) 你獲得一個網頁。
例如，Facebook的伺服器可能搜集你朋友的最近活動，以便向你顯示這些資訊，這需要幾秒鐘的時間。作為使用者的你，可能感覺這幾秒鐘很久，進而可能認為Facebook怎麼這麼慢！另一方面，Facebook的伺服器必須為數以百萬的使用者提供服務，每個人的幾秒鐘累積起來就相當多了。為服務好所有使用者，Facebook的伺服器實際上在很努力地工作。有沒有辦法讓Facebook的伺服器少做些工作，進而提高Facebook網站的通路速度呢？
假設你有個侄女，總是沒完沒了地問你有關星球的問題。火星離地球多遠？月球呢？木星呢？每次你都得在Google搜尋，再告訴她答案。這需要幾分鐘。現在假設她老問你月球離地球多遠，很快你就記住了月球離地球238900英裡。是以不必再去Google搜尋，你就可以直接告訴她答案。這就是緩存的工作原理：網站将資料記住，而不再重新計算。
這就是緩存，具有如下兩個優點。
❑ 使用者能夠更快地看到網頁，就像你記住了月球與地球之間的距離時一樣。下次你侄女再問你時，你就不用再使用Google搜尋，立刻就可以告訴她答案。
❑ Facebook需要做的工作更少。
緩存是一種常用的加速方式，所有大型網站都使用緩存，而緩存的資料則存儲在散清單中！
小結：
❑ 模拟映射關系；
❑ 防止重複；
❑ 緩存/記住資料，以免伺服器再通過處理來生成它們。
沖突
所謂沖突即：給兩個鍵配置設定的位置相同。
舉個栗子：假設你有一個數組，它包含26個位置。
而你使用的散列函數非常簡單，它被字母順序配置設定數組的位置。
你可能已經看出了問題。如果你要将蘋果的幾個存儲到散清單中，配置設定給你的是第一個位置。
接下來，你要将香蕉的價格存儲到散清單中，配置設定給你的是第二個位置。
一切順利！但現在你要将鳄梨的價格存儲到散清單中，配置設定給你的又是第一個位置。
不好，這個位置已經存儲了蘋果的價格！怎麼辦？這種情況就被稱為沖突！這是個問題。如果你将鳄梨的價格存儲到這個位置，将覆寫蘋果的價格，以後再查詢蘋果的價格時，得到的是鳄梨的價格！沖突很糟糕，必須要避免。處理沖突的方式很多，最簡單的方式如下：如果兩個鍵映射到了同一個位置，就在這個位置存儲一個連結清單。
在這個例子中，apple和avocado映射到了同一個位置，是以在這個位置存儲一個連結清單。在需要查詢香蕉的價格時，速度依然很快。但在需要查詢蘋果的價格時，速度要慢些：你必須在相應的連結清單中找到apple。如果這個連結清單很短，也沒什麼大不了——隻需搜尋三四個元素。但是，假設你工作的雜貨店隻銷售名稱以字母A打頭的商品。
等等！除第一個位置外，整個散清單都是空的，而第一個位置包含一個很長的清單！換言之，這個散清單中的所有元素都在這個連結清單中，這與一開始就将所有元素存儲到一個連結清單中一樣糟糕：散清單的速度會很慢。
這裡的經驗教訓有兩個。
❑ 散列函數很重要。前面的散列函數将所有的鍵都映射到一個位置，而最理想的情況是，散列函數将鍵均勻地映射到散清單的不同位置。
❑ 如果散清單存儲的連結清單很長，散清單的速度将急劇下降。然而，如果使用的散列函數很好，這些連結清單就不會很長！
填裝因子
散清單的梯安裝因子很容易計算
散清單使用數組來存儲資料，是以你需要計算數組中被占用的位置數。例如，下述散清單的填裝因子為2/5，即0.4。
填裝因子大于1意味着商品數量超過了數組的位置數。一旦填裝因子開始增大，你就需要在散清單中添加位置，這被稱為調整長度（resizing）。例如，假設有一個像下面這樣相當滿的散清單。
你就需要調整它的長度。為此，你首先建立一個更長的新數組：通常将數組增長一倍。
接下來，你需要使用函數Hash将所有的元素都插入到這個全新的散清單中。
這個新散清單的填裝因子為3/8，比原來低多了！填裝因子越低，發生沖突的可能性就越小，散清單的性能越高，一個不錯的經驗規則是：一旦填裝因子大于0.7，就調整散清單的長度。
良好的散列函數讓數組中的值呈均勻分布。
糟糕的散列函數讓值紮堆，導緻大量的沖突。
散列函數的結果必須是均勻分布的，這很重要。它們的映射範圍必須盡可能大。最糟糕的散列函數莫過于将所有輸入都映射到散清單的同一個位置。
總結：
❑ 你可以結合散列函數和數組來建立散清單。
❑ 沖突很糟糕，你應使用可以最大限度減少沖突的散列函數。
❑ 散清單的查找、插入和删除速度都非常快。
❑ 散清單适合用于模拟映射關系。
❑ 一旦填裝因子超過0.7，就該調整散清單的長度。
❑ 散清單可用于緩存資料（例如，在Web伺服器上）。
❑ 散清單非常适合用于防止重複。