在Python中进行逆向字典查找

Question

有没有一种简单的方法，在已知字典值的情况下找到对应的键？

我所能想到的是这个：

key = [key for key, value in dict_obj.items() if value == 'value'][0]

- RadiantHex

---

可能是重复问题：https://dev59.com/iHRB5IYBdhLWcg3w3K8J - Tobias Kienzler

谷歌引导我来到这里... 我必须说... 为什么没有人像我一样使用iteritems，因为这使得速度快了40倍... 而使用().next方法。 - Angry 84

如果你有很多反向查找要做：reverse_dictionary = {v:k for k,v in dictionary.items()} - Austin

@TobiasKienzler 虽然通过反转字典然后进行普通查找可以解决问题，但显然这里的目标是确定哪个键对应于某个值。还有其他方法可以实现，尽管它们仍然是O（N）。 - Karl Knechtel

Answer 1

你的列表推导式遍历字典的所有项，找到所有匹配项，然后仅返回第一个键。这个生成器表达式只会迭代到必须返回第一个值为止：

key = next(key for key, value in dd.items() if value == 'value')

其中dd是字典。如果未找到匹配项，则会引发StopIteration，因此您可能希望捕获并返回更合适的异常，例如ValueError或KeyError。

- PaulMcG

---

当key不在列表中时，它应该引发与listObject.index(key)相同的异常。 - Brian Jack

如果有多个匹配项，使用keys = { key for key,value in dd.items() if value=='value' }来获取所有键的集合。 - askewchan

没必要将结果返回为集合(set)，因为字典的键已经保证了唯一性，只需返回一个列表(list)即可，或者更好的方式是返回生成器表达式(generator expression)，让调用者将其放入任何容器中。 - PaulMcG

Answer 2

有些情况下，字典是一对一的映射。

例如：

d = {1: "one", 2: "two" ...}

如果你只需要进行单个查找，那么你的方法是可行的。但是，如果你需要进行多个查找，创建一个反向字典会更加高效。

ivd = {v: k for k, v in d.items()}

如果存在多个具有相同值的键的可能性，您需要在这种情况下指定所需的行为。

如果您使用的是Python 2.6或更旧版本，您可以使用：

ivd = dict((v, k) for k, v in d.items())

- John La Rooy

---

优化得很好。但我认为你的意思是使用dict()将你的2元组列表转换为字典：ivd=dict([(v,k) for (k,v) in d.items()])。 - hobs

@hobs 可以使用字典推导式而不是列表推导式：invd = { v:k for k,v in d.items() } - askewchan

@gnibbler 字典理解在 Python 2.6 中尚未迁移回来，因此如果您想保持可移植性，您需要忍受在生成器或列表理解式中使用dict()包装二元组的额外6个字符。 - hobs

@hobs，我已经将这个加入到我的回答中了。 - John La Rooy

Answer 3

这个版本比你的版本短了26%，但功能相同，即使对于冗余/模糊值也是如此（返回第一个匹配项，与你的版本相同）。然而，它可能比你的版本慢两倍，因为它从字典创建了列表两次。

key = dict_obj.keys()[dict_obj.values().index(value)]

如果你更喜欢简洁而不是易读性，你可以使用下面的方法来节省一个字符：

key = list(dict_obj)[dict_obj.values().index(value)]

如果您更注重效率，@PaulMcGuire的方法更好。如果有很多键共享相同的值，则最好不要使用列表推导式来实例化那个键的列表，而是使用生成器：

key = (key for key, value in dict_obj.items() if value == 'value').next()

- hobs

---

假设是原子操作，键和值是否保证有相同的对应顺序？ - Noctis Skytower

@NoctisSkytower 是的，只要在调用之间没有更改 dict，dict.keys() 和 dict.values() 就是一一对应的。 - hobs

Answer 4

由于这仍然非常相关，而且我在Google上找到了第一个结果并花了一些时间弄清楚，因此我将发布我的解决方案（适用于Python 3）：

testdict = {'one'   : '1',
            'two'   : '2',
            'three' : '3',
            'four'  : '4'
            }

value = '2'

[key for key in testdict.items() if key[1] == value][0][0]

Out[1]: 'two'

它将给你匹配的第一个值。

- Freek

Answer 5

