Set去重原理

在上篇文章《哈希值和可变性Hash value and mutability》最后说到set去重问题，所以这篇主要是通过实践来研究一下set去重背后的故事，当然也是参考了网上一些资料得到了一些启发，感谢那些陌生的喜欢分享的博友们。

set的简单应用 利用set中元素的唯一性，我们可以对list去重

list1 = [1,2,3,1,2,3] print(set(list1)) # output: {1, 2, 3}

set去重的原理

set中元素的hash值不一样 class Person: def __init__(self, name, identityId): self.name = name self.identityId = identityId def __hash__(self): print("%s call hash method"%self.name) return hash(id(self)) def __eq__(self, other): print("%s call eq method"%self.name) if self.__dict__ == other.__dict__: return True else: return False p1 = Person('p1', 123456789) p2 = Person('p2', 123456789) print("p1 id: %s"%hex(id(p1))) print("p2 id: %s"%hex(id(p2))) list_test = [p1,p2] print(set(list_test))

可以看出set调用了元素的hash方法，p1和p2的hash返回不同，就认为是不重复的元素，所以不去重

#output: p1 id: 0x209563fabe0 p2 id: 0x209563fa910 p1 call hash method p2 call hash method {<__main__.Person object at 0x00000209563FABE0>, <__main__.Person object at 0x00000209563FA910>} set中元素的hash返回值是一样的 class Person: def __init__(self, instance, name, identityId): self.instance = instance self.name = name self.identityId = identityId def __hash__(self): print("%s call hash method"%self.instance) return hash(self.identityId) def __eq__(self, other): print(f"{self.instance} call eq method: equal to {other.instance}") if self.name == other.name: return True else: return False p1 = Person('p1','kelly', 123456789) p2 = Person('p2','xia', 123456789) p3 = Person('p3','peter', 111111111) p4 = Person('p4','kelly', 123456789) p5 = Person('p5','kelly.xia', 123456789) print("p1 id: %s"%hex(id(p1))) print("p2 id: %s"%hex(id(p2))) print("p3 id: %s"%hex(id(p3))) print("p4 id: %s"%hex(id(p4))) print("p5 id: %s"%hex(id(p5))) print(f"p1==p4:{p1==p4}") list_test = [p1,p2,p3,p4,p5] print(set(list_test))

p1,p2,p3,p4,p5，通过id来看是指向不同的引用的，p1和p2的hash返回值相同，所以再调用p1的eq方法，eq返回是False的，所以认为p1和p2是不重复的。而p1和p4，hash返回值是一样的，再用户p1的eq方法，返回是Ture，所以认为p1和p4是重复的，将除去p4.最后的p5，跟p1，p2的hash返回值都是一样的，所以再分别调用p1和p2的eq方法，因为eq访求返回都为False，所以认为p5分别和p1，p2是不重复的。

#output： p1 id: 0x209564e1fd0 p2 id: 0x209564e1070 p3 id: 0x209564e1ac0 p4 id: 0x209564e1430 p5 id: 0x209564e1c40 p1 call eq method: equal to p4 p1==p4:True p1 call hash method p2 call hash method p1 call eq method: equal to p2 p3 call hash method p4 call hash method p1 call eq method: equal to p4 p5 call hash method p1 call eq method: equal to p5 p2 call eq method: equal to p5 {<__main__.Person object at 0x00000209564E1070>, <__main__.Person object at 0x00000209564E1FD0>, <__main__.Person object at 0x00000209564E1C40>, <__main__.Person object at 0x00000209564E1AC0>}

结论 由以上得出结论：set的去重是通过两个函数__hash__和__eq__结合实现的。当两个对象的哈希值不相同时，就认为这两个对象是不同的; 当两个对象的哈希值一样时，调用__eq__方法，当返回值为True时认为这两个对象是重复的，应该去除一个。返回FALSE时，认为这两个对象不是重复的，所以不去重。

应用 利用set去重特性，我们扩展思维应用到许多需要去重的场景中去，关键就是override超类Object的__hash__和__eq__方法。