双向/反向映射

Question

我正在用Python做一个交换机的东西，需要跟踪谁在和谁说话，如果Alice->Bob，那就意味着Bob->Alice。

是的，我可以创建两个哈希表，但我想知道是否有人有一种使用一个哈希表的方法。

或者建议另一种数据结构。

没有多个对话。假设这是为客服呼叫中心设计的，因此当Alice拨打交换机时，她只会与Bob通话。他的回复也只发给她。

- Sudhir Jonathan

---

请注意，您正在描述一个双射映射。 - Nick Dandoulakis

如果Alice正在和Bob交谈，那么她就不能同时与Charles交谈；同样，Bob也不能与其他人交谈。此外，在任何给定的时间内，你可以与多少人交谈，进行多少个对话？ - system PAUSE

不，我的交换机上没有这个。Alice 发给我的任何消息都必须转发给 Bob。只是我将同时路由数千个对话。但每个人一次只与另一个人交谈。 - Sudhir Jonathan

也许你需要一个Conversation类，它具有operator_id和customer_id属性，以及两个映射：operator_id -> conversation 和 customer_id -> conversation。 - John Machin

不需要存储任何对话记录，我只需要将客户的消息路由到操作员，反之亦然。 - Sudhir Jonathan

如果您正在寻找更一般的情况（不一定是双射），请参阅如何实现高效的双向哈希表？。 - Basj

Answer 1

您可以通过继承dict并添加所需逻辑来创建自己的字典类型。这里是一个基本示例：

class TwoWayDict(dict):
    def __setitem__(self, key, value):
        # Remove any previous connections with these values
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)

    def __delitem__(self, key):
        dict.__delitem__(self, self[key])
        dict.__delitem__(self, key)

    def __len__(self):
        """Returns the number of connections"""
        return dict.__len__(self) // 2

它的工作原理如下：

>>> d = TwoWayDict()
>>> d['foo'] = 'bar'
>>> d['foo']
'bar'
>>> d['bar']
'foo'
>>> len(d)
1
>>> del d['foo']
>>> d['bar']
Traceback (most recent call last):
  File "<stdin>", line 7, in <module>
KeyError: 'bar'

我确定我没有覆盖所有情况，但那应该能让你开始了解。

- Sasha Chedygov

---

@SudhirJonathan：你可以进一步发挥这个想法——例如，添加一个.add方法，这样你就可以像这样做d.add('Bob', 'Alice')而不是使用我展示的语法。我还会包括一些错误处理。但你已经掌握了基本思路。 :) - Sasha Chedygov

我猜这属于那些添加的范畴，但在设置新的键值对时删除旧的键值对会很有帮助（d['foo'] = 'baz' 还需要额外删除 bar 键）。 - beardc

@SashaChedygov 我没有从问题中读出这一点，只知道它是一个双射映射 - 但你是对的，在这种情况下，映射是从参与者集合到其自身。因此，这个问题，它没有那个假设，就是一个fupe（=fake-dupe）。 - Tobias Kienzler

值得一提的是：子类化 dict 在此处会产生一些误导性的行为，因为如果你使用一些初始内容创建对象，那么结构将会被破坏。需要重写 __init__ 函数以允许像 d = TwoWayDict({'foo' : 'bar'}) 这样的构建方式正常工作。 - Henry Keiter

提醒一下，这个功能已有对应的库：pip install bidict。网址：https://pypi.python.org/pypi/bidict/。 - user1036719

Answer 2

在您的特殊情况下，您可以将两者存储在一个字典中：

relation = {}
relation['Alice'] = 'Bob'
relation['Bob'] = 'Alice'

由于你所描述的是一种对称关系：A -> B => B -> A

- Nadia Alramli

---

嗯... 是的，我最喜欢这个。本来想避免写两个选项，但这是目前为止最好的想法。 - Sudhir Jonathan

仍然认为双向映射应该是可能的 :-/ - Sudhir Jonathan

如果需要高效，那么在底层你需要将两个键都索引到某个索引数据结构中——无论是哈希、排序列表、二叉树、字典树、后缀数组还是其他更奇特的结构。在Python中实现这一点的简单方法是使用哈希。 - Kragen Javier Sitaker

