在之前我們已經(jīng)學過了二分查找和簡單查找抡草，我們知道二分查找的運行時間為O(㏒ n)， 簡單查找的運行時間為O(n)。除此之外锅知，還有沒有更快的查找算法呢？
可能有人會說數(shù)組的查找速度更快脓钾，查找速度為O(1)售睹。沒錯，但是我們今天講的是一種進化版的類似于數(shù)組的數(shù)據(jù)結(jié)構(gòu)--散列表可训。
散列表的性能取決于散列函數(shù)昌妹，那什么是散列函數(shù)呢？
散列函數(shù)
散列函數(shù)是這樣的函數(shù)握截，即無論你給它什么數(shù)據(jù)飞崖，它都還你一個數(shù)字。專業(yè)術語來描述就是：將輸入映射到數(shù)字川蒙。
散列函數(shù)需要滿足一些要求：
它必須是一致性的蚜厉，就是同樣的輸入必須映射到相同的數(shù)字。
它應該將不同的輸入映射到不同的數(shù)字畜眨。但絕大多數(shù)情況是達不到這種要求的，這就產(chǎn)生了沖突术瓮。關于沖突的介紹康聂，后面再講。
散列函數(shù)和數(shù)組結(jié)合在一起就創(chuàng)建了一種名為散列表的數(shù)據(jù)結(jié)構(gòu)胞四。散列表是一種包含額外邏輯的數(shù)據(jù)結(jié)構(gòu)恬汁。數(shù)組和鏈表都被直接映射到內(nèi)存，但散列表更復雜辜伟，它使用散列函數(shù)來確定元素的存儲位置氓侧。
幾乎每種語言都提供了散列表的實現(xiàn)方式。Python提供的散列表實現(xiàn)為字典导狡，我們可以使用函數(shù)dict()來創(chuàng)建散列表约巷。
>>> book = dict()
對了， Python還提供另一種創(chuàng)建散列表的快捷方式--使用大括號
>>> book = {}
以上兩種方式是等效的旱捧。
現(xiàn)在創(chuàng)建了散列表后独郎，在其中添加一些商品的價格。
>>> book = dict()
>>> book["apple"] = 8
>>> book["banana"] = 5
>>> book["milk"] = 4
>>> print(book)
{'apple': 8, 'banana': 5, 'milk': 4}
現(xiàn)在我們來查詢香蕉的價格：
>>> print (book["banana"])
5
這就實現(xiàn)了一個簡單的散列表枚赡。
散列表由鍵和值組成氓癌，散列函數(shù)將鍵映射到值。在Python中使用字典來實現(xiàn)散列表贫橙，如果對字典不太熟悉的同學贪婉，可以看我以前關于字典的文章：Python基礎學習-字典
散列表的應用
將散列表用于查找
散列表被用于大海撈針式的查找。當我們訪問一個網(wǎng)站的時候卢肃，我們輸入類似于：www.baidu.com這樣的域名疲迂，然后通過DNS解析到一個IP地址才顿。這里將網(wǎng)站地址映射到IP地址，就是運用了散列表的功能鬼譬。
將散列表用作緩存
緩存是一種常用了加速方式娜膘，它可以使用我們?yōu)g覽網(wǎng)站更加快速，所有的大型網(wǎng)站都使用緩存优质，而緩存的數(shù)據(jù)則是存儲在散列表中的竣贪。其基本原理是將頁面url映射到頁面數(shù)據(jù)。
沖突
由于大多數(shù)語言都提供了散列表的實現(xiàn)方式巩螃，所以我們可以不必深究散列表的內(nèi)部實現(xiàn)原理演怎，但我們必須要考慮散列表的性能。
關于散列表的性能我們首先要了解一個名為沖突的概念避乏。理想的情況是散列函數(shù)總將不同的輸入映射到數(shù)組的不同位置爷耀，但實際上，幾乎沒有這樣的散列函數(shù)拍皮。我們來看一個示例歹叮，假設有一個數(shù)組，它包含了26個位置：
使用的散列函數(shù)非常簡單铆帽，它按照字母表順序分配數(shù)組的位置咆耿。先將蘋果的價格存儲到散列表中，分配給第一個位置：
接下來將香蕉的價格存儲到散列表中爹橱，分配給第二個位置：
接下來再將杏仁的價格存儲在散列表中萨螺，由于杏仁的英文單詞為apricot，分配給它的又是第一個位置：
但是這個位置已經(jīng)存儲了蘋果的價格愧驱，怎么辦慰技？這種情況被稱為沖突：給兩個鍵分配了相同的位置。
處理沖突的方式有很多组砚，最簡單的一種就是在發(fā)生沖突的位置存儲一個鏈表：
所以吻商，一個好的散列函數(shù)對于散列表的性能尤其重要。
性能
在平均情況下惫确，散列表執(zhí)行各項操作的時間都為O(1)手报。O(1)被稱為常量時間。
簡單查找的運行時間為線性時間：
二分查找的所需時間為對數(shù)時間：
在散列表中查找所花費的時間為常量時間：
在最糟情況下改化，散列表所有的操作的運行時間都為O(n)--線性時間掩蛤。下面將散列表同數(shù)組和鏈表比較一下：
為了避免沖突，需要有：
較低的填裝因子
良好的散列函數(shù)
填裝因子
散列表的填裝因子很容易計算：
填裝因子越低陈肛，發(fā)生沖突的可能性越小揍鸟，散列表的性能越高，一個不錯的經(jīng)驗是：一旦填裝因子大于0.7，就調(diào)整散列表的長度阳藻。
良好的散列函數(shù)
良好的散列函數(shù)可以使數(shù)組中的值呈均勻分布晰奖。什么樣散列函數(shù)是良好的呢，有興趣的話腥泥，可以去研究一下SHA函數(shù)匾南。這里不做介紹，因為我也不懂~
小結(jié)
在Python中使用字典來實現(xiàn)散列表
散列表的查找蛔外、插入和刪除都很快
散列表適合于模擬映射關系
散列表可用于緩存數(shù)據(jù)
一旦填裝因子超過0.7蛆楞，就該調(diào)整散列表的長度
每天學習一點點，每天進步一點點夹厌。
