파이썬 (해싱을 사용하여 딕셔너리 구현하기)

다음 코드는 간단한 해시 함수를 사용하여 정수가 키인 딕셔너리를 구현하고 있다. 여기에서 기본적인 아이디어는 intDict 클래스의 인스턴스를 해시 버킷 리스트로 나타내는 것이며, 각 버킷은 키/값의 쌍들로 이루어진 리스트이다. 각 버킷을 리스트로 구현함으로 버킷에 해시되는 값들을 리스트에 저장하여 충돌을 해결할 수 있다. 인스턴스 변수 buckets는 numBuckets의 개수만큼의 빈 리스트로 초기화한다. dictkey키로 엔트리를 검색하거나 저장하려고 할 때 해시함수 %를 사용하여 dictkey를 정수로 반환하고 그 정수를 사용하여 buckets를 인덱스하여 해당하는 dictkey와 연관된 해시 버킷을 찾아낸다. 그 다음엔 그 버킷을 선형적으로 검색하여 dictkey키로 된 엔트리가 있는지 확인한다. 검색을 하는 경우에는 그 키로 된 엔트리가 없다면 None을 반환한다. 저장을 하려고 하는 경우에는 이미 들어가 있는 엔트리가 있다면 그 엔트리의 값을 대체하거나 엔트리가 없다면 새로운 엔트리를 추가한다.

# 해싱을 사용하여 딕셔너리 구현하기
class intDict(object):
    def __init__(self, numBuckets):
        self.buckets = []
        self.numBuckets = numBuckets
        for i in range(numBuckets):
            self.buckets.append([])

    def addEntry(self, dictKey, dictVal):
        hashBucket = self.buckets[dictKey%self.numBuckets]
        for i in range(len(hashBucket)):
            if hashBucket[i][0] == dictKey:
                hashBucket[i] = (dictKey, dictVal)
                return
        hashBucket.append((dictKey, dictVal))

    def getValue(self, dicKey):
        hashBucket = self.buckets[dicKey%self.numBuckets]
        for e in hashBucket:
            if e[0] == dicKey:
                return e[1]
            return None
        
    def __str__(self):
        result = '{'
        for b in self.buckets:
            for e in b:
                result = result + str(e[0]) + ':' + str(e[1]) + ', '
                return result[:-1] + '}'
            
import random
D = intDict(29)
for i in range(20):
    key = random.randint(0, 10**5)
    D.addEntry(key, i)

print('The value of the intDict is:')
print(D)
print('\n', 'The buckets are:')
for hashBucket in D.buckets:
    print(' ', hashBucket)

__str__ 메소드에서 보면 요소들이 추가된 순서에 관계없이 키가 해시하려는 값의 순서로 딕셔너리를 만들고 있다는 것을  알 수가 있다. 이것이 dict 자료형의 키의 순서를 왜 예측할 수 없는지를 설명해준다. 위의 코드는 먼저 20개의 엔트리로 intDict를 만든다. 엔트리의 값은 정수 0에서 19이다. 키는 0과 10^5 -1 사이의 정수 중 하나를 임의로 선택한다. 그 다음에는 클래스에 정의된 __str__ 메소드를 사용하여 intDict를 출력한다. 마직막으로 D.bucket을 반복하여서 각 해시 버킷을 출력한다.

 

출력 결과

The value of the intDict is:
{957:7,}

 The buckets are:
  [(957, 7)]
  [(96745, 4), (19373, 5), (1567, 19)]
  [(86799, 12)]
  []
  []
  [(79726, 1)]
  []
  [(43101, 10), (36112, 18)]
  [(74886, 16)]
  []
  []
  [(62042, 13)]
  []
  [(68018, 6)]
  []
  []
  []
  [(83508, 17)]
  [(192, 2)]
  []
  []
  [(10722, 3), (99839, 14)]
  []
  [(34620, 0)]
  [(18381, 9), (33490, 11)]
  []
  []
  [(22792, 15)]
  [(79952, 8)]

만약 추상화 장벽을 무시하고 intDict을 직접 살펴보면 많은 해시 버킷이 비어있는 것을 확인할 수 있다. 비어있지 않은 버킷은 충돌 횟수에 따라 하나에서 세 개의 튜플을 갖고 있다.