[07-1] 해시 테이블(Hash Table)이란? (1)

해시 테이블은 코딩 테스트에서 사실상 필수적으로 나온다. 또한, 굉장히 강력한 자료구조 이다.

사용방법은 매우 간단하지만 언제? 어떠한 상황에서 활용해야 하는가? 를 판단할 줄 알아야 올바르게 본 자료구조를 활용할 수 있다.

 

사실 해시 테이블은 우리가 자주 활용하고 있다. 바로 Dictionary 구조가 해시 테이블이기 때문!

파이썬 코드를 작성하면서 딕셔너리 구조를 최소한 한번은 활용해보았기에 이번 해시 테이블 구조의 친밀감(?)은 다른 파트보다는 수월했다.

 

 

해시 테이블의 구현 방법은 크게 2가지 방법이 있다.

1. Array list: 파이썬의 딕셔너리

2. Find key: 코딩테스트에서 어떻게 딕셔너리를 활용할 지

 

참고용으로,

해시 테이블에서는 충돌이 발생하는데 이를 어떻게 해결할 것인가는 어떤 식으로 해시테이블을 구성했느냐에 따라 달라진다.

- Array list ⇒ Open addressing

- Array list + Linked list ⇒ Seperate chaining

 

해시테이블이란 무엇일까?

빠른 탐색을 위한 자료구조로 key-value의 쌍을 갖는 데이터를 말한다. O(1)

해시 테이블 구조

 

간략하게 정리해본 해시 테이블 구조이다. key-value 쌍으로 저장을 하고 쉽게 생각하면 출석번호, 은행의 번호표 정도로 이해하면 매우 쉽다.

 

def hashFunction(key):
    return key % 6

 

사진에서 인덱스를 부여하는 방법으로 코드 예시를 들어보았다. 나머지를 기준으로 key값이 0이 나오면 0번 인덱스에 들어가면 되는 것이고~ 각자의 위치에 자리잡으면 된다.

 

근데,, 이거 너무 복잡한거 아닌가? 왜 이렇게 까지 해야하지? 만약에 내가 100개를 하고싶으면 100의 나머지로 해야하나? 하는 의문이 들게 되었다.

 

자, 이렇게 하는 이유는 Direct-address Table의 사례를 보면 이해하기 쉽다.

키가 1일때 index 1이고 value에 넣는다면?

Direct address table

 

이렇게 하면 어떤 문제가 발생하는가? 일단, 보기에는 아주 깔끔하다! function도 없고!

하지만 이 최대의 단점은 바로 효율성의 문제 이다.

 

만약에 4대의 자동차를 자동차번호와 차주를 해시 테이블로 구성하려고 하는데, 자동차 번호를 index(=key)로 해버린다면?

1111 김씨, 7777 이씨, 8888 박씨 , 9999이씨

이렇게 입력하게 되면 1111 부터 9999까지 몇 천개의 메모리가 낭비가 된다. 이 얼마나 비효율적인가?

 

또한, 만약에 key가 문자라면? 아이디 일 수 있지 않은가?

Kim: 김씨, Lee: 이씨

이렇게 되었다면 Kim, Lee를 인덱스로 활용할 수 없게 되는데.. 어떻게 해야하지?

 

이러한 문제를 해결하기 위해서 해시 테이블을 만들었다.

 

정리하자면, 키값을 바로 인덱스로 쓰지 못하고 hashfunction을 활용해서 간접적으로 테이블을 구축하는 것이다.

문자열이든~ 너무 긴 숫자든~ 신경안쓰고 인덱스로 바꿔서 key-value 쌍으로 만드는 것이다.

 

하지만 해시 테이블 역시 문제가 있다.

만약에 key%9라면 총 9칸밖에 못들어가는데, 그 와중에 겹친다면? 

0번 인덱스, 4번 인덱스, 다시 0번 인덱스가 나와서 0에 들어가야 한다면? 이미 0번 인덱스에 key-value가 있는데?

 

이를 바로 Collision(충돌)이라고 한다!

앞서 정리한 Open addressing 을 살펴보자

Open addressing

 

앞서 본 사례에서 8번 군만두가 들어와 2번 인덱스에 들어가야한다. 하지만 이미 짜장면이 있다!

이럴 때 그 다음으로 가면 되지~ 하고 3번으로 가는데 어? 또 있네? 그러면 그 다음으로 가지 뭐~

하는 것이 바로 Open addressing이다.

 

Open addressing에는 바로 다음으로도 갈 수도, 2칸 뒤로 갈 수도, 3칸, 4칸... 제곱 등 다양한 방법이 있다.

즉, 쉽게 말하면 다음 칸으로 가지 뭐~ 다른 곳으로 가지 뭐~ 하면 Open addressing 인 것이다!

 

남은 설명은 다음편에!