3

考虑使用以下类的对象创建的带有键的字典：

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
4

4 回答 4

2

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

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

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

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

于 2012-05-31T22:40:20.730 回答
1

您可能可以将字典的值作为由键和值本身组成的元组或列表。使用您的示例：

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

现在你可以像这样a使用c：

>>> dct[c][1]
于 2012-05-31T23:06:22.213 回答
1

发生这种情况是因为 c 和 a 共享相同的哈希。

不; 发生这种情况是因为它们共享一个哈希并且彼此比较相等。

通常，不相等的对象可能散列到相同的值。（相等的对象必须散列到相同的值。）

__eq__如果对象具有相同的 x 坐标，则您将对象定义为相等。这显然是错误的；只有当两个坐标相等时，它们才应该相等。

但听起来这不是你真正想要做的。如果你想“给定c，得到a”，那么你真正要求的是在给定一个点的情况下找到具有相同 x 坐标的所有其他点。

这很简单：制作一个将 x 坐标值映射到具有该坐标的点的字典。

于 2012-05-31T23:12:41.513 回答
0

换句话说，给定一个对象列表和一个对象 X，在列表中找到一个与 X 具有相同哈希值的元素。考虑：

class A(object):
    def __init__(self, x, blah):
        self.x = x
        self.blah = blah
    def __eq__(self, other):
        return self.x == other.x
    def __hash__(self):
        return self.x
    def __repr__(self):
        return '%d-%s' % (self.x, self.blah)


ls = [A(1, 'one'), A(2, 'FOO'), A(3, 'three')]
test = A(2, 'BAR')
print test, '=', (set(ls) - (set(ls) - set([test]))).pop()

要使用您的字典示例，请替换set(ls)为viewkeys：

dct = dict(zip(ls, range(100)))
print test, '=', (dct.viewkeys() - (dct.viewkeys() - set([test]))).pop()
于 2012-05-31T23:12:19.903 回答