[자료구조] 해시 테이블

해시 테이블

해시 테이블은 key-value 시스템을 이용하여 데이터를 저장하는 자료구조다.
해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 그 index에 각각의 value들을 저장한다.

key를 index로 변환할 때는 해시함수가 사용된다.

** 해시함수: 입력받은 값을 특정 범위 내의 숫자로 변경하는 함수를 말한다.

 

간단하게 예를 들면

pizza, cake, taco는 key 이고, 이 메뉴들의 가격이 value라고 하면

각 key들을 hash function에 넣어 구한 값(=Hasing해서 나온 값)이 index가 되고, 이렇게 구한 인덱스에 value를 저장한다.

이 배열이 해시 테이블이다.

해시테이블에서는 index를 bucket이라고 부르며 각 요소에는 key와 value를 모두 저장한다.

 

 

시간 복잡도

삽입의 시간 복잡도는 O(1)이고

key를 알고있다면 삭제, 탐색도 역시 O(1)시간이 소요된다.

 

 

해시 충돌 Hash Collision

위에서 언급했듯이 해시 함수를 이용하여 인덱스 값을 구할 때, 만일 해싱된 값이 중복되게 나올 경우 이를 해시 충돌이 발생했다고 한다.

해시 충돌을 해결하는 대표적인 4가지 방법은 다음과 같다.

 

  1. 선형 탐사법
    충돌이 발생하면 한 칸 옆으로 이동한다. 이동했을 때 또 충돌이 난다면 충돌이 발생하지 않을 때까지 이동하는 방법

    따라서, 최악의 경우 탐색에 O(n)시간이 걸릴 수도 있다.

 

  2. 제곱 탐사법

    충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆 칸으로 이동하는 방법

  3. 이중 해시

    충돌이 발생하면 다른 해시함수를 이용하여 index를 구하는 방법.
    또 충돌이 발생하면 충돌이 발생하지 않을때 까지 두번째 해시로 인덱스를 만들어낸다.

 

  4. 분리 연결법

    위 3가지 방법과는 다르게 충돌이 발생할 경우, 다른 인덱스로 이동하지 않는다.

    대신 해시테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버켓에 그대로 요소를 추가하는 방법이다.
    이 방법은 최악의 경우 하나의 버켓이 무한정 늘어날 수 있다는 단점이 있다.

 

해시 테이블 어디에 사용할까?

탐색에 상수시간에 걸리므로 **탐색**이 많이 일어나는 경우에 적합하다.

(해시 충돌로 인해 최악의 경우 선형시간이 걸릴 수 있지만 그래도 배열로 저장했을 때보다 속도면에서는 안전)

 

 

파이썬으로 해시테이블 구현하기

1. Dictionary타입으로 해시테이블 구현

  내부적으로 동작하는 건 조금 다르지만 사용법은 거의 동일하다.

table = {}  # 해시 테이블

table['key'] = 100
table['key2'] = 'hello'

print(table['key'])
>> 100

table['key'] = 300

print(table['key'])
>> 300

del table['key']

print(table['key'])
>> 에러 발생

 

2. set타입으로 해시테이블 구현

  set을 사용하면 key와 value가 동일하게 저장되는 방식으로 구현할 수 있다. 또는 집합이라고 볼 수도 있다.

  중복된 내용을 전부 제거할 때도 사용할 수 있다.

table1 = set()

table1.add('key')
table1.add(100)

table2 = set()
table2.add('key')
table2.add('hello')

print(table1 & table2)  # 교집합
>> {'key'}
print(table1 | table2) # 합집합
>> {'key', 100, 'hello'}
print(table1 - table2)  # 차집합
>> {100}