🔥 TIL - Day 35

이번엔 알고리즘 풀이를 할 때 굉장히 빈번하게 쓰이는 딕셔너리에 대해 알아봤다.

딕셔너리는 key 값으로 value를 찾는 자료구조이다.

일단 딕셔너리의 내부구조를 이해하기 전에 해시 테이블이라는 개념을 알아야 한다.
해시 테이블은 해시 값의 결과를 인덱스로 사용하여 그에 매핑되는 값을 찾는 자료구조이다.

해시 테이블을 알려면 또 해시함수를 알야야 하는데 간단하게 알아보자면 임의 길이의 문자열을 해시 알고리즘에 의해 고정된 길이의 문자열로 변경하는 것이다.

자 해시 테이블을 구성하는 방법을 한 번 생각해보자.
해싱된 결과를 인덱스로 쓴다고 했는데 해싱된 문자열을 그대로 쓸 수 없으니 해시 테이블의 크기로 해싱된 문자열을 나머지 연산 한 결과를 인덱스로 사용한다. 그러면 키 값의 역할을 할 해싱된 문자열은 해시 테이블에 들어갈 수 있는 인덱스의 범위로 계산이 될 것이고 해당 인덱스에 값을 넣어주면 된다.

여기까지 말로 한 내용을 코드로 옮겨보자.
직접 파이썬의 딕셔너리를 구현보는 것이다.

class Dict:

    HASH_TABLE_SIZE = 8

    def __init__(self):
        self.hash_table = [0] * self.HASH_TABLE_SIZE

    def put(self, key, value):
        index = hash(key) % self.HASH_TABLE_SIZE
        self.hash_table[index] = value

    def get(self, key):
        index = hash(key) % self.HASH_TABLE_SIZE
        return self.hash_table[index]

내부적으로 해시 테이블의 역할을 할 리스트를 갖는다. 인덱스를 잡기 위해 리스트는 반드시 초기화해줘야 한다.

딕셔너리에서 핵심적인 기능인 삽입(put), 조회(get)을 구현했다.

삽입의 경우 파이썬이 제공해주는 hash 함수를 이용해서 key 값의 해시 값을 구하고 해시 테이블의 크기로 나머지 연산을 한다. 이렇게 되면 key 값이 어떤 값이든 해시 테이블의 크기 안에 들어오는 인덱스로 변환될 것이므로 해당 인덱스에 value를 넣어주면 된다.

조회는 삽입과 거의 같다. hash 함수와 해시 테이블의 크기로 해시 테이블의 index를 계산하고 해당 index의 값을 리턴한다.

테스트

dict = Dict()
dict.put('key1', 'value1')
dict.put('key2', 'value2')

print(dict.get('key1'))

한 개만 더 신경써보자.
해싱된 결과를 해시 테이블의 크기로 나머지 연산한 결과를 해시 테이블의 인덱스로 쓴다고 했다. 이 인덱스가 중복되는 경우는 없을까 ??

있다. 있다. 있다.

인덱스 중복보다는 충돌이라는 단어를 더 많이 쓰는 것 같다.
key 값을 해싱한 결과는 해시함수에 의해 당연히 다르겠지만 그 결과를 나머지 연산을 했을 때는 값이 같아질 수 있다. 해시 테이블의 범위가 작다면 매우 높은 확률로 충돌이 발생할 것이다.

충돌을 해결하는 두 가지 방법을 알아보자.
개방주소법과 체이닝이다.

일단 개방주소법 먼저 가볍게 다뤄보자.
충돌은 인덱스가 같아지는 현상을 해결해야 한다. 개방주소법은 이 문제를 굉장히 단순하게 해결한다. 3번 인덱스에서 충돌이 발생했다면 4번 을 보는 것이다.
4번이 꽉 찾다면? 5번 을 본다. 단순하다. 이런 식으로 처리한다.
해싱 성능을 위해 다음 인덱스를 결정하는 많은 방법이 연구된 것 같다. 필요할 때 정말 필요해질 때 알아보자 ...

다음으로 체이닝이다.
체이닝은 해시 테이블의 각 인덱스가 LinkedList를 가리키도록 하는 것이다.
일단 형태는 2차원 배열을 생각하면 된다.
해시 테이블의 인덱스를 찾았다면 이제 key 값으로 해시 테이블의 인덱스 번 째 방에 위치한 LinkedList를 순회하면서 REAL 값을 찾는 것이다.

체이닝은 코드로 옮겨서 확인해보자.

해시 테이블 내부적으로 LinkedList를 key-value 쌍으로 가져야 하니 클래스를 하나 정의한다. 여기 튜플의 key-value 에서는 해싱된 값이 아닌 원래의 값이 저장된다.

class LinkedTuple:
    def __init__(self):
        self.list = list()

    def add(self, key, value):
        self.list.append((key, value))

    def get(self, key):
        for k, v in self.list:
            if key is k:
                return v

다음으로 딕셔너리를 위한 클래스를 정의한다.
이전과 동일하게 내부적으로 해시 테이블을 위한 리스트를 갖고 해당 리스트에 해시 테이블의 크기만큼 위에 정의한 클래스의 인스턴스를 추가해준다.

원래의 key로 LinkedTuple을 조회하고 삽입하는 것 외에는 동일하다.

class Dict:
    HASH_TABLE_SIZE = 8

    def __init__(self):
        self.hash_table = []
        for _ in range(self.HASH_TABLE_SIZE):
            self.hash_table.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % self.HASH_TABLE_SIZE
        self.hash_table[index].add(key, value)

    def get(self, key):
        index = hash(key) % self.HASH_TABLE_SIZE
        return self.hash_table[index].get(key)

테스트

dict = Dict()
dict.put("key1", "value1")
dict.put("key2", "value2")
print(dict.get("key1"))

---

학부생 때 해시 테이블에 대해서 엄청 깊게 이론적으로 배운 기억이 있는데 이론만이 아니라 직접 구현해보면서 배웠다면 훨씬 좋지 않았을까....

해시 테이블 충돌같은거 솔직히 이름을 제외하고 아무런 기억이 없었다... ㅎ