python - 使用自定义对象查询 Python 字典键

Question

考虑一个字典，其中的键是使用以下类的对象创建的:

class Point( object ):

    def __init__( self, x, y ):
        self.x = x
        self.y = y

    def __eq__( self, other ):
        return self.x == other.x

    def __hash__( self ):
        return self.x.__hash__()

    def __ne__( self, other ):
        return self.x != other.x

>>> a = Point(1,1)
>>> b = Point(0, 2)
>>> dct = {}
>>> dct[a] = 15
>>> dct[b] = 16
>>> dct[a]
15
>>> c = Point(1,None)
>>> dct[c]
15

发生这种情况是因为 c 和 a 共享相同的散列且相等。是否有 O(1) 方法来实现给定 c 返回 a 的函数(与下面的 O(n) 实现相反？):

def getKey( dct, key ):
    for k in dct:
        if k == key:
            return k
    return None

Answer 1

你的函数总是返回 None 或 key，所以我不明白你的意思...

根据复杂度，假设你至少需要 O(log(n))， 例如，如果 dct 是我认为的字典，那么:

def getKey( dct, key ):
    if dct.has_key(key):
        return key
    return None

如果你想返回它的值，那么只需使用:dct.get(key, None)