[자료구조] Hash Table(해시테이블)

Hash Table(해시테이블) 이란?

1. 기본 개념

기본 개념은 매우 쉽습니다.

위 그림처럼 책이 아무렇게나 꽂혀있는 것 같아도, 서점에 가면 누구나 책을 쉽게 찾을 수 있도록 '위치 번호'가 있습니다. 이것을 해시테이블의 Key 라고 하고 내가 찾을 도서를 Value 라고 보면됩니다. 하지만 도서와 다르게 Hash Table은 1:1 구조 입니다.

해쉬 테이블은 그 위치번호와 도서 이름이 묶여있는 표라고 생각하시면 됩니다.

아래와 같은 개념도 역시 도움이 될것입니다.

 Andy, Brian, Chris, Dennis, Emma는 앞글자를 Key 값으로 해서 테이블이 생성되었습니다.

보통 꼬리에 꼬리를 무는 질문이 많은 기술면접 같은 경우는 Hash Table 또는 Tree 에서 많은 질문을 합니다. 아주 많은 질문을 할 수 있거든요. 이렇게 면접때 질문으로도 많이 나오고, 사용하는 곳도 방대하며, 이 개념이 나온지 반세기가 지났는데도 이것보다 나은 방법을 찾지 못했을만큼 빠르고 획기적인 방법입니다. 기본적으로 엔지니어라면 배우고 또 배우고 또 배우는 개념이고(저처럼 계속 까먹어서?.. 아마도..) Hash Function을 만드는 기술은 날로 발전합니다. 

2. 용어

Hash(해시) : 어떠한 값을 일정 길이로 변환하는 해우이

Hash Table(해시테이블) : 키 값을 가지고 해당 데이터에 직접적으로 접근이 가능한 데이터 구조

Hashing Function(해시함수) : 해당 데이터의 위치를 찾을 수 있는 Key를 만드는 함수

Hash Value or Hash Address(해시값 또는 해시주소) : Key를 해시함수로 연산하여 Value를 알아내고, 이를 기반으로 해시 테이블에서 해당 Key에 대한 데이터 위치를 일관적으로 찾을 수 있도록 함.

Slot(슬롯) : 한개의 데이터를 저장할 수 있는 공간(해시테이블은 1:1 구조)

3. 파이썬에선 어떻게?

파이썬에서는 따로 해시테이블을 작성할 필요는 없고 딕셔너리를 사용하시면 됩니다.

4. 좋아 보입니다. 그죠? 단점도 있습니다.

데이터들이 종속관계거나 상하관계일 경우에는 사용되지 않는 데이터 구조입니다.
전화번호부에는 사용하기 좋지만, 회사 조직도에는 사용하기에 껄끄러운 자료 구조 입니다.

공간 효율이 떨어집니다. 데이터가 없는데도 미리 저장공인이 있어야 하며, 없으면 데이터가 들어갈 자리가 없으니 에러를 뱉어 내겠지요?

잘 짜여진 Hash Function 이면 좋겠지만, 완벽한 해시 함수는 없습니다. 언제나 Collision(충돌)이 생기기 마련이고 충돌이 생기더라도 한개의 함수에 의존해야 합니다. 이는 뒤에 후술 하겠습니다.

5. 해시 충돌(Hash Collision)에 대해 설명

이론적으로, 해시 테이블은 삽입/삭제/검색 과정에서 O(1)의 시간 복잡도를 가집니다. 물론 여기서 Hash Function의 복잡도는 제외합니다. 왜냐하면 키값만 알면 내가 원하는 데이터에 바로 접근할 수 있기 때문이죠. 하지만 위에서 보았듯, Andy와 Andrew가 들어가면 A 키 에 2개의 Value 가 생깁니다. 이것이 해시 충돌입니다. 해시함수가 아무리 완벽해도 생길 수 밖에 없습니다.

해결책:

(1) Chaining(체이닝)

말그대로 연결해 주는 것 입니다.

위를 보면 John Smith와 Sandra Dee의 해시가 충돌되었고 John Smith에서 Sandra Dee로 LinkedList가 만들어진 것을 볼수 있습니다. 

