hash查找的是性能較好的算法之一肴捉，但它對(duì)于hash算法的設(shè)計(jì)有很大的技巧鬓长。生成hash的時(shí)候核蘸，不同的元素可能生成相同的hash值巍糯。所以減少?zèng)_突就成了很大的問(wèn)題，尤其是元素基數(shù)很大的時(shí)候客扎。
#coding:utf-8
import time
import random
def myHash(data,hashLength):
return data % hashLength
def hashSearch(hash,hashLength,data):
hashAddress = myHash(data,hashLength)
while hash.get(hashAddress) and hash[hashAddress] != data:
hashAddress += 1
hashAddress = hashAddress % hashLength
if hash.get(hashAddress) == None:
return None
return hashAddress# 數(shù)組實(shí)現(xiàn)hash映射
def toHash(num,hash,hashlength):
for i in num:
hashAdress = myHash(i,hashLength)
while hash.get(hashAdress):
hashAdress += 1 ＃防止沖突
hashAdress = hashAdress % hashlength
hash[hashAdress] = i
def sampleSearch(num,data):
for i in num:
if i == data:
return True
else:
return False
if __name__ == '__main__':
hashLength = 20
L = []
for i in range(100):
L.append(i)
L[i] += random.random()
L.append(38) #由于L中元素中全部都是隨機(jī)量,這里傳入一個(gè)整數(shù)方便查找
hash = {}
toHash(L,hash,hashLength) # 比較hash查找與普通順序查找的性能差別
start = time.clock()
result = hashSearch(hash,hashLength,38)
print 'use time %f' % (time.clock() - start)
start = time.clock()
print sampleSearch(L,38)
print 'use time %f' % (time.clock() - start)
if result:
print('hash index is ' + str(result)) # 結(jié)果為int類(lèi)型,用str函數(shù)轉(zhuǎn)為str類(lèi)型
print(hash[result])
else:
print('no result')