@SudhirJonathan 如果你需要一个真正的双向映射，可以看看bidict，如这个问题所述 - 请注意Aya在我的重复问题上的评论中讨论的性能问题。 - Tobias Kienzler

Answer 3

我知道这个问题很旧了，但我想提到另一个很好的解决方案，即Python包bidict。它非常容易使用：

from bidict import bidict
map = bidict(Bob = "Alice")
print(map["Bob"])
print(map.inv["Alice"])

- Nearoo

---

"map" 遮蔽了 Python 内置关键字 'map'。 - Chris

Answer 4

我会创建一个第二个哈希表，并用以下方式填充：

reverse_map = dict((reversed(item) for item in forward_map.items()))

- Ian Clelland

---

代码中有一些多余的括号：reverse_map = dict(reversed(item) for item in forward_map.items())。该代码的作用是将一个字典反转，得到一个新的字典，其中原字典的键变为新字典的值，原字典的值变为新字典的键。可以将代码简化为：reverse_map = {v:k for k,v in forward_map.items()}。 - Andriy Drozdyuk

如果您不打算进一步更新字典，那么这是一个很好的简单方法。我使用了 my_dict.update(dict(reversed(item) for item in my_dict.items()))。 - Gilly

在Python 3中使用此代码时，我收到一个警告：Unexpected type(s): (Generator[Iterator[Union[str, Any]], Any, None]) Possible types: (Mapping) (Iterable[Tuple[Any, Any]])。有什么办法可以消除这个警告吗？ - Kerwin Sneijders

在Python3中，使用以下代码不会出现警告：my_dict.update({item[1]: item[0] for item in my_dict.items()})。 - mmindenhall

Answer 5

如果你可以承受内存消耗，使用两个哈希映射实际上可能是最快的解决方案。我建议将它们封装在一个类中，程序员的负担在于确保这两个哈希映射能够正确地同步。

- Kenan Banks

---

+1，这就是bidict的基本功能，同时提供了通过使用mydict[:value]来获取key的语法糖（以一定的性能代价为代价）来访问反向映射。 - Tobias Kienzler

Answer 6

一种更简洁的方法，仍然使用reversed函数：

dict(map(reversed, my_dict.items()))

- Eti JS

Answer 7

你有两个不同的问题。

1. 你有一个“Conversation”对象。它涉及到两个人。由于一个人可以有多个对话，所以你有一个多对多的关系。

2. 你有一个从人到“Conversations”列表的Map。每个“Conversations”都有一对人。

做这样的事情：

from collections import defaultdict
switchboard= defaultdict( list )

x = Conversation( "Alice", "Bob" )
y = Conversation( "Alice", "Charlie" )

for c in ( x, y ):
    switchboard[c.p1].append( c )
    switchboard[c.p2].append( c )

- S.Lott

Answer 8

不，没有办法在不创建两个字典的情况下完成这个任务。如果只使用一个字典，如何才能保持相似的性能并实现此功能呢？

最好创建一个自定义类型，封装两个字典并公开所需的功能。

- Andrew Hare

Answer 9

另一个可能的解决方案是实现 dict 的子类，该子类保存原始字典并跟踪其反向版本。如果键和值重叠，则保留两个单独的字典很有用。

class TwoWayDict(dict):
    def __init__(self, my_dict):
        dict.__init__(self, my_dict)
        self.rev_dict = {v : k for k,v in my_dict.iteritems()}

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        self.rev_dict.__setitem__(value, key)

    def pop(self, key):
        self.rev_dict.pop(self[key])
        dict.pop(self, key)

    # The above is just an idea other methods
    # should also be overridden. 

例子：

>>> d = {'a' : 1, 'b' : 2} # suppose we need to use d and its reversed version
>>> twd = TwoWayDict(d)    # create a two-way dict
>>> twd
{'a': 1, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b'}
>>> twd['a']
1
>>> twd.rev_dict[2]
'b'
>>> twd['c'] = 3    # we add to twd and reversed version also changes
>>> twd
{'a': 1, 'c': 3, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b', 3: 'c'}
>>> twd.pop('a')   # we pop elements from twd and reversed  version changes
>>> twd
{'c': 3, 'b': 2}
>>> twd.rev_dict
{2: 'b', 3: 'c'}

- Akavall

Answer 10

您可以使用 DoubleDict，如Python Cookbook中的578224号配方所示。

- Noctis Skytower