散列表实现查找
本章是填补之前文章的坑，对哈希算法进行了实现，使用了平方取中法/除留余数法进行哈希映射，使用开放地址与公共溢出区解决冲突，同时对不同方法进行了性能分析对比，最后进行了总结。
可以转载，但请声明源链接：文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
Library
import pandas as pd import numpy as np import time
读取数据
df = pd.read_excel('重庆市印刷和记录媒介复制业754.xlsx') df.dropna(axis=0, how='any') # 去除非数 print("表长为：", len(df)) df.head()
表长为： 75
get_nms
def get_nums(s): ''' 逐位相加其ASCII码 ''' s = str(s) nums = 0 for s0 in s: if(s0 == '-'): continue try: nums += ord(s0) except: print("error: ",s) return nums get_nums("重庆优得利印刷有限公司")
276879
平方取中法
df['nums_电话'] = df['电话'].apply(get_nums) df['nums_电话^2'] = df['nums_电话'].apply(lambda x: np.square(x)) df['nums_企业名称'] = df['企业名称'].apply(get_nums) # df['nums_电话^4'] = df['nums_电话^2'].apply(lambda x: np.square(x)) df.head()
def get_mid(x): ''' 取中间三位数作为地址 ''' return int(x/10)%1000
df['adr_电话'] = df['nums_电话^2'].apply(get_mid) df['adr_企业名称'] = df['nums_企业名称'].apply(get_mid) df.head(100)
除留余数法
df['adr_电话_1'] = df['nums_电话^2']%1007 df['adr_企业名称_1'] = df['nums_企业名称']%1007 df.head()
创建哈希表(分别使用开发地址与公共溢出区解决冲突)
#初始化为全0 # 开放地址法所使用的hash hash_map_tele = np.zeros(32000) hash_map_name = np.zeros(8000) # 公共溢出区所使用的hash hash_map_tele_1 = np.zeros(2100) hash_map_name_1 = np.zeros(2100) len(hash_map_tele)
400000
#探测开放地址法 def create_hash_map_tele(x, adr, df_ID): try: adr = int(x[adr]) except: print('error: ', adr) while(hash_map_tele[adr] != 0): adr += 800 hash_map_tele[adr] = x[df_ID] def create_hash_map_name(x, adr, df_ID): try: adr = int(x[adr]) except: print('error: ', adr) while(hash_map_name[adr] != 0): adr += 800 hash_map_name[adr] = x[df_ID] #使用公共溢出区 count1 = 0 count2 = 0 def create_hash_map_tele1(x, adr, df_ID): global count1 if(hash_map_tele_1[x[adr]] == 0): hash_map_tele_1[x[adr]] = x[df_ID] else: hash_map_tele_1[1100 + count1] = x[df_ID] count1 += 1 def create_hash_map_name1(x, adr, df_ID): global count2 if(hash_map_name_1[x[adr]] == 0): hash_map_name_1[x[adr]] = x[df_ID] else: hash_map_name_1[1100 + count2] = x[df_ID] count2 += 1
df.apply(create_hash_map_tele, axis=1, args=('adr_电话', 'ID')) df.apply(create_hash_map_name, axis=1, args=('adr_企业名称', 'ID')) df.apply(create_hash_map_tele1, axis=1, args=('adr_电话_1', 'ID')) df.apply(create_hash_map_name1, axis=1, args=('adr_企业名称_1', 'ID')) hash_map_tele
array([0., 0., 0., ..., 0., 0., 0.])
查找流程(平方取中+开发地址探测法)-method1
# 查找 search_method = int(input("请输入你查找关键词的类型：1，电话查找；2，企业名称查找")) if(search_method == 1): tele = input("请输入你要查找对象的电话号码：") tele = int(tele) time_start = time.time() nums = get_mid(pow(get_nums(tele), 2)) print("-----base_nums-----\n",nums) print("-----hash_map_tele_value-----\n", hash_map_tele[nums]) print("-----开始查找-----") while(df['电话'][hash_map_tele[nums]] != tele): # print("-----tele-----\n", df['电话'][hash_map_tele[nums]]) nums += 800 # print('-----add_nums-----\n', nums) if(nums >= 32000): print('查找错误：无该信息') break time_end = time.time() if(nums < 32000): print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_tele[nums]]) print("---------------本次查找耗时：---------------\n",time_end-time_start) elif(search_method == 2): name = input("请输入你要查找对象的企业名称：") time_start = time.time() nums = get_mid(get_nums(name)) print("-----base_nums-----\n",nums) print("-----hash_map_tele_value-----\n", hash_map_name[nums]) print("-----开始查找-----") while(df['企业名称'][hash_map_name[nums]] != name): # print("-----tele-----\n", df['企业名称'][hash_map_name[nums]]) nums += 800 # print('-----add_nums-----\n', nums) if(nums >= 8000): print('查找错误：无该信息') break time_end = time.time() if(nums < 8000): print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_name[nums]]) print("---------------本次查找耗时：---------------\n",time_end-time_start) else: print("请选择正确的查找方式！")
-----base_nums----- 370 -----hash_map_tele_value----- 4.0 -----开始查找----- ---------------你查找的信息如下：--------------- ID 4 企业名称 吕兴华 电话 13896015224 企业地址 重庆市璧山区大路街道天星街23号 nums_电话 569 nums_电话^2 323761 adr_电话 376 nums_企业名称 63703 adr_企业名称 370 Name: 4, dtype: object ---------------查找耗时：--------------- 0.0009999275207519531
查找流程(除留余数法+公共溢出法)-method2
# 查找 search_method = int(input("请输入你查找关键词的类型：1，电话查找；2，企业名称查找")) if(search_method == 1): tele = input("请输入你要查找对象的电话号码：") tele = int(tele) time_start = time.time() nums = get_nums(tele)%1007 print("-----base_nums-----\n",nums) print("-----hash_map_tele_value-----\n", hash_map_tele_1[nums]) print("-----开始查找-----") while(df['电话'][hash_map_tele_1[nums]] != tele): # print("-----tele-----\n", df['电话'][hash_map_tele_1[nums]]) nums += 1 # print('-----add_nums-----\n', nums) if(nums >= 2100): print('查找错误：无该信息') break time_end = time.time() if(nums < 2100): print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_tele_1[nums]]) print("---------------本次查找耗时：---------------\n",time_end-time_start) elif(search_method == 2): name = input("请输入你要查找对象的企业名称：") time_start = time.time() nums = get_nums(name)%1007 print("-----base_nums-----\n",nums) print("-----hash_map_tele_value-----\n", hash_map_name_1[nums]) print("-----开始查找-----") while(df['企业名称'][hash_map_name_1[nums]] != name): # print("-----tele-----\n", df['企业名称'][hash_map_name_1[nums]]) nums += 1 # print('-----add_nums-----\n', nums) if(nums >= 2100): print('查找错误：无该信息') break time_end = time.time() if(nums < 2100): print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_name_1[nums]]) print("---------------本次查找耗时：---------------\n",time_end-time_start) else: print("请选择正确的查找方式！")
-----base_nums----- 262 -----hash_map_tele_value----- 4.0 -----开始查找----- ---------------你查找的信息如下：--------------- ID 4 企业名称 吕兴华 电话 13896015224 企业地址 重庆市璧山区大路街道天星街23号 nums_电话 569 nums_电话^2 323761 nums_企业名称 63703 adr_电话 376 adr_企业名称 370 adr_电话_1 514 adr_企业名称_1 262 Name: 4, dtype: object ---------------本次查找耗时：--------------- 0.005001544952392578
性能分析
df.head(10)
print("表长为：", len(df))
表长为： 754
32000与8000的来历
print("重复元素最多次数fen'bie为：") for i in range(500): flag = 0 for j in range(800): index = 800*i + j if(hash_map_tele[index] != 0): flag = 1 if(flag == 0): print("tele_i:", i) break for i in range(500): flag = 0 for j in range(800): index = 800*i + j if(hash_map_name[index] != 0): flag = 1 if(flag == 0): print("name_i:", i) break
tele_i: 39 name_i: 9
计算method1的ASL
c1 = 0 # 统计总的查找次数 for i in range(500): for j in range(800): index = 800*i + j if(hash_map_tele[index] != 0): c1 += (i+1) print('method1-tele-asl:', c1/754) c2 = 0 # 统计总的查找次数 for i in range(500): for j in range(800): index = 800*i + j if(hash_map_name[index] != 0): c2 += (i+1) print('method1-name-asl:', c2/754)
method1-tele-asl: 12.10079575596817 method1-name-asl: 1.6498673740053051
计算method2的ASL
df1 = df.adr_电话_1.value_counts() print(df1)
514 39 916 33 329 32 47 31 767 31 187 29 216 29 473 28 619 27 646 26 384 26 62 26 9 25 372 25 175 21 530 20 6 20 852 19 256 18 130 18 780 17 690 17 343 16 917 16 653 15 537 15 685 13 423 12 513 11 891 11 201 10 771 10 311 9 859 7 994 7 93 6 386 5 568 5 938 5 206 4 28 4 688 3 890 3 788 2 119 2 590 1 309 1 752 1 494 1 894 1 434 1 Name: adr_电话_1, dtype: int64
df2 = df.adr_企业名称_1.value_counts() print(df2)
68 6 90 5 406 5 231 4 979 4 .. 439 1 768 1 445 1 446 1 1006 1 Name: adr_企业名称_1, Length: 516, dtype: int64
print("有多少个元素在method2-tele基础表中，即只需查一次：",len(df1)) print("有多少个元素在method2-name基础表中，即只需查一次：",len(df2))
有多少个元素在method2-tele基础表中，即只需查一次： 51 有多少个元素在method2-name基础表中，即只需查一次： 516
# 基本表中的元素只需查一次，溢出区的元素和顺序表的查找次数是一样的，所以可以使用等差数列的计算公式进行计算，不过需要注意的就是溢出区的查找次数是从2开始的 print("method2-tele-asl:", (51 + (703*2 + (703*702)/2))/754) print("method2-name-asl:", (516 + (238*2 + (238*237)/2))/754)
method2-tele-asl: 329.19098143236073 method2-name-asl: 38.720159151193634
最终得出结果
- method1-tele-asl: 12.10079575596817
- method1-name-asl: 1.6498673740053051
- method2-tele-asl: 329.19098143236073
- method2-name-asl: 38.720159151193634
分析
总的来说，重复元素的个数越多，哈希查找的效率就相应越低而法1的开放地址探测法对冲突的解决在本题中查找效率是明显优于公共溢出法的，但相应的占据了更大的存储空间至于平方去中法以及除留余数法在本题中映射出来的地址重复个数基本一致，故不相上下。
