python之hash去重

• 众所周知python可以很方便的使用set去重，可用于爬取URL避免重复爬取相同的链接，如下

l=[1,1,2,3,5,5]print(set(l))

{1, 2, 3, 5}

• 那么set是如何实现去重的呢？
  • 通过散列函数对数据进行处理，即hash。
  • hash可以将数据进行加密压缩处理，使数据都固定了大小，于是比原始数据的小很多，每一个不同的数据，散列值都不相同，即不同的数字指纹。
  • 可通过判断指纹重复即可实现去重。

classMySet(object):def__init__(self, name, values):
        self.name= name
        self.values= valuesdef__hash__(self):print('hash', self.name, self.values)returnhash(self.values)

my_set= MySet('m1',1)
my_set1= MySet('m2',1)
my_set2= MySet('m3',3)print(set([my_set, my_set1, my_set2]))

• 如下所示，当使用set时，会自动调用所有对象的__hash__方法

hash m1 1
hash m2 1
hash m3 3

{<__main__.MySet object at 0x000002476656E278>, 
<__main__.MySet object at 0x000002476656E358>,
 <__main__.MySet object at 0x000002476656E320>}

• 但是还没并没有实现去重，因为还需要加入__eq__方法，如果没有重写__hash__和__eq__方法，则会默认调用这两个方法。

classMySet(object):def__init__(self, name, values):
        self.name= name
        self.values= valuesdef__hash__(self):print('hash', self.name,hash(self.values))returnhash(self.values)def__eq__(self, other):print('对比hash值：', self.__dict__['name'], other.__dict__['name'])ifisinstance(other, self.__class__):return other.__hash__()== self.__hash__()returnFalse


my_set= MySet('m1','1')
my_set1= MySet('m2','2')
my_set2= MySet('m3','3')
my_set3= MySet('m4','1')print(set([my_set, my_set1, my_set2, my_set3]))

• 如下所示，在没有使用集合之前，都没有调用hash方法，使用集合之后，才开始调用__hash__方法，然后遍历对象进行hash，当hash的过程中出现重复的指纹时，才会调用__eq__方法。可以看到m1 m3 判断之后又进行hash了一次，最后才hash了m4

使用集合去重：
hash m1 371345545330485801
hash m2 -7717153669321315512
hash m3 371345545330485801
对比hash值： m1 m3
hash m3 371345545330485801
hash m1 371345545330485801
hash m4 6432170882297048919
{<__main__.MySet object at 0x000001BB4DC1E3C8>, 
<__main__.MySet object at 0x000001BB4DC1E390>, 
<__main__.MySet object at 0x000001BB4DC1E438>}

• 在爬虫中可以使用redis保存url，但是爬取的url太多的话占用的内存依旧很大，那么推荐使用布隆过滤器