也许像下面的DoubleDict这样的类似字典的类是你想要的？你可以使用任何一个提供的元类与DoubleDict结合使用，或完全避免使用任何元类。

import functools
import threading

################################################################################

class _DDChecker(type):

    def __new__(cls, name, bases, classdict):
        for key, value in classdict.items():
            if key not in {'__new__', '__slots__', '_DoubleDict__dict_view'}:
                classdict[key] = cls._wrap(value)
        return super().__new__(cls, name, bases, classdict)

    @staticmethod
    def _wrap(function):
        @functools.wraps(function)
        def check(self, *args, **kwargs):
            value = function(self, *args, **kwargs)
            if self._DoubleDict__forward != \
               dict(map(reversed, self._DoubleDict__reverse.items())):
                raise RuntimeError('Forward & Reverse are not equivalent!')
            return value
        return check

################################################################################

class _DDAtomic(_DDChecker):

    def __new__(cls, name, bases, classdict):
        if not bases:
            classdict['__slots__'] += ('_DDAtomic__mutex',)
            classdict['__new__'] = cls._atomic_new
        return super().__new__(cls, name, bases, classdict)

    @staticmethod
    def _atomic_new(cls, iterable=(), **pairs):
        instance = object.__new__(cls, iterable, **pairs)
        instance.__mutex = threading.RLock()
        instance.clear()
        return instance

    @staticmethod
    def _wrap(function):
        @functools.wraps(function)
        def atomic(self, *args, **kwargs):
            with self.__mutex:
                return function(self, *args, **kwargs)
        return atomic

################################################################################

class _DDAtomicChecker(_DDAtomic):

    @staticmethod
    def _wrap(function):
        return _DDAtomic._wrap(_DDChecker._wrap(function))

################################################################################

class DoubleDict(metaclass=_DDAtomicChecker):

    __slots__ = '__forward', '__reverse'

    def __new__(cls, iterable=(), **pairs):
        instance = super().__new__(cls, iterable, **pairs)
        instance.clear()
        return instance

    def __init__(self, iterable=(), **pairs):
        self.update(iterable, **pairs)

    ########################################################################

    def __repr__(self):
        return repr(self.__forward)

    def __lt__(self, other):
        return self.__forward < other

    def __le__(self, other):
        return self.__forward <= other

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

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

    def __gt__(self, other):
        return self.__forward > other

    def __ge__(self, other):
        return self.__forward >= other

    def __len__(self):
        return len(self.__forward)

    def __getitem__(self, key):
        if key in self:
            return self.__forward[key]
        return self.__missing_key(key)

    def __setitem__(self, key, value):
        if self.in_values(value):
            del self[self.get_key(value)]
        self.__set_key_value(key, value)
        return value

    def __delitem__(self, key):
        self.pop(key)

    def __iter__(self):
        return iter(self.__forward)

    def __contains__(self, key):
        return key in self.__forward

    ########################################################################

    def clear(self):
        self.__forward = {}
        self.__reverse = {}

    def copy(self):
        return self.__class__(self.items())

    def del_value(self, value):
        self.pop_key(value)

    def get(self, key, default=None):
        return self[key] if key in self else default

    def get_key(self, value):
        if self.in_values(value):
            return self.__reverse[value]
        return self.__missing_value(value)

    def get_key_default(self, value, default=None):
        return self.get_key(value) if self.in_values(value) else default

    def in_values(self, value):
        return value in self.__reverse

    def items(self):
        return self.__dict_view('items', ((key, self[key]) for key in self))

    def iter_values(self):
        return iter(self.__reverse)

    def keys(self):
        return self.__dict_view('keys', self.__forward)

    def pop(self, key, *default):
        if len(default) > 1:
            raise TypeError('too many arguments')
        if key in self:
            value = self[key]
            self.__del_key_value(key, value)
            return value
        if default:
            return default[0]
        raise KeyError(key)

    def pop_key(self, value, *default):
        if len(default) > 1:
            raise TypeError('too many arguments')
        if self.in_values(value):
            key = self.get_key(value)
            self.__del_key_value(key, value)
            return key
        if default:
            return default[0]
        raise KeyError(value)

    def popitem(self):
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError('popitem(): dictionary is empty')
        return key, self.pop(key)

    def set_key(self, value, key):
        if key in self:
            self.del_value(self[key])
        self.__set_key_value(key, value)
        return key

    def setdefault(self, key, default=None):
        if key not in self:
            self[key] = default
        return self[key]

    def setdefault_key(self, value, default=None):
        if not self.in_values(value):
            self.set_key(value, default)
        return self.get_key(value)

    def update(self, iterable=(), **pairs):
        for key, value in (((key, iterable[key]) for key in iterable.keys())
                           if hasattr(iterable, 'keys') else iterable):
            self[key] = value
        for key, value in pairs.items():
            self[key] = value

    def values(self):
        return self.__dict_view('values', self.__reverse)

    ########################################################################

    def __missing_key(self, key):
        if hasattr(self.__class__, '__missing__'):
            return self.__missing__(key)
        if not hasattr(self, 'default_factory') \
           or self.default_factory is None:
            raise KeyError(key)
        return self.__setitem__(key, self.default_factory())

    def __missing_value(self, value):
        if hasattr(self.__class__, '__missing_value__'):
            return self.__missing_value__(value)
        if not hasattr(self, 'default_key_factory') \
           or self.default_key_factory is None:
            raise KeyError(value)
        return self.set_key(value, self.default_key_factory())

    def __set_key_value(self, key, value):
        self.__forward[key] = value
        self.__reverse[value] = key

    def __del_key_value(self, key, value):
        del self.__forward[key]
        del self.__reverse[value]

    ########################################################################

    class __dict_view(frozenset):

        __slots__ = '__name'

        def __new__(cls, name, iterable=()):
            instance = super().__new__(cls, iterable)
            instance.__name = name
            return instance

        def __repr__(self):
            return 'dict_{}({})'.format(self.__name, list(self))

