효율적인 양방향 해시 테이블을 구현하는 방법은 무엇입니까?

효율적인 양방향 해시 테이블을 구현하는 방법은 무엇입니까?

---

Python dict은 매우 유용한 데이터 구조입니다.

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

d['a'] # get 1

때로는 값으로 색인을 생성하고 싶을 수도 있습니다.

d[1] # get 'a'

이 데이터 구조를 구현하는 가장 효율적인 방법은 무엇입니까? 공식적으로 권장하는 방법이 있습니까?

---

다음은 Python 사전의 값에서 키 찾기dict 에서 영감을 받아 다음 2) 및 3)을 허용하도록 수정 된 양방향 클래스입니다 .

참고 :

• 1) 역 디렉토리 bd.inverse 는 표준 dict bd가 수정 되면 자동으로 업데이트됩니다 .
• 2) 역 디렉토리 bd.inverse[value] 는 항상 다음 과 key같은 목록 입니다 bd[key] == value.
• 3) https://pypi.python.org/pypi/bidict 의 bidict모듈 과 달리 여기서는 동일한 값을 가진 2 개의 키를 가질 수 있습니다 . 이것은 매우 중요 합니다.

암호:

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value,[]).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value,[]).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key],[]).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

사용 예 :

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}

---

키, 값 쌍을 역순으로 추가하여 동일한 dict 자체를 사용할 수 있습니다.

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

---

가난한 사람의 양방향 해시 테이블은 두 개의 사전 만 사용하는 것입니다 (이는 이미 고도로 조정 된 데이터 구조입니다).

색인에 bidict 패키지 도 있습니다 .

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

bidict의 소스는 github에서 찾을 수 있습니다.

• https://github.com/jab/bidict

---

아래 코드 스 니펫은 반전 가능한 (용 사적) 맵을 구현합니다.

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

The advantage of this implementation is that the inverse attribute of a BijectiveMap is again a BijectiveMap. Therefore you can do things like:

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True

---

Something like this, maybe:

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

You have to decide what you want to happen if more than one key has a given value; the bidirectionality of a given pair could easily be clobbered by some later pair you inserted. I implemented one possible choice.

---

Example :

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

---

First, you have to make sure the key to value mapping is one to one, otherwise, it is not possible to build a bidirectional map.

Second, how large is the dataset? If there is not much data, just use 2 separate maps, and update both of them when updating. Or better, use an existing solution like Bidict, which is just a wrapper of 2 dicts, with updating/deletion built in.

But if the dataset is large, and maintaining 2 dicts is not desirable:

• If both key and value are numeric, consider the possibility of using Interpolation to approximate the mapping. If the vast majority of the key-value pairs can be covered by the mapping function (and its
  reverse function), then you only need to record the outliers in maps.

• If most of access is uni-directional (key->value), then it is totally ok to build the reverse map incrementally, to trade time for
  space.

Code:

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

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]

참고URL : https://stackoverflow.com/questions/3318625/how-to-implement-an-efficient-bidirectional-hash-table