Python 中的反向字典查找

根本没有。不要忘记该值可以在任意数量的键上找到，包括0或多于1。

据我所知，目前还没有一种方法，但是有一种方法可以做到这一点，那就是创建一个用于按键进行正常查找的 dict，以及另一个用于按值进行反向查找的 dict。

这里有一个实现的例子:

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

这确实意味着查找值的键可能导致多个结果，这些结果可以作为简单列表返回。

通过字典中的值可以是任何类型的对象，它们不能以其他方式进行散列或索引。因此，通过值查找键对于这种集合类型来说是不自然的。任何类似的查询只能在 O (n)时间内执行。因此，如果这是一个频繁的任务，你应该寻找一些关键索引，如 Jon sujest，或者甚至一些空间索引(DB 或 http://pypi.python.org/pypi/Rtree/)。

在有些情况下，字典是一个: 一个映射

例如,

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())

你的列表内涵检查所有的 dict 条目找到所有的匹配，然后只返回第一个键。这个生成器表达式只会在返回第一个值时进行必要的迭代:

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

其中 dd是决定权。如果没有找到匹配，将引发 StopIteration，因此您可能希望捕获这个异常并返回一个更合适的异常，如 ValueError或 KeyError。

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

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

这是一种权衡，感觉是错误的，但它很简单，有效，当然取决于值是元组而不是简单的值。

也许你想要的是一个类似字典的类，比如下面的 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))

这个版本比 你的短26% ，但是功能完全相同，即使是对于冗余/模糊的值(返回第一个匹配，就像您的那样)。但是，它的速度可能是您的两倍，因为它从 dict2次创建了一个列表。

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()

不，如果不查看所有键并检查它们的所有值，就无法有效地完成此操作。所以你需要 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])
}

由于这仍然是非常相关的，第一次 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'

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

我使用字典作为一种“数据库”，所以我需要找到一个关键，我可以重用。对于我来说，如果一个键的值是 None，那么我可以获取它并重用它，而不必“分配”另一个 id。我只是想分享一下。

db = {0:[], 1:[], ..., 5:None, 11:None, 19:[], ...}


keys_to_reallocate = [None]
allocate.extend(i for i in db.iterkeys() if db[i] is None)
free_id = keys_to_reallocate[-1]

我喜欢这一个，因为我不必尝试捕获任何错误，如 StopIteration或 IndexError。如果有可用的密钥，那么 free_id将包含一个。如果没有，那么它将只是 None。可能不是蟒蛇，但我真的不想在这里使用 try..。

做一本反向词典

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

如果您有许多反向查找要做

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