python之理解搜索
1、順序查找
1.1 順序查找
當(dāng)數(shù)據(jù)項(xiàng)存儲在諸如列表的集合中，我們說它們有線性和順序關(guān)系。每個(gè)數(shù)據(jù)項(xiàng)都存儲在相對其它數(shù)據(jù)項(xiàng)的位置。python列表中，這些相對位置是單個(gè)項(xiàng)的索引值。這些索引值是有序的，我們可以按照順序來訪問它們。即順序查找。
從列表的第一個(gè)項(xiàng)開始，我們按照基本的順序排序，簡單地從一個(gè)項(xiàng)移動(dòng)到另一個(gè)項(xiàng)，直到找到我們正在尋找的項(xiàng)或遍歷完整個(gè)列表找不到要尋找的項(xiàng)。
代碼如下：
def senquential_search(search):
origin_list = [1, 2, 4, 5, 6]
list_length = len(origin_list)
i = 0
found = False
while i < list_length and not found:
if origin_list[i] == search:
found = True
else:
i = i+1
if found:
print('found the search data %d and its index is %d' % (search, i))
else:
print('the search data %d not found' % search)
結(jié)果：
found the search data 4 and its index is 2
the search data 7 not found
1.2 順序查找分析
首先，項(xiàng)在列表任何位置的概率都是一樣的。然后查找某一項(xiàng)是否存在的唯一方法就是將其與每個(gè)項(xiàng)進(jìn)行比較。能找到的話，三種情況：最好開頭找到、其次中間找到、最差末尾找到。
平均下來計(jì)算的話，我們會(huì)在列表的中間找到該項(xiàng)，即我們將循環(huán)n/2次，當(dāng)n無限大時(shí)，那么順序查找的復(fù)雜度（大O符號）就是O(n)。
1.3 有序查找的引子
上面的假設(shè)是列表中的項(xiàng)是隨機(jī)的，沒有大小相對順序的，試想下如果列表中的項(xiàng)以某種順序排序。當(dāng)帶搜索項(xiàng)大于一定值，就停止搜索。順序查找會(huì)取得一些好的效率么。
def senquential_search(search):
origin_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
list_length = len(origin_list)
i = 0
found = stop = False
while i < list_length and not found and not stop:
if origin_list[i] == search:
found = True
else:
if origin_list[i] > search:
stop = True
else:
i = i + 1
if found:
print('found the search data %d and its index is %d' % (search, i))
else:
print('the search data %d not found' % search)
結(jié)果如下：
senquential_search(16)
senquential_search(7)
不過分析起來結(jié)果如上節(jié)，沒啥改善。不過還是為下節(jié)做準(zhǔn)備，就是有序列表以特定的方式去查找能否會(huì)取得更高的效率。
2、二分查找
2.1 二分查找
有序列表對于我們的比較是很有用的。在順序查找中，當(dāng)我們與第一個(gè)項(xiàng)進(jìn)行比較時(shí)，如果不是我們需要的，則最多還有n-1項(xiàng)去查找。
二分查找建立在一個(gè)有序列表上，如列表從小到大排序。然后它查找時(shí)從中間開始查找，如果該項(xiàng)是我們的搜索項(xiàng)，即完成了查找；如果不是，我們可以利用列表的有序性消除剩余項(xiàng)一半的元素。如果我們的搜索項(xiàng)大于中間項(xiàng)，就可以消除中間項(xiàng)及比中間項(xiàng)小的一半元素。即如果搜索項(xiàng)在列表中，它肯定在中中間項(xiàng)大的那一半元素中。最后不斷改變首尾元素的起始位置（改變中間項(xiàng)），找到搜索項(xiàng)。
def binary_search(search):
origin_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
list_length = len(origin_list)
firstpos = 0
lastpos = list_length - 1
found = False
while firstpos <= lastpos and not found:
middlepos = (firstpos + lastpos) // 2
if origin_list[middlepos] == search:
found = True
else:
if origin_list[middlepos] > search:
lastpos = middlepos-1
else:
firstpos = middlepos + 1
if found:
print('found the search data %d and its index is %d' % (search, middlepos))
else:
print('the search data %d not found' % search)
binary_search(17)
binary_search(7)
結(jié)果：
found the search data 17 and its index is 5
the search data 7 not found
2.2 二分查找中的遞歸思想
下面繼續(xù)分析之前，可以發(fā)現(xiàn)這個(gè)算法是分而治之的很好的例子。分和治意味著我們可以將問題分為更小的部分，以某種方式解決這個(gè)小部分，最后再重新組合整個(gè)問題以獲得結(jié)果。
當(dāng)我們執(zhí)行列表的二分查找時(shí)，我們首先檢索中間項(xiàng)。如果我們正在搜索的項(xiàng)小于中間項(xiàng)，我們可以簡單地對原始列表的左半部分進(jìn)行二分查找。同樣，項(xiàng)大，即右半部分二分查找。不過那種方式，都是遞歸調(diào)用二分查找函數(shù)。
def binary_search(search_list, search):
if len(search_list) == 0:
print('the search data %d not found' % search)
else:
middlepos = len(search_list) // 2
if search_list[middlepos] == search:
print('found the search data %d and its index is %d' % (search, middlepos))
else:
if search_list[middlepos] > search:
binary_search(search_list[:middlepos-1], search)
else:
binary_search(search_list[middlepos+1:], search)
結(jié)果：
binary_search([0, 1, 2, 8, 13, 17, 19, 32, 42], 17)
binary_search([0, 1, 2, 8, 13, 17, 19, 32, 42], 7)
2.3 二分查找分析
為了分析二分查找算法，我們需要先知道每個(gè)計(jì)較大約消除了一半的元素，該算法檢查整個(gè)列表的最大比較次數(shù)是多少？假如從n項(xiàng)開始，大約n/2項(xiàng)將在第一次比較后留下，然后第二次余下n/4，繼而n/8、n/16……。
當(dāng)我們拆分足夠多次后，我們最終會(huì)得到只有一個(gè)項(xiàng)的列表。這個(gè)要么是我們尋找的項(xiàng)，要么不是。達(dá)到這一點(diǎn)的比較次數(shù)是i，那么n/2^i=1時(shí)，求解出i=logn。最大比較次數(shù)相對于列表中的項(xiàng)是對象的。因此二分查找是O（logn）。
另一個(gè)分析的問題是在上面的遞歸求解的例子中：
binary_search(alist[:midpoint],item)
使用切片運(yùn)算創(chuàng)建列表的左半部分，然后傳遞到下一個(gè)調(diào)用（同樣對右半部分）。我們上面做的分析假設(shè)切片操作符是恒定時(shí)間的。然而，我們知道python中的slice運(yùn)算符實(shí)際上是O（k）。這意味著使用slice的二分查找將不會(huì)在嚴(yán)格的對數(shù)時(shí)間執(zhí)行。幸運(yùn)的是，這可以通過傳遞列表聯(lián)通開始和結(jié)束的索引來糾正，如不利用遞歸實(shí)現(xiàn)的二分查找。
即使二分查找通常比順序查找更好，但更重要的需要注意，對于小的n的值，排序的額外成本可能不值得。實(shí)際中，我們應(yīng)該經(jīng)?？紤]采取額外的分類工作是否可以是搜索獲得好處。我們可以排序一次，然后進(jìn)行很多次查找，那么排序的成本就可以忽略。然后對大型的列表，排序一次的代價(jià)可能是昂貴的，從一開始就執(zhí)行順序查找可能是最好的選擇。
3、hash查找
3.1 hash查找
在之前的部分，我們已經(jīng)知道利用項(xiàng)在集合中相對彼此的位置來改進(jìn)我們的搜索算法。如一個(gè)列表是有序的，我們可以使用二分法查找在對數(shù)時(shí)間中查找。下面將繼續(xù)進(jìn)一步建立一個(gè)可以在O（1）時(shí)間內(nèi)搜索的數(shù)據(jù)結(jié)構(gòu)。這個(gè)概念被稱為hash查找。
為了做到這一點(diǎn)，當(dāng)我們在集合中查找項(xiàng)時(shí)，我們需要更多的去了解項(xiàng)可能在哪里。如果每個(gè)項(xiàng)都在該在的地方，那么搜索可以使用單個(gè)比較就能發(fā)現(xiàn)項(xiàng)的存在。然后，通常實(shí)際情況并不是這樣。
哈希表是以一種容易找到它們方式存儲項(xiàng)的集合。哈希表的每個(gè)位置，通常稱為一個(gè)槽，可以容納一個(gè)項(xiàng)，并且從0開始的整數(shù)值命名。最初哈希表不包含項(xiàng)，因此每個(gè)槽都為空。python中可以利用列表來實(shí)現(xiàn)一個(gè)哈希表，每個(gè)元素初始化為None。
項(xiàng)和該項(xiàng)在散列表中所屬的槽之間的印射被稱為hash函數(shù)。hash函數(shù)將接收集合中的任何項(xiàng)，并在槽名范圍內(nèi)（0和m-1）返回一個(gè)整數(shù)。假設(shè)我們有54,26,93,17,77和31的集合。我們的第一個(gè)hash函數(shù)稱為余數(shù)法，只需要一個(gè)項(xiàng)除以其表大小，返回剩余部分作為其散列值（h(item)=item%11)。這種余數(shù)方法（模運(yùn)算）通常以某種形式存在所有散列函數(shù)中，因此結(jié)果必須在槽名的范圍之內(nèi)。
[圖片上傳失敗...(image-a4c738-1526807077282)]
一旦計(jì)算了哈希值，我們可以將每個(gè)項(xiàng)插入到指定位置的哈希表中，如下所示。注意，11個(gè)插槽的6個(gè)已經(jīng)被占用，這被稱為負(fù)載因子，通常表示為λ=項(xiàng)數(shù)/表大小。這個(gè)例子中，λ=6/11。
現(xiàn)在當(dāng)我們要所有一個(gè)項(xiàng)時(shí)，我們只需要使用哈希函數(shù)來計(jì)算項(xiàng)的槽名稱，然后檢索哈希表以查看它是否存在。該搜索操作是O（1），因?yàn)樾枰愣ǖ臅r(shí)間量來計(jì)算散列值，然后在該位置索引散列列表。如果正確的話，我們將找到這個(gè)項(xiàng)。
然后基于以上，我們能注意到只有每個(gè)項(xiàng)印射到哈希表中的唯一位置，這種技術(shù)才會(huì)起作用。例如44和77的散列值都是0。根據(jù)散列函數(shù)，一個(gè)或更多的項(xiàng)要在同一槽中，這種現(xiàn)象被稱為碰撞（它也可以被稱為沖突）。顯然，沖突是散列技術(shù)產(chǎn)生了問題。
3.2 hash函數(shù)
給定項(xiàng)的集合，將每個(gè)項(xiàng)印射到唯一槽的散列函數(shù)被稱為完美散列函數(shù)。如果我們知道項(xiàng)和集合永遠(yuǎn)不會(huì)改變，那么可以構(gòu)造一個(gè)完美的散列函數(shù)。不幸的是，實(shí)際中給定任意項(xiàng)的集合，沒有系統(tǒng)的方法來構(gòu)建完美的散列函數(shù)，幸運(yùn)的是，我們不需要散列函數(shù)是完美的，仍舊可以提高性能。
總是有具有完美散列函數(shù)的一種方式是增加散列表的大小，是的可以容納項(xiàng)范圍中的每個(gè)可能值。這保證每個(gè)項(xiàng)將具有唯一的槽。雖然這個(gè)對于小項(xiàng)目是實(shí)用的，但是當(dāng)項(xiàng)的數(shù)目盡可能大的時(shí)候是不可行的。例如項(xiàng)是九個(gè)數(shù)字的社保號碼，那么這個(gè)方法將需要大約10億個(gè)槽，如果只是存儲幾個(gè)學(xué)生的數(shù)據(jù)，那么將浪費(fèi)大量的內(nèi)存。
我們的目標(biāo)是構(gòu)建一個(gè)散列函數(shù)，最大限度地減少?zèng)_突數(shù)，易于計(jì)算，并均勻分布在哈希表中的項(xiàng)。有很多方法擴(kuò)展簡單余數(shù)法，下面將介紹幾個(gè)。
3.2.1 分組求和法
將項(xiàng)分為相等大小的塊，最后一塊可能不是相等大小。然后將這些塊加在一起求出散列值。如我們的項(xiàng)是電話號碼 436-555-4601，我們將取出數(shù)字，并將他們分為兩位數(shù)（43,65,55,46,01）,43 + 65 + 55 + 46 + 01=210，相加為210.我們假設(shè)哈希表一共11個(gè)槽，這種情況下，210%11=1，因此電話號碼的436-555-4601散列到槽1。一些分組求和法會(huì)在求和之前每隔一個(gè)反轉(zhuǎn)，即（43,56,55,64,01），43+56+55+64+01=219，散列值為219%11=10。
3.2.2 平方取中法
先對該項(xiàng)平方，然后提取一部分?jǐn)?shù)字結(jié)果。例如項(xiàng)是44，我們將計(jì)算44^2=1936，通過提取中間兩個(gè)數(shù)字得到93，我們得到93%11=5。
3.2.3 基于字符的項(xiàng)
基于字符的項(xiàng)去創(chuàng)建散列函數(shù)同樣可以。cat可以看作是ascii值的序列。
>>> ord('c')
99
>>> ord('a')
97
>>> ord('t')
116
然后我們可以獲取這三個(gè)ascii值，將它們相加，并使用余數(shù)方法獲取散列值。
def hash(astring, tablesize):
sum = 0
for pos in range(len(astring)):
sum = sum + ord(astring[pos])
return sum%tablesize
有趣的是，當(dāng)使用次散列函數(shù)時(shí)，不同順序的字符換總會(huì)返回相同的散列值。那么我們就將字符的位置作為權(quán)重重新計(jì)算。
同樣的我們可以自己實(shí)現(xiàn)一些方法來計(jì)算集合中項(xiàng)的散列值。但是萬變不離其宗的是：哈希函數(shù)必須是搞笑的，以便它不會(huì)成為存儲和搜索過程中的主要部分。否則本末倒置了。
3.3 解決沖突
現(xiàn)在再回到碰撞的問題，當(dāng)兩個(gè)項(xiàng)散列值在同一槽時(shí)，我們必須有一個(gè)系統(tǒng)的方法將第二個(gè)項(xiàng)放在散列表中，這個(gè)過程稱之為沖突解決。如前所述，如果散列函數(shù)是完美的，沖突將永遠(yuǎn)不會(huì)發(fā)生，然而實(shí)際中，沖突解決稱為解決散列非常重要的一部分。
解決沖突的辦法一種叫做查找散列表，嘗試查找到另一個(gè)空槽以保存導(dǎo)致沖突的項(xiàng)。一個(gè)簡單的辦法就是從原始的哈希位置開始，然后以順序方式移動(dòng)槽，知道遇到第一個(gè)空槽。注意，我們也可能需要回到第一個(gè)槽（循環(huán)）以查找整個(gè)散列表。這種沖突解決過程被稱為開放尋址，因?yàn)樗噲D在散列表中找到下一個(gè)空槽或地址。通過系統(tǒng)地一次訪問每個(gè)槽，我們執(zhí)行稱為線性探測的開放尋址計(jì)數(shù)。
下面展示了在簡單余數(shù)法散列函數(shù)（54,26,93,17,77,31,44,55,20）下整數(shù)項(xiàng)的擴(kuò)展集合。當(dāng)我們嘗試將44放入槽0時(shí)，發(fā)生沖突，先線性探測下，我們卓哥順序觀察，知道找到位置。這時(shí)我們找到槽1。再次，55應(yīng)該在槽0中，但是必須放在槽2中，因?yàn)樗窍乱粋€(gè)開放位置，值20散列到槽9。由于槽9已滿，進(jìn)行線性探測，我們訪問槽10,0,1和2，最后在位置3找到一個(gè)空槽。這里依次移位尋找空槽的位置，這里很明顯看出會(huì)影響之后的項(xiàng)的插入。
一旦我們使用線性探測和開放尋址建立了哈希表，我們就必須使用相同的方法來搜索項(xiàng)。假設(shè)我們相差找93，當(dāng)我們計(jì)算哈希值時(shí)，我們得到5，查看槽5得到93，返回True。如果我們查找20，這時(shí)哈希值是9，而槽9的當(dāng)前項(xiàng)是31，我們不能簡單的返回False，因?yàn)槲覀冎揽赡艽嬖跊_突。我們被迫做一個(gè)順序搜索，從位置10開始尋找，知道我們找到項(xiàng)20或我們找到一個(gè)空槽。
線性探測的缺點(diǎn)是聚集的趨勢：項(xiàng)在表中聚集，意味著如果在相同的散列值處發(fā)生很多沖突，則將線性探測來填充多個(gè)周邊槽。這將影響正在插入的其他項(xiàng)，假如我嫩嘗試添加上面的項(xiàng)20時(shí)看到的，必須跳過一組值為0的值，最終找到開放位置。
處理聚集的一種方式是擴(kuò)展線性探測技術(shù)，使得不是順序地查找下一個(gè)開放槽，而是跳過槽，從而更均勻地分布引起沖突的項(xiàng)。這將潛在地減少發(fā)生的聚集 。如下圖所示加3探頭進(jìn)行碰撞識別時(shí)的項(xiàng)，意味著一旦發(fā)生碰撞，我們將查看之后的第三個(gè)槽，直到找到一個(gè)槽為空。
在沖突后尋找另一個(gè)槽的過程叫做重新散列。使得簡單的線性探測，rehash函數(shù)是newhashvalue=rehash(oldhashvalue)，其中rehash(pos)=(pos+1)%sizeoftbale。加3可以定義為rehash(pos)=(pos+3)$sizeoftable。一般來說為rehash(pos)=(pos + skip)％sizeoftable。重要的是，“跳過”的大小必須使得表中的所有槽最終都被訪問。否則，表的一部分將不會(huì)被使用。為了確保這一點(diǎn)，通常建議表的大小是素?cái)?shù)。
線性探測思想的另一個(gè)變種稱為二次探測。代替使用常量“跳過”值，使用rehash函數(shù)，將散列值遞增1，3，5，7，9依此類推，這意味著如果第一哈希值是h，則連續(xù)值是h+1，h+4，h+9，h+16等，換句話說，二次探測使用由連續(xù)完全正方形組成的跳躍。下圖示例：
[圖片上傳失敗...(image-58a6d9-1526807077282)]
用于沖突解決的提到方式允許每個(gè)槽保持對項(xiàng)的集合（或鏈）的引用。連接允許許多項(xiàng)存在哈希表中相同的位置。當(dāng)發(fā)生沖突時(shí)，項(xiàng)仍舊放在散列表的正確槽中。隨著越來越多的項(xiàng)放在哈希到相同的位置，搜索集合中的項(xiàng)的難度增加。如下使用鏈解決沖突。
當(dāng)我們要搜索一個(gè)項(xiàng)時(shí)，我們使用散列函數(shù)來生成它應(yīng)該在的槽，由于每個(gè)槽都有一個(gè)集合，我們使用一種搜索計(jì)數(shù)來查找該項(xiàng)是否存在。優(yōu)點(diǎn)在于平均來說，每個(gè)可能有更少的項(xiàng)，搜索可能有效。
3.4 實(shí)現(xiàn)map抽象數(shù)據(jù)類型
最有用的python集合之一是字典。字典是一種關(guān)聯(lián)數(shù)據(jù)類型，你可以在其中存儲鍵值對，該鍵用于查找關(guān)聯(lián)的值，我們經(jīng)常稱之為map。
map的抽象數(shù)據(jù)類型定義如下。該結(jié)構(gòu)是鍵值之間的管理的無序集合。map中的鍵都是唯一的，因此鍵值之間存在一對一的關(guān)系。操作如下：
- Map()：創(chuàng)建一個(gè)新的map。它返回一個(gè)空的map集合。
- put(key, value)：向map中添加一個(gè)新的鍵值對。如果鍵已經(jīng)在map中，那么新值替換舊值。
- get(key)：根據(jù)指定的鍵返回存儲的值、
- del(map[key])：刪除指定的鍵值對。
- len()：返回集合鍵值對數(shù)量。
- in ：key in map類似語句，找到返回True，否則返回False。
字典的一個(gè)很大的好處就是給定一個(gè)鍵，我們可以快速根據(jù)這個(gè)鍵去查找相關(guān)的值。為了加速這種查找能力，我們需要支持一個(gè)高效的搜索的實(shí)現(xiàn)。我們可以使用具有順序或二分查找的列表，但是如果使用上面的哈希表將更好，因?yàn)椴檎夜１淼捻?xiàng)可以接近O(1)的性能。
我們使用兩個(gè)列表來創(chuàng)建一個(gè)實(shí)現(xiàn)Map抽象數(shù)據(jù)類型的HashTable類。一個(gè)名為slots的列表將保存鍵項(xiàng)，一個(gè)名為data的并行列表將保存數(shù)據(jù)值。當(dāng)我們查找一個(gè)鍵時(shí)，data列表中相應(yīng)位置將保存相關(guān)的數(shù)據(jù)值。我們將使用前面提出的想法將鍵列表視為哈希表。這里注意哈希表的初始已被選擇為11，盡管這是任意的，但重要的是，大小是質(zhì)數(shù)，使得沖突解決的算法可以盡可能的提高。
class HachTable(object):
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
hash函數(shù)實(shí)現(xiàn)簡單的余數(shù)方法。沖突解決是加1函數(shù)的線性探測。put函數(shù)將定最終將有一個(gè)空槽，除非key已經(jīng)存在于self.slots，它計(jì)算原始哈希值，如果該槽部位空，則迭代rehash函數(shù)，直到出現(xiàn)空槽。如果非空槽已經(jīng)包含key，則舊數(shù)據(jù)替換為新數(shù)據(jù)。
def put(self, key, value):
hashvalue = self.hash_function(key)
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = value
else:
if self.slots[hashvalue] == key:
self.slots[hashvalue] = value
else:
nextslot = self.rehash(hashvalue)
while self.slots[nextslot] !=None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot)
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = value
else:
self.data[nextslot] = value
def hash_function(self, value):
return value % self.size
def rehash(self, oldhash):
return (oldhash + self.hop) % self.size
同樣get函數(shù)從計(jì)算初始哈希值開始，如果值不在槽中，那么rehash定位下一個(gè)可能的位置。搜索將通過檢索以確保我們沒有返回到初始槽來終止。如果發(fā)生這種情況，我們已用盡所有的槽，并且項(xiàng)不存在。
HashTable類提供了附加的字典功能。我們重載__getitem__和__setitem__方法以允許使用[]訪問。這意味著一旦創(chuàng)建了HashTable。索引操作符將可用。
def get(self, key):
startslot = self.hash_function(key)
data_value = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not stop and not found:
if self.slots[position] == key:
found = True
data_value = self.data[position]
else:
position = self.rehash(position)
if position == startslot:
stop = True
return data_value
def hash_function(self, value):
return value % self.size
def rehash(self, oldhash):
return (oldhash + self.hop) % self.size
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
完整數(shù)據(jù)：
class HachTable(object):
def __init__(self):
self.size = 11
self.hop = 1
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, value):
hashvalue = self.hash_function(key)
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = value
else:
if self.slots[hashvalue] == key:
self.slots[hashvalue] = value
else:
nextslot = self.rehash(hashvalue)
while self.slots[nextslot] !=None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot)
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = value
else:
self.data[nextslot] = value
def get(self, key):
startslot = self.hash_function(key)
data_value = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not stop and not found:
if self.slots[position] == key:
found = True
data_value = self.data[position]
else:
position = self.rehash(position)
if position == startslot:
stop = True
return data_value
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
def hash_function(self, value):
return value % self.size
def rehash(self, oldhash):
return (oldhash + self.hop) % self.size
H = HachTable()
H[54] = "cat"
H[26] = "dog"
H[93] = "lion"
H[17] = "tiger"
H[77] = "bird"
H[31] = "cow"
H[44] = "goat"
H[55] = "pig"
H[20] = "chicken"
print(H.slots)
print(H.data)
H.put(20, 'monkey')
print(H.data)
print(H[20])
結(jié)果為：
[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
['bird', 'goat', 'pig', 'monkey', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
monkey
3.5 hash法分析
在最好的情況下，散列將提供O(1)，恒定時(shí)間搜索。然而，由于沖突，比較的數(shù)量通常不是那么簡單。
我們需要分析散列表的使用最重要的信息是負(fù)載因子λ（λ=項(xiàng)數(shù)/表大小）。如果λ小，則碰撞的機(jī)會(huì)較低，這意味著更可能在它們所屬的槽中。如果λ大，意味著表正在填滿，則存在越來越多的沖突，這意味著解決沖突更加困難，需要更多的比較去找到一個(gè)空槽。使用鏈接，增加的碰撞意味著每個(gè)鏈上的項(xiàng)數(shù)量增加。
4、感謝
這系列將是學(xué)習(xí)交流、非原創(chuàng)。
