해쉬(Hash)

1. 해쉬(Hash) - 해쉬란?

• 해쉬란 임의의 크기의 데이터(Key)를 고정된 크기의 값(Value)로 바꾸어 저장하는 것.
• Key에 대한 Value를 구하는 과정을 해싱(Hashing)이라고 하고, 이 때 사용하는 함수가 해쉬 함수이다.
• 해쉬 함수를 이용해서 변환한 값을 인덱스로 하여 key와 value를 저장하는 자료구조를 해쉬 테이블이라고 한다.
• Value 자체를 인덱스로 사용하기 때문에 시간복잡도는 O(1)이다.

위의 내용은 해쉬에 대한 간단한 내용 정리이다. 아는 사람이 보면 쉽지만, 모르는 사람이 보면 무슨 소리인가 싶은 말들이다. 그래서 예시를 들어 설명해보겠다.

다음과 같이 N개의 카드번호와 사람의 성이 적혀있는 데이터가 있다고 할 때, 카드번호가 주어지면 그에 맞는 사람을 찾아내는 시간복잡도는 O(N)이다. 근데 이 N이 정말 굉장히 크다고 하면, O(N)은 느린 속도이다. 그렇다면, 어떻게 더 효율적으로 찾을 수 있을까?
위에 적혀있는 해쉬에 대한 내용을 읽어보면 어느정도 감이 잡힌다. 카드 번호를 인덱스로 사용하면 O(1)에 카드번호와 대응되는 사람을 찾을 수 있다. 다만, 카드번호가 16자리이기에 10^16개의 배열이 필요한데, 크기가 너무 커서 불가능하다. 그래서 생각할 수 있는 방법은 카드번호를 인덱스로 쓰지만 앞 4자리만을 이용하여 인덱스로 사용하는 것이다. 그림으로 보면 아래와 같다.

처음에 해쉬에 대해서 정리한 내용 중 해쉬함수는 이 예시에서는 16자리의 카드번호를 앞의 4자리로 반환해주는 함수이고, 해쉬 테이블은 위 그림과 같이 해쉬 함수를 이용하여 정리한 테이블을 의미한다.

2. 해쉬(Hash) - 충돌(Collision)

해쉬는 충돌이라는 큰 문제가 있다. 충돌이란 두 입력 값에 대해 동일한 출력 값이 나오는 것이다. 위의 예시에서는 나타나지 않았지만, 만약 카드번호가 엄청 많아져서 앞의 4자리가 겹치는 번호가 생겼다고 하면 그것이 충돌이다. 예를 들자면, '1385 4985 6515 2199 Lee' 와 '1385 9548 2165 8455 Kim'를 전부 해쉬 테이블의 인덱스 1385에 넣고 싶지만 그럴 수 없다는 것이다. 그렇다면 이를 어떻게 해결해야할까?

3. 해쉬(Hash) - 충돌을 해결하는 방법

대표적으로 크게 두 가지 방법이 있다. Open addressing과 Chaining이다. 먼저 Open addressing을 살펴보자.

3-1. Open addressing
: Oepn addressing은 데이터를 저장하는 인덱스를 바꾸는 방식이다.

다음 그림과 같은 상황이라고 해보자.

먼저 Lee를 테이블에 넣고, Kim을 넣어야하는데 이미 1385칸을 Lee가 점유했다. 1385칸에 기록할 수 없으므로 한 칸 오른쪽인 1386칸에 Kim을 넣는다. 같은 방식으로 1387칸에 Kwon을 넣는다. 그림으로 나타내면 다음과 같다.

맨 처음에는 해쉬 테이블에 이름만 썼지만, 이 경우에는 카드번호를 적어주지 않으면 구분할 수 없으므로 카드번호도 함께 기록해준다.
Open addressing에서 예시와 같이 1칸씩 옆으로 옮기는 경우를 Linear probing이라고 한다. 이 방식 이외에도 옆으로 이동하는 방식에 따라 여러가지 방법이 있다.

 

3-2. Chaining
: 체이닝은 해쉬 테이블에서 한 인덱스에 한가지 원소를 담고 있는 것이 아니라 연결리스트를 이용해 여러 원소를 담고 있는 방식이다.

그림으로 간단하게 표현해보겠다.

나중에 들어올 데이터를 앞에 붙여야 O(1)으로 시간복잡도에서 손해를 보지 않는다.