在Python中，如何从字典中获取键？

Question

我有一个可以用来放东西的字典的唯一标识符：

class identifier():
    def __init__(self, d):
        self.my_dict = d
        self.my_frozenset = frozenset(d.items())
    def __getitem__(self, item):
        return self.my_dict[item]
    def __hash__(self):
        return hash(self.my_frozenset)
    def __eq__(self, rhs):
        return self.my_frozenset == rhs.my_frozenset
    def __ne__(self, rhs):
       return not self == rhs

我有一个节点类型，它包含了用于哈希和比较的标识符：

class node:
    def __init__(self, id, value):
        # id is of type identifier
        self.id = id
        self.value = value
        # define other data here...
    def __hash__(self):
        return hash(self.id)
    def __eq__(self, rhs):
        if isinstance(rhs, node):
            return self.id == rhs.id
        ### for the case when rhs is an identifier; this allows dictionary
        ### node lookup of a key without wrapping it in a node
        return self.id == rhs
    def __ne__(self, rhs):
        return not self == rhs

我把一些节点放进了字典里：

d = {}
n1 = node(identifier({'name':'Bob'}), value=1)
n2 = node(identifier({'name':'Alex'}), value=2)
n3 = node(identifier({'name':'Alex', 'nationality':'Japanese'}), value=3)
d[n1] = 'Node 1'
d[n2] = 'Node 2'
d[n3] = 'Node 3'

过了一段时间，我只剩下一个标识符：

my_id = identifier({'name':'Alex'})

有没有什么方法可以高效地查找这个字典中与这个标识符对应的节点呢？

请注意，这比听起来要复杂一些；我知道我可以简单地用 d[my_id] 来获取关联的项目 'Node 2'，但我想高效地返回对 n2 的引用。

我知道我可以通过查看 d 中的每个元素来做到这一点，但我试过了，这太慢了（字典里有成千上万的项目，我需要做这个很多次）。

我知道在内部，dict 是使用 hash 和 eq 操作符来存储节点 n2 及其关联的项目 'Node 2'。实际上，使用 my_id 查找 'Node 2' 实际上需要先查找 n2，所以这肯定是可能的。

我用这个来存储图形中的数据。节点有很多额外的数据（我把它放在 value 中），这些数据在哈希中没有用到。我没有创建我正在使用的图形包（networkX），但我可以看到存储我的节点的字典。我也可以保持一个额外的字典来存储标识符和节点，但这会很麻烦（我需要包装图形类，并重写所有添加节点、删除节点、从列表中添加节点、从列表中删除节点、添加边等类型的函数，以保持那个字典的最新状态）。

这真是个难题。任何帮助都将非常感谢！

Answer 1

这里有一种方法可以在NetworkX中使用自定义节点对象。如果你把这个对象存储在“节点属性”字典里，你就可以通过引用ID来把对象取回来，这就像一个反向字典。虽然有点麻烦，但确实能用。

import networkx as nx

class Node(object):

    def __init__(self,id,**attr):
        self.id=id
        self.properties={}
        self.properties.update(attr)

    def __hash__(self):
        return self.id

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

    def __repr__(self):
        return str(self.id)

    def __str__(self):
        return str(self.id)


G=nx.Graph()
# add two nodes
n1=Node(1,color='red') # the node id must be hashable
n2=Node(2,color='green')
G.add_node(n1,obj=n1)
G.add_node(n2,obj=n2)

# check what we have
print G.nodes() # 1,2
print n1,n1.properties['color'] # 1,red
print n1==n2   # False 
for n in G:
    print n.properties['color']
print Node(1) in G # True
# change color of node 1
n1.properties['color']='blue'
for n in G:
    print n.properties

# use "node attribute" data in NetworkX to retrieve object
n=G.node[Node(1)]['obj']
print type(n) # <class '__main__.Node'>
print n # 1
print n.id # 1
print n.properties # {'color': 'blue'}

当然，你也可以定义一个函数来简化这个过程：

   def get_node(G,n):
        return G.node[Node(1)]['obj']

    n=get_node(G,1)
    print n.properties

Answer 2

有两个字典。

每当你往主要字典里添加一个键值对时，也要把这个键值对反过来添加到另一个字典里，也就是把键和值对调一下。

举个例子：

# When adding a value:
d[n2] = value;
# Must also add to the reverse dictionary:
rev[value] = d

# This means that:
value = d[n2]
# Will be able to efficiently find out the key used with:
key = rev[value]

Answer 3

不要用：

d[n1] = 'Node 1'

而是用：

d[n1] = ('Node 1', n1)

这样你就可以访问到 n1，无论你是怎么找到这个值的。

我认为，如果你只有 k2（它和 k1 是一样的），那么用字典是无法找回原来的键 k1 的。