|
原来自己写了个hashmap存储，写了一半查资料的时候看到python的字典dict本身就是hashmap，就直接用字典去存了这千万的数据，吧嗒吧嗒代码写完了，处理流程也写完了。跑了一下，从2个多G的文件中加载五六分钟加载完，查询平均每4秒左右才查到，这。。。。 搜了下python字典的使用，有上千万的应用的例子，用的是整型的key，看起来查询效率是O(1)，哪里的问题造成我的字典查询这么慢，hash冲突？提前分配了1千万的桶貌似没效果，多少冲突才会造成4秒左右查一次，感觉至少一个桶里link了几十上百万的冲突点才会这么慢，我用的key都是等长、长度32的字符串，key的长度不知影不影响查询效率，也就hash的时候太长的字符串会慢一点点不是主要原因，hash完了也是等长的key。那就是这些等长的字符串hash之后会有很多的冲突，这是很可能的，毕竟dict的key自身没有限制，字符串规律越明显冲突越多。 先记下这些大概思路和准备的解决办法，着急用，另外由于这个方法多进程运行也不适合，太占内存，用redis来代替字典，省下了n-1个进程的内存，有时间再具体分析这个现象的原因： 1、分节点，先排序或者先写个脚本给1千万的key分下类，最终结果都是分成每1w一个节点，然后这些节点再生产一个节点key，先查节点key，再查1w的key 2、重写字典的hash函数，根据自身的key的规则写hash函数，或者重新实现一个dict。 3、还是分节点把1000个节点key加载到内存，1w的内容写文件，查文件，这个方法不用考虑内存占用。 这些方法都不适合我的应用，我用的文件是加密的，每次查询的时候还得解密节点文件，也挺耗时，所以还必须把1kw的数据解密后加载到内存里，其他处理模块属于多进程结构，所以多线程也不能用。单个进程占10个G内存，redis也是10个G。redis里存的也是明文，而且redis密码都是明文配置，需要做一些安全配置，再对插入和取出的数据加解密也不算慢，可以接受。 但问题的原因还是要分析的
***************************解决问题分割线******************************
今天有空解决下这个问题：
#!/usr/bin/env python
import time
fileDict = {}
#此方法有缺陷，解决了4、5秒查询一次的问题，却未解决hash冲突问题，而是使用其他hash函数先hash出int的key
#这样的话即使发生冲突了也不知道，我随机测了一下没有出现重复的，说明这个hash函数比较适合我的字符串规则。
#可以参考此种方法实现自己的hashmap add，del，find，iterator方法，而不使用字典
#不知道python是否可以实现类似c++的重载，可以的话直接重载dict的hash就可以了
============================第一次解决问题分割线=======================================
#再来看这个问题，否定了之前有冲突的疑问，由于我是python新手，刚用python，基本都是现拿来用的
#回头再详细总结一下这次问题学习到的相关python知识
#是由于class中__eq__的使用，还有dict比较的不仅仅是hash值还有key本身
#同一个class的两个对象a和b，如果他们都是同一个字符串，那么python默认比较的是内存地址，也就是指针，是不相等的，所以这里要重写__eq__来实现比较真正的key包含的字符串，类似于c++重载==，可以给class添加多个属性值，一一比较或只比较id
#所以这里不存在第一次解决问题时候提出的缺陷
class zstring:
def __eq__(self,other):
if self.value == other.value:
return True
return False
def __init__(self, md5string):
self.value = md5string
def __hash__(self):
hash = 0
for ch in self.value:
hash = hash*131 + ord(ch)
return hash
#hash table node
class Node():
def __init__(self, name, md5, desc, type):
self.name = name
self.md5 = md5
self.desc = desc
self.type = type
def initHashmap(filepath):
if not os.path.isfile(filepath):
print filepath + " is not vailable"
return
#file param like this: filename;md5;desc;type
global fileDict
fd = open(filepath, 'rb') #文件格式 1kw行的 name;md5;desc;type
line = fd.readline()
index = 0
while line:
index += 1
if index%10000 == 0:
print "insert count: " + str(index)
line = line.strip('\n')
line = line.strip()
if line == b'': #空白行
print "line error blank:" + str(index)
line = fd.readline()
continue
if line.startswith(b'#') == True: #注释行
print "line error #:" + str(index)
line = fd.readline()
continue
if line.count(";") >= 3:
val = (line.replace(line.split(";")[1],line.split(";")[1].lower()).replace('\r','').replace('\n','')).split(";")
node = Node(val[0], val[1], val[2], val[3])
a = zstring(node.md5)
fileDict[a] = node
line = fd.readline()
if __name__ == "__main__":
if len(sys.argv) < 2:
print "python testhashdict.py /home/fileparams.conf"
exit()
initHashmap(sys.argv[1])
while True:
instr = raw_input("input md5:")
print instr
if instr == "exit":
break
print instr
#a = zstring("a1158022c9cc1a5c37f5d44c2465ad85")
a = zstring(instr)
if fileDict.get(a):
print fileDict[a].name
print fileDict[a].md5
print fileDict[a].desc
print fileDict[a].type
else:
print "get nothing"
|