面试题：Python字典：自定义哈希与高效查找

Question

假设你需要创建一个自定义类MyClass，其实例需要作为字典的键。该类有两个属性attr1和attr2，当且仅当attr1和attr2的值都相等时，两个MyClass实例应被视为相等（用于字典查找）。实现MyClass类，使其能够正确作为字典的键，同时考虑如何优化哈希函数以提高字典查找效率。阐述在设计自定义类作为字典键时，对哈希函数和__eq__方法的设计原则及相互关系。

Answer 1

class MyClass:
    def __init__(self, attr1, attr2):
        self.attr1 = attr1
        self.attr2 = attr2

    def __eq__(self, other):
        if isinstance(other, MyClass):
            return self.attr1 == other.attr1 and self.attr2 == other.attr2
        return False

    def __hash__(self):
        return hash((self.attr1, self.attr2))

设计原则及相互关系

1. 哈希函数设计原则：

   • 一致性：对于相等的对象（通过__eq__方法判断），哈希函数必须返回相同的哈希值。这确保了字典在查找时能够正确定位到相等的键。
   • 高效性：哈希函数应尽可能均匀地分布哈希值，减少哈希冲突。在上述代码中，通过对属性元组(self.attr1, self.attr2)进行哈希，利用Python内置的元组哈希机制，该机制通常能提供较好的分布。
   • 不可变性：如果对象的状态会发生改变，可能导致哈希值改变，那么就不适合作为字典键。在这个类中，假设attr1和attr2在实例化后不会改变，所以可以作为字典键。

2. __eq__方法设计原则：

   • 明确定义相等关系：__eq__方法应清晰定义两个实例在什么情况下被视为相等。在上述代码中，当且仅当attr1和attr2都相等时，两个实例被视为相等。
   • 与哈希函数一致性：如前所述，相等的对象必须有相同的哈希值。

3. 相互关系：

   • 哈希函数依赖__eq__定义：哈希函数的设计应基于__eq__方法所定义的相等关系。如果__eq__方法改变了相等的定义，哈希函数也应相应调整。
   • 协同工作提高效率：合理设计的哈希函数和__eq__方法能够提高字典操作（如查找、插入、删除）的效率。良好的哈希函数减少冲突，__eq__方法在哈希冲突发生时准确判断对象是否相等。