이 기법을 사용하면 

• 해시함수의 의존도가 비교적 낮아지고
• 상대적으로 메모리 사용량이 낮고 공간을 확보할 필요가 없지만,
• 클러스터 현상이 생겨 검색속도가 낮아질 수 있고
• LinkedList 공간이 따로 필요하다.

**클러스터 현상 : 데이터 들이 일부 해시테이블 위치에 쏠리는 현상

(2) Open Address(개방주소법)

위에 Hash Address/Hash Value 용어를 설명해 놓은 곳에 'address' 라는 말이 있습니다. 개방주소법은 해당 주소를 개방한다~ 라는 의미. 체이닝처럼 연결리스트를 만드는 것이 아니라 그냥 비어있는 곳에 가서 데이터를 넣는 방법입니다.

그럼 어떻게 찾나요?

일정한 규칙에 따라 비어있는 슬롯에 넣는 것이지 마구잡이로 넣는 것은 아닙니다.

개방주소법에도 여러방법이 있습니다.

• Linear Probing(선형탐색) : +n개를 건너뛰고 비어있는 해시에 데이터를 저장한다.
• Quadratic Probing(제곱탐색) : 충돌 후 해시를 제곱하여 해당 해시에 저장한다.
• Double Hash(이중해지) :  다른 해시 함수를 한 번 더 써서 해시한다(해시 함수 2개)

개방 주소법은

• 별도의 저장공간이 필요없어 별다른 작업이 필요치 않으나,
• 해시 함수에 따라 성능 차이가 생길 수 있고
• 데이터 길이가 많이 늘어나는 것에 대한 별도의 준비를 해야 합니다.

6. 가장 이상적인 해시 함수를 만드는 방법

우선, 3가지 조건이 있어야 합니다. 

• 일정 길이로 반환할것!
• 연산에 유리하도록 빠르고 쉬울 것!
• 유니크한 값을 반환 할 것!

For루프나 While 루프를 사용하지 않을 수 는 없겠지만, 많이 쓰면 취약할 수 있습니다.

names = ['Andy', 'Brian', 'Chris', 'Dennis', 'Emma', 'Andrew']
for name in names:
    hashed = ''
    # 10000000007 이라는 소수로 나누어 줄겁니다.
    divided_by = 10000000007

    for letter in name:
        hashed += str(ord(letter))
        # ord는 string을 ASCII코드로 바꾸어 줍니다(A는 65고 a는 97입니다), 
        # zfill로 자릿수를 맞춥니다
    hashed = str(int(hashed) % divided_by).zfill(len(str(divided_by)))
    print(hashed)


>>> 05110100079
>>> 01410592483
>>> 04114058145
>>> 00062434338
>>> 06910910997
>>> 00068524049

위는 어떤가요? 또한, 파이썬은 Built-in 함수로 hash()를 제공합니다. 

print(hash('Andy'))
print(hash('Andy'))

>>> 5926023110164343275
>>> 5926023110164343275

하지만, 같은 객체만 같은 값을 반환합니다. 계속 돌려보면 항상 다른 값이 산출됩니다. 글자가 같다는 것과 객체가 같다는 것은 다른 말 입니다. 디자인패턴의 Singleton 을 제외한 모든 객체는 실행할때마다 새로 만들어 집니다. 파이썬의 대표적인 Singleton Pattern 은 'None' 입니다.

print(hash(None))
print(hash(None))

>>> 102527053
>>> 102527053

Singleton 은 언제나 같은 객체로 유지되므로 항상 같은 숫자가 나옵니다. None의 경우 1000만번을 돌려도 같은 값이 나옵니다.

문득 파이선Tip:
PEP8에 따르면 싱글턴 패턴끼리 비교를 하려면 'is'를 쓰라고 하고 있습니다. 아래와 같이요. 이건 디자인 패턴에서 추가로 다루겠습니다.

if empty_list == None: (X)

if empty_list is None: (O)

7. 그래서 어디서 쓰이나요?

• 블록체인!!!
• 비밀번호 저장!!!