python之理解搜索
1、順序查找
1.1 順序查找
當(dāng)數(shù)據(jù)項(xiàng)存儲(chǔ)在諸如列表的集合中外傅，我們說(shuō)它們有線性和順序關(guān)系。每個(gè)數(shù)據(jù)項(xiàng)都存儲(chǔ)在相對(duì)其它數(shù)據(jù)項(xiàng)的位置。python列表中淳蔼，這些相對(duì)位置是單個(gè)項(xiàng)的索引值。這些索引值是有序的裁眯，我們可以按照順序來(lái)訪問(wèn)它們鹉梨。即順序查找。
從列表的第一個(gè)項(xiàng)開始穿稳，我們按照基本的順序排序存皂，簡(jiǎn)單地從一個(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)行比較。能找到的話疤孕，三種情況：最好開頭找到商乎、其次中間找到、最差末尾找到祭阀。
平均下來(lái)計(jì)算的話鹉戚，我們會(huì)在列表的中間找到該項(xiàng)，即我們將循環(huán)n/2次专控，當(dāng)n無(wú)限大時(shí)抹凳，那么順序查找的復(fù)雜度（大O符號(hào)）就是O(n)。
1.3 有序查找的引子
上面的假設(shè)是列表中的項(xiàng)是隨機(jī)的伦腐，沒(méi)有大小相對(duì)順序的赢底，試想下如果列表中的項(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)
不過(guò)分析起來(lái)結(jié)果如上節(jié)辩越，沒(méi)啥改善嘁扼。不過(guò)還是為下節(jié)做準(zhǔn)備，就是有序列表以特定的方式去查找能否會(huì)取得更高的效率黔攒。
2趁啸、二分查找
2.1 二分查找
有序列表對(duì)于我們的比較是很有用的。在順序查找中督惰，當(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è)算法是分而治之的很好的例子。分和治意味著我們可以將問(wèn)題分為更小的部分板祝，以某種方式解決這個(gè)小部分宫静，最后再重新組合整個(gè)問(wèn)題以獲得結(jié)果。
當(dāng)我們執(zhí)行列表的二分查找時(shí)券时，我們首先檢索中間項(xiàng)囊嘉。如果我們正在搜索的項(xiàng)小于中間項(xiàng)，我們可以簡(jiǎn)單地對(duì)原始列表的左半部分進(jìn)行二分查找革为。同樣，項(xiàng)大舵鳞，即右半部分二分查找震檩。不過(guò)那種方式，都是遞歸調(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ù)相對(duì)于列表中的項(xiàng)是對(duì)象的炭懊。因此二分查找是O（logn）。
另一個(gè)分析的問(wèn)題是在上面的遞歸求解的例子中：
binary_search(alist[:midpoint],item)
使用切片運(yùn)算創(chuàng)建列表的左半部分拂檩，然后傳遞到下一個(gè)調(diào)用（同樣對(duì)右半部分）侮腹。我們上面做的分析假設(shè)切片操作符是恒定時(shí)間的。然而广恢，我們知道python中的slice運(yùn)算符實(shí)際上是O（k）凯旋。這意味著使用slice的二分查找將不會(huì)在嚴(yán)格的對(duì)數(shù)時(shí)間執(zhí)行。幸運(yùn)的是，這可以通過(guò)傳遞列表聯(lián)通開始和結(jié)束的索引來(lái)糾正至非，如不利用遞歸實(shí)現(xiàn)的二分查找钠署。
即使二分查找通常比順序查找更好，但更重要的需要注意荒椭，對(duì)于小的n的值谐鼎，排序的額外成本可能不值得。實(shí)際中趣惠，我們應(yīng)該經(jīng)忱旯鳎考慮采取額外的分類工作是否可以是搜索獲得好處。我們可以排序一次味悄，然后進(jìn)行很多次查找草戈，那么排序的成本就可以忽略。然后對(duì)大型的列表侍瑟，排序一次的代價(jià)可能是昂貴的唐片，從一開始就執(zhí)行順序查找可能是最好的選擇。
3涨颜、hash查找
3.1 hash查找
在之前的部分费韭，我們已經(jīng)知道利用項(xiàng)在集合中相對(duì)彼此的位置來(lái)改進(jìn)我們的搜索算法。如一個(gè)列表是有序的庭瑰，我們可以使用二分法查找在對(duì)數(shù)時(shí)間中查找星持。下面將繼續(xù)進(jìn)一步建立一個(gè)可以在O（1）時(shí)間內(nèi)搜索的數(shù)據(jù)結(jié)構(gòu)。這個(gè)概念被稱為hash查找弹灭。
為了做到這一點(diǎn)督暂，當(dāng)我們?cè)诩现胁檎翼?xiàng)時(shí)，我們需要更多的去了解項(xiàng)可能在哪里穷吮。如果每個(gè)項(xiàng)都在該在的地方损痰，那么搜索可以使用單個(gè)比較就能發(fā)現(xiàn)項(xiàng)的存在。然后酒来，通常實(shí)際情況并不是這樣卢未。
哈希表是以一種容易找到它們方式存儲(chǔ)項(xiàng)的集合。哈希表的每個(gè)位置堰汉，通常稱為一個(gè)槽辽社，可以容納一個(gè)項(xiàng)，并且從0開始的整數(shù)值命名翘鸭。最初哈希表不包含項(xiàng)滴铅，因此每個(gè)槽都為空。python中可以利用列表來(lái)實(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ù)來(lái)計(jì)算項(xiàng)的槽名稱废登，然后檢索哈希表以查看它是否存在淹魄。該搜索操作是O（1），因?yàn)樾枰愣ǖ臅r(shí)間量來(lái)計(jì)算散列值堡距，然后在該位置索引散列列表甲锡。如果正確的話，我們將找到這個(gè)項(xiàng)羽戒。
然后基于以上缤沦，我們能注意到只有每個(gè)項(xiàng)印射到哈希表中的唯一位置，這種技術(shù)才會(huì)起作用易稠。例如44和77的散列值都是0缸废。根據(jù)散列函數(shù)，一個(gè)或更多的項(xiàng)要在同一槽中驶社，這種現(xiàn)象被稱為碰撞（它也可以被稱為沖突）企量。顯然，沖突是散列技術(shù)產(chǎn)生了問(wèn)題亡电。
3.2 hash函數(shù)
給定項(xiàng)的集合届巩，將每個(gè)項(xiàng)印射到唯一槽的散列函數(shù)被稱為完美散列函數(shù)。如果我們知道項(xiàng)和集合永遠(yuǎn)不會(huì)改變份乒，那么可以構(gòu)造一個(gè)完美的散列函數(shù)恕汇。不幸的是腕唧，實(shí)際中給定任意項(xiàng)的集合，沒(méi)有系統(tǒng)的方法來(lái)構(gòu)建完美的散列函數(shù)瘾英，幸運(yùn)的是枣接，我們不需要散列函數(shù)是完美的，仍舊可以提高性能方咆。
總是有具有完美散列函數(shù)的一種方式是增加散列表的大小月腋，是的可以容納項(xiàng)范圍中的每個(gè)可能值。這保證每個(gè)項(xiàng)將具有唯一的槽瓣赂。雖然這個(gè)對(duì)于小項(xiàng)目是實(shí)用的榆骚，但是當(dāng)項(xiàng)的數(shù)目盡可能大的時(shí)候是不可行的。例如項(xiàng)是九個(gè)數(shù)字的社保號(hào)碼煌集，那么這個(gè)方法將需要大約10億個(gè)槽妓肢，如果只是存儲(chǔ)幾個(gè)學(xué)生的數(shù)據(jù)，那么將浪費(fèi)大量的內(nèi)存苫纤。
我們的目標(biāo)是構(gòu)建一個(gè)散列函數(shù)碉钠，最大限度地減少?zèng)_突數(shù)，易于計(jì)算卷拘，并均勻分布在哈希表中的項(xiàng)喊废。有很多方法擴(kuò)展簡(jiǎn)單余數(shù)法，下面將介紹幾個(gè)栗弟。
3.2.1 分組求和法
將項(xiàng)分為相等大小的塊污筷，最后一塊可能不是相等大小。然后將這些塊加在一起求出散列值乍赫。如我們的項(xiàng)是電話號(hào)碼 436-555-4601瓣蛀，我們將取出數(shù)字，并將他們分為兩位數(shù)（43,65,55,46,01）,43 + 65 + 55 + 46 + 01=210雷厂，相加為210.我們假設(shè)哈希表一共11個(gè)槽惋增，這種情況下，210%11=1改鲫，因此電話號(hào)碼的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 平方取中法
先對(duì)該項(xiàng)平方讲弄，然后提取一部分?jǐn)?shù)字結(jié)果措左。例如項(xiàng)是44，我們將計(jì)算44^2=1936避除，通過(guò)提取中間兩個(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)一些方法來(lái)計(jì)算集合中項(xiàng)的散列值。但是萬(wàn)變不離其宗的是：哈希函數(shù)必須是搞笑的焙糟，以便它不會(huì)成為存儲(chǔ)和搜索過(guò)程中的主要部分口渔。否則本末倒置了。
3.3 解決沖突
現(xiàn)在再回到碰撞的問(wèn)題穿撮，當(dāng)兩個(gè)項(xiàng)散列值在同一槽時(shí)缺脉，我們必須有一個(gè)系統(tǒng)的方法將第二個(gè)項(xiàng)放在散列表中，這個(gè)過(guò)程稱之為沖突解決悦穿。如前所述攻礼，如果散列函數(shù)是完美的，沖突將永遠(yuǎn)不會(huì)發(fā)生栗柒，然而實(shí)際中礁扮，沖突解決稱為解決散列非常重要的一部分。
解決沖突的辦法一種叫做查找散列表傍衡，嘗試查找到另一個(gè)空槽以保存導(dǎo)致沖突的項(xiàng)。一個(gè)簡(jiǎn)單的辦法就是從原始的哈希位置開始负蠕，然后以順序方式移動(dòng)槽蛙埂，知道遇到第一個(gè)空槽。注意遮糖，我們也可能需要回到第一個(gè)槽（循環(huán)）以查找整個(gè)散列表绣的。這種沖突解決過(guò)程被稱為開放尋址，因?yàn)樗噲D在散列表中找到下一個(gè)空槽或地址欲账。通過(guò)系統(tǒng)地一次訪問(wèn)每個(gè)槽屡江，我們執(zhí)行稱為線性探測(cè)的開放尋址計(jì)數(shù)。
下面展示了在簡(jiǎn)單余數(shù)法散列函數(shù)（54,26,93,17,77,31,44,55,20）下整數(shù)項(xiàng)的擴(kuò)展集合赛不。當(dāng)我們嘗試將44放入槽0時(shí)惩嘉，發(fā)生沖突，先線性探測(cè)下踢故，我們卓哥順序觀察文黎，知道找到位置惹苗。這時(shí)我們找到槽1。再次耸峭，55應(yīng)該在槽0中桩蓉，但是必須放在槽2中，因?yàn)樗窍乱粋€(gè)開放位置劳闹，值20散列到槽9院究。由于槽9已滿，進(jìn)行線性探測(cè)本涕，我們?cè)L問(wèn)槽10,0,1和2业汰，最后在位置3找到一個(gè)空槽。這里依次移位尋找空槽的位置偏友，這里很明顯看出會(huì)影響之后的項(xiàng)的插入蔬胯。
一旦我們使用線性探測(cè)和開放尋址建立了哈希表，我們就必須使用相同的方法來(lái)搜索項(xiàng)位他。假設(shè)我們相差找93氛濒，當(dāng)我們計(jì)算哈希值時(shí)，我們得到5鹅髓，查看槽5得到93舞竿，返回True。如果我們查找20窿冯，這時(shí)哈希值是9骗奖，而槽9的當(dāng)前項(xiàng)是31，我們不能簡(jiǎn)單的返回False醒串，因?yàn)槲覀冎揽赡艽嬖跊_突执桌。我們被迫做一個(gè)順序搜索，從位置10開始尋找芜赌，知道我們找到項(xiàng)20或我們找到一個(gè)空槽仰挣。
線性探測(cè)的缺點(diǎn)是聚集的趨勢(shì)：項(xiàng)在表中聚集，意味著如果在相同的散列值處發(fā)生很多沖突缠沈，則將線性探測(cè)來(lái)填充多個(gè)周邊槽膘壶。這將影響正在插入的其他項(xiàng)，假如我嫩嘗試添加上面的項(xiàng)20時(shí)看到的洲愤，必須跳過(guò)一組值為0的值颓芭，最終找到開放位置。
處理聚集的一種方式是擴(kuò)展線性探測(cè)技術(shù)柬赐，使得不是順序地查找下一個(gè)開放槽亡问，而是跳過(guò)槽，從而更均勻地分布引起沖突的項(xiàng)肛宋。這將潛在地減少發(fā)生的聚集 玛界。如下圖所示加3探頭進(jìn)行碰撞識(shí)別時(shí)的項(xiàng)万矾，意味著一旦發(fā)生碰撞，我們將查看之后的第三個(gè)槽慎框，直到找到一個(gè)槽為空良狈。
在沖突后尋找另一個(gè)槽的過(guò)程叫做重新散列。使得簡(jiǎn)單的線性探測(cè)笨枯，rehash函數(shù)是newhashvalue=rehash(oldhashvalue)薪丁，其中rehash(pos)=(pos+1)%sizeoftbale。加3可以定義為rehash(pos)=(pos+3)$sizeoftable馅精。一般來(lái)說(shuō)為rehash(pos)=(pos + skip)％sizeoftable严嗜。重要的是，“跳過(guò)”的大小必須使得表中的所有槽最終都被訪問(wèn)洲敢。否則漫玄，表的一部分將不會(huì)被使用。為了確保這一點(diǎn)压彭，通常建議表的大小是素?cái)?shù)睦优。
線性探測(cè)思想的另一個(gè)變種稱為二次探測(cè)。代替使用常量“跳過(guò)”值壮不，使用rehash函數(shù)汗盘，將散列值遞增1，3询一，5隐孽，7，9依此類推健蕊，這意味著如果第一哈希值是h菱阵，則連續(xù)值是h+1，h+4缩功，h+9晴及，h+16等，換句話說(shuō)掂之，二次探測(cè)使用由連續(xù)完全正方形組成的跳躍抗俄。下圖示例：
[圖片上傳失敗...(image-58a6d9-1526807077282)]
用于沖突解決的提到方式允許每個(gè)槽保持對(duì)項(xiàng)的集合（或鏈）的引用脆丁。連接允許許多項(xiàng)存在哈希表中相同的位置世舰。當(dāng)發(fā)生沖突時(shí)，項(xiàng)仍舊放在散列表的正確槽中槽卫。隨著越來(lái)越多的項(xiàng)放在哈希到相同的位置跟压，搜索集合中的項(xiàng)的難度增加。如下使用鏈解決沖突歼培。
當(dāng)我們要搜索一個(gè)項(xiàng)時(shí)震蒋，我們使用散列函數(shù)來(lái)生成它應(yīng)該在的槽茸塞，由于每個(gè)槽都有一個(gè)集合，我們使用一種搜索計(jì)數(shù)來(lái)查找該項(xiàng)是否存在查剖。優(yōu)點(diǎn)在于平均來(lái)說(shuō)钾虐，每個(gè)可能有更少的項(xiàng)，搜索可能有效笋庄。
3.4 實(shí)現(xiàn)map抽象數(shù)據(jù)類型
最有用的python集合之一是字典效扫。字典是一種關(guān)聯(lián)數(shù)據(jù)類型，你可以在其中存儲(chǔ)鍵值對(duì)直砂，該鍵用于查找關(guān)聯(lián)的值菌仁，我們經(jīng)常稱之為map。
map的抽象數(shù)據(jù)類型定義如下静暂。該結(jié)構(gòu)是鍵值之間的管理的無(wú)序集合济丘。map中的鍵都是唯一的，因此鍵值之間存在一對(duì)一的關(guān)系洽蛀。操作如下：
- Map()：創(chuàng)建一個(gè)新的map摹迷。它返回一個(gè)空的map集合。
- put(key, value)：向map中添加一個(gè)新的鍵值對(duì)辱士。如果鍵已經(jīng)在map中泪掀，那么新值替換舊值。
- get(key)：根據(jù)指定的鍵返回存儲(chǔ)的值颂碘、
- del(map[key])：刪除指定的鍵值對(duì)异赫。
- len()：返回集合鍵值對(duì)數(shù)量。
- in ：key in map類似語(yǔ)句头岔，找到返回True塔拳，否則返回False。
字典的一個(gè)很大的好處就是給定一個(gè)鍵峡竣，我們可以快速根據(jù)這個(gè)鍵去查找相關(guān)的值靠抑。為了加速這種查找能力，我們需要支持一個(gè)高效的搜索的實(shí)現(xiàn)适掰。我們可以使用具有順序或二分查找的列表颂碧，但是如果使用上面的哈希表將更好，因?yàn)椴檎夜１淼捻?xiàng)可以接近O(1)的性能类浪。
我們使用兩個(gè)列表來(lái)創(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)簡(jiǎn)單的余數(shù)方法。沖突解決是加1函數(shù)的線性探測(cè)昔脯。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è)可能的位置。搜索將通過(guò)檢索以確保我們沒(méi)有返回到初始槽來(lái)終止崩泡。如果發(fā)生這種情況禁荒，我們已用盡所有的槽，并且項(xiàng)不存在角撞。
HashTable類提供了附加的字典功能呛伴。我們重載__getitem__和__setitem__方法以允許使用[]訪問(wèn)。這意味著一旦創(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ù)量通常不是那么簡(jiǎn)單奕锌。
我們需要分析散列表的使用最重要的信息是負(fù)載因子λ（λ=項(xiàng)數(shù)/表大小）村生。如果λ小惊暴，則碰撞的機(jī)會(huì)較低，這意味著更可能在它們所屬的槽中梆造。如果λ大缴守，意味著表正在填滿，則存在越來(lái)越多的沖突镇辉，這意味著解決沖突更加困難屡穗，需要更多的比較去找到一個(gè)空槽。使用鏈接忽肛，增加的碰撞意味著每個(gè)鏈上的項(xiàng)數(shù)量增加村砂。
4、感謝
這系列將是學(xué)習(xí)交流屹逛、非原創(chuàng)础废。
