set() 去重原理

悠悠 2022-01-15 14:57 340阅读 0赞

### 文章目录 ###

*   *  起步
     *  自定义的数据结构
     *  \_\_eq\_\_函数
     *  \_\_hash\_\_函数
     *  去重原理

## 起步 ##

众所周知，set() 是 Python 中的"天然去重因子"。对一串数据如：**lyst = \[1, 1, 2, 4, 4\]**，我们常常 set 一下，也就是：`set(lyst)`，达到去重目的。

那么，set() 是如何去重的呢？

## 自定义的数据结构 ##

为了贴合实际的开发需求，我们常需要自定义数据结构。拿通用示例 Student 来说。

class Student(object):
        def __init__(self, name, age, sid):
            self.name = name
            self.age = age
            self.sid = sid

现在，我们实例两个 Student 对象，分别是 stu1 和 stu2，其名字 name，年龄 age，学号 sid 相同。现实生活中，可以认为这两个学生是同一人。

stu1 = Student("zhong", 15, 11198)
    stu2 = Student("zhong", 15, 11198)
    
    print(set([stu1, stu2]))
    # 输出：{<__main__.Student object at 0x0030FE10>, <__main__.Student object at 0x0030FAD0>}

然而 set() 并不这样认为，因此没有实现去重效果。

## \_\_eq\_\_函数 ##

事实上，我们用比较操作符 `==` 会发现，Python 解释器认为 stu1 并不等于 stu2。

print(stu1 == stu2)  # 输出：False

会有上述现象，是因为程序没有按照现实需求运行。现实需求是：如果名字、年龄、学号都相同，那一定就是同一个人，因而我们需要重写魔法方法 `__eq__()`。代码如下所示：

class Student(object):
        def __init__(self, name, age, sid):
            self.name = name
            self.age = age
            self.sid = sid
    
        def __eq__(self, other):
            return self.name == other.name and \
                   self.age == other.age and \
                   self.sid == other.sid
    
    stu1 = Student("zhong", 15, 11198)
    stu2 = Student("zhong", 15, 11198)
    print(stu1 == stu2)  # 输出：True

现在我们是不是可以用 set 去重了呢？

print(set([stu1, stu2]))
    ---------------------------------
    Traceback (most recent call last):
      File "xxxxxxxxx", line 18, in <module>
        print(set([stu1, stu2]))
    TypeError: unhashable type: 'Student'

很遗憾，解释器报错了。它说 Student 类型的对象不能哈希。

## \_\_hash\_\_函数 ##

当我们没有为 Student 添加 `__eq__()` 函数时，set() 还不会报错，现在却说不能哈希？好在，我们可以重写 `__hash__()` 方法，改变原来的默认的哈希处理逻辑。

class Student(object):
        def __init__(self, name, age, sid):
            self.name = name
            self.age = age
            self.sid = sid
    
        def __eq__(self, other):
            return self.name == other.name and \
                   self.age == other.age and \
                   self.sid == other.sid
    
        def __hash__(self):
            return hash((self.name, self.age, self.sid))
    
    stu1 = Student("zhong", 15, 11198)
    stu2 = Student("zhong", 15, 11198)
    print(set([stu1, stu2]))
    # 输出：{<__main__.Student object at 0x0030FE10>}

为方便起见，这里借助了 tuple 的不可变特性，使其能够正确通过哈希处理。此时我们再用 set() 去重，发现成功了！

倘若在上述代码的基础上，试图把 eq 函数去掉，你会发现 set() 去重失效了。尽管它们的哈希结果相同。

class Student(object):
        def __init__(self, name, age, sid):
            self.name = name
            self.age = age
            self.sid = sid
    
        def __hash__(self):
            return hash((self.name, self.age, self.sid))
    
    stu1 = Student("zhong", 15, 11198)
    stu2 = Student("zhong", 15, 11198)
    print(set([stu1, stu2]))  # 输出：{<__main__.Student object at 0x00A9FAD0>, <__main__.Student object at 0x00A9FE10>}
    print(hash(stu1) == hash(stu2))  # 输出： True

## 去重原理 ##

经过前面一步步推导，我们也得出了 set() 去重原理：

1.  set() 函数中会先调用对象的 `__hash__()` 方法，获取 hash 结果；
2.  如果 hash 结果相同，用比较操作符 `==` （也就是调用函数 `__eq__()`）判断二者的值是否相等；
3.  如果都相等，去重；否则，set() 认为二者不同，两个都保留到结果中。