散列查找

hash查找的是性能较好的算法之一，但它对于hash算法的设计有很大的技巧。生成hash的时候，不同的元素可能生成相同的hash值。所以减少冲突就成了很大的问题，尤其是元素基数很大的时候。

#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# 数组实现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中元素中全部都是随机量,这里传入一个整数方便查找
  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)) # 结果为int类型,用str函数转为str类型
    print(hash[result])    
  else:        
    print('no result')