Как реализовать эффективную двунаправленную хеш-таблицу?

Question

Как реализовать эффективную двунаправленную хеш-таблицу?

Python dict очень полезная структура данных:

d = {'a': 1, 'b': 2}

d['a'] # get 1

Иногда также требуется индексировать значениями.

d[1] # get 'a'

Который является самым эффективным способом реализовать эту структуру данных? Какой-либо чиновник рекомендует способу сделать это?

64

python hashtable bidirectional

задан martineau 26 December 2018 в 23:22

3 ответа

Другие вопросы по тегам:

python hashtable bidirectional

Похожие вопросы:

score 35 · Answer 1

Вы можете использовать тот же самый словарь, добавив пару ключ-значение в обратном порядке.

d={'a':1,'b':2}
revd=dict([reversed(i) for i in d.items()])
d.update(revd)

score 32 · Answer 2

Двунаправленная хеш-таблица для бедняков будет использовать всего два словаря (это уже хорошо настроенные структуры данных).

В индексе также есть пакет bidict :

https://pypi.python.org/pypi/bidict

Источник для bidict можно найти на github:

https://github.com/jab/bidict

score 1 · Answer 3

Что-то вроде этого, может быть:

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        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):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

Вы должны решить, что вы хотите, если заданное значение имеет несколько ключей; двунаправленность данной пары может быть легко нарушена какой-либо более поздней парой, которую вы вставили. Я реализовал один из возможных вариантов.

Пример:

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b