- Noctis Skytower

Answer 6

# oneline solution using zip
>> x = {'a':100, 'b':999}
>> y = dict(zip(x.values(), x.keys()))  
>> y
{100: 'a', 999: 'b'}

- NotTooTechy

Answer 7

不，如果不查看所有的键并检查它们的值，则无法有效地完成此操作。因此，需要 O(n) 时间来完成此操作。如果您需要执行大量此类查找，则需要通过构建反转字典（也可以在 O(n) 内完成）来有效地执行此操作，然后在该反转字典内进行搜索（每次搜索平均需要 O(1)）。

以下是从普通字典构建反转字典（能够执行一对多映射）的示例：

for i in h_normal:
    for j in h_normal[i]:
        if j not in h_reversed:
            h_reversed[j] = set([i])
        else:
            h_reversed[j].add(i)

例如，如果您的

h_normal = {
  1: set([3]), 
  2: set([5, 7]), 
  3: set([]), 
  4: set([7]), 
  5: set([1, 4]), 
  6: set([1, 7]), 
  7: set([1]), 
  8: set([2, 5, 6])
}

你的 h_reversed 将会是

{
  1: set([5, 6, 7]),
  2: set([8]), 
  3: set([1]), 
  4: set([5]), 
  5: set([8, 2]), 
  6: set([8]), 
  7: set([2, 4, 6])
}

- Salvador Dali

Answer 8

制作反向词典

reverse_dictionary = {v:k for k,v in dictionary.items()} 

如果您需要进行大量反向查找

- imbr

---

只有在键和值之间存在一对一映射时，此方法才有效。 - Noel Yap

这也需要将值（现在变成键）变为可哈希的。 - MMM

Answer 9

据我所知，目前还没有这样的方法，但是有一种方法可以创建一个字典用于按键进行正常查找，另一个字典用于按值进行反向查找。

这里有一个这样实现的示例：

http://code.activestate.com/recipes/415903-two-dict-classes-which-can-lookup-keys-by-value-an/

这意味着查找一个值的键可能会有多个结果，可以作为一个简单列表返回。

- Jonathan Holloway

---

请注意，有许多可能的值不是有效的键。 - Ignacio Vazquez-Abrams

Answer 10

我知道这可能被认为是“浪费”，但在这种情况下，我经常将键作为值记录中的附加列存储：

d = {'key1' : ('key1', val, val...), 'key2' : ('key2', val, val...) }

这是一种权衡，感觉不太对，但它简单有效，当然前提是值必须是元组而不是简单值。

- CarlS