在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 及其关联的项目，“节点 2”。事实上，使用 my_id 查找 'Node 2' 实际上需要查找 n2 作为中间步骤，所以这绝对应该是可能。

我用它来将数据存储在图表中。节点有很多未在哈希中使用的附加数据（我在其中放置值）。我没有创建我正在使用的图形包（networkX），但我可以看到存储我的节点的字典。我还可以保留一个关于节点标识符的额外字典，但这会很痛苦（我需要包装图形类并重写所有添加节点，删除节点，从列表中添加节点，从列表中删除节点，添加边缘等键入函数以使该字典保持最新）。

这真是一个难题。任何帮助将不胜感激！

Answer 1

而不是

d[n1] = 'Node 1'

使用：

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

那么无论您如何找到该值，您都可以访问n1。

如果你拥有的只是等于 k1 的 k2 ，我不相信字典有办法检索原始密钥 k1 。

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

这是一种将自定义节点对象与 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 4

问题是，无法保证密钥实际上是节点。如果你这样做，

d[my_id]=d[my_id] 

一切仍然会完美地工作，除了现在，你的密钥是一个标识符而不是一个节点。
像这样允许两个类“相等”确实很危险。
如果您确实需要通过名称查找节点，则应在 Node 类或外部完成，但不应依赖于哈希中节点的存在。

如果你无法修改它（因为你无法修改代码），那么我猜你只能采用这种低效的方式

Answer 5

使用 my_id 查找“节点 2”实际上需要查找 n2 作为中间步骤

这是不正确。字典是一个哈希表：它将项目的哈希映射到（一桶）条目。当您请求 d[my_id] 时，Python 首先获取 hash(my_id)，然后在 d 中查找。你会感到困惑，因为你有 hash(n1) == hash(id1)，这是一件非常糟糕的事情。

您要求标识符和节点之间的映射。如果您想要其中之一，则必须自己创建一个。

---

标识符是在创建时就全部与节点匹配的，还是稍后再构造它们？也就是说，您是否真的要求能够找到具有标识符 identifier({'name':'Alex'}) 的节点，或者该标识符是否已创建并添加到节点？如果是后者，您可以执行以下操作：

class Node:
    def __init__(self, id, value):
        id.parent = self
        ...