Python检测是否已有数据

Question

现在的实现是一个字典类型，拥有500万条数据，KEY是40位的Hash做的是从里面确定某个Hash是否存在，但是这样的方法内存占用太多了准备尝试bloomfilter替换但是感觉增加数据有点麻烦，是否有其他类似的算法可以用？====另一种介绍===每次拿到一个HASH在列表中寻找，如果有，则停止执行，如果没有，则将该HASH添加到列表，继续重复执行。问题在：内存/效率

Answer 1

因为hash40位，是１６进制数的，我将字母替换为数字，然后转化为数字来存，这样应该可以省内存，效率应该会比较O(n)低。
我的代码:
#!/usr/bin/envpython
#-*-coding:utf-8-*-
SHIFT=5#如果计算机为32位,SHIFT为5;如果计算机为64位,SHIFT为6
MASK=0x1F#如果计算机为32位,MASK为0x1F;如果计算机为64位,MASK为0x3F
classBitBucket(object):
def__init__(self):
self._unique_key_count=0#唯一的key有多少个
self._total_key_count=0#加入的key有多少个
self._bit={}
self._map={'a':'1','b':'2','c':'3','d':'4','e':'5','f':'6'}
defset(self,value):
"""returnlastbit"""
value=self._translate(value)
self._total_key_count+=1
ifnotself._has_key(value):
self._unique_key_count+=1
key=value>>SHIFT
self._bit[key]=self._bit.get(key,0)|(1<<(value&MASK))
return0
return1
defexist(self,value):
value=self._translate(value)
ifself._has_key(value):
returnTrue
returnFalse
defclear(self,value):
value=self._translate(value)
ifself._has_key(value):
self._unique_key_count-=1
self._total_key_count-=1
key=value>>SHIFT
self._bit[key]=self._bit[key]&(~(1<<(value&MASK)))
returnTrue
returnFalse
defget_total_count(self):
returnself._total_key_count
defget_bit_count(self):
returnself._unique_key_count
def_has_key(self,value):
key=value>>SHIFT
returnself._bit.get(key,0)&(1<<(value&MASK))
def_translate(self,value):
value=value.lower()
returnlong(''.join([self._map.get(c,c)forcinvalue]))
if__name__=='__main__':
bitBucket=BitBucket()
bitBucket.set("a"*40)
printbitBucket.exist("a"*40)
printbitBucket.exist("b"*40)
bitBucket.clear("a"*40)
importhashlib
foriinrange(1,27):
a=chr(i)
sha1=hashlib.sha1()
sha1.update(a)
bitBucket.set(sha1.hexdigest())
printbitBucket.get_total_count()
printbitBucket.get_bit_count()
count=0
foriinrange(1,30):
a=chr(i)
sha1=hashlib.sha1()
sha1.update(a)
ifbitBucket.exist(sha1.hexdigest()):
count+=1
assertcount==bitBucket.get_bit_count()
或者可以考虑用字典树来做，用C++来做最好不过了，效率和内存但可以提高！