Python中的反向字典查找

Question

是否有任何直接的方法通過了解字典中的值來查找關鍵字？

所有我能想到的是這樣的：

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

Answer 1

有沒有。不要忘記，可以在任意數量的鍵上找到該值，包括0或大於1.

Answer 2

據我所知，沒有一個鍵可以做，但是一種方法是創建一個字典用於通過鍵進行正常查找以及用於按值進行反向查找的另一個字典。

這裏有這樣一個實現的例子：

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

這並不意味着查找一個值的按鍵可能會導致它可以返回一個簡單的列表多個結果。

Answer 3

通過字典中的值可以是任何類型的對象，它們不能以其他方式進行散列或索引。因此，通過該值查找關鍵字對於此集合類型是不自然的。任何類似的查詢都只能在O（n）時間內執行。因此，如果這是頻繁的任務，你應該看看一些關鍵的索引，比如Jon，或者甚至是一些空間索引（DB或http://pypi.python.org/pypi/Rtree/）。

Answer 4

存在以下情況：一本字典是一個：一個映射

例如，

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

Answer 5

你的列表中理解穿過字典的所有項目找到所有的比賽，然後就返回第一個關鍵。該發生器表達只會迭代儘可能必要返回第一值：

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

其中dd是字典。如果找不到匹配項，將會增加StopIteration，因此您可能需要注意並返回一個更合適的例外，如ValueError或KeyError。

Answer 6

我知道這可能被視爲「浪費」，但在這種情況下，我經常存儲密鑰作爲值記錄的附加列：

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

這是一個權衡和感覺錯了，但它的簡單和作品，當然取決於值是元組而不是簡單的值。

Answer 7

也許像下面的字典一樣的類如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)) 

Answer 8

此版本比相同yours但功能縮短26％，甚至爲冗餘/曖昧值（返回第一匹配，因爲你的一樣）。然而，它可能是你的兩倍，因爲它從字典中創建了一個列表兩次。

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

或者如果你喜歡簡潔易讀性上可以保存一個或多個字符與

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

如果你喜歡效率，@ PaulMcGuire的approach更好。如果有很多鍵共享相同的值是更有效的不是實例鍵那樣的list列表理解，而是使用使用發電機：

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

Answer 9

key in dict.values() 

這是字面上它

Answer 10

不，如果不查看所有鍵並檢查其所有值，都無法有效地進行此操作。所以你需要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]) 
} 

Answer 11

由於這仍然非常相關，第一款谷歌打，我只是花一些時間弄清這一點，我會後我的（在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' 

它會給你的第一個匹配的值。

Answer 12

我使用字典作爲一種「數據庫」，所以我需要找到一個可以重用的密鑰。對於我的情況，如果一個密鑰的值是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。可能不pythonic，但我真的不想在這裏使用try ...

Answer 13

正如值可以在字典不存在，一個更Python和自動記錄的代碼將是：

a # Value to search against 
x = None # Searched key 
for k, v in d.items(): 
    if v == a: 
     x = k 
     break 
x # Now contains the key or None if not found. 

事實上類型的字典都沒有作出回答這樣的問題羣，如果你遇到這樣的問題上新設計的程序，那麼你應該回顧一下你的設計。