해시 테이블이란?

이번 시간에는 해시테이블을 공부해도록 하죠. 자바스크립트에서 흔히 사용되는 객체는 키 - 값이 하나의 쌍으로 연관되어있습니다. 이렇게 동작하는 방식이 해쉬테이블과 유사합니다.

해쉬테이블도 키를 통해 값을 매핑할 수 있는 자료 구조입니다. 위의 그림을 보면 연필, 볼펜, 샤프, 필통 키가 있고 각각의 키가 해시 함수를 거치게 되면 특정한 인덱스를 갖게 되죠. 이 부분을 조금 더 자세하게 설명해보겠습니다.

number, string, object, array 우리가 컴퓨터에서 보는 모든 것들은 사실 이진수로 이루어져있죠. 즉 모든 것이 숫자라는 것입니다. 따라서 이 것을 10진수로 변환해 10으로 나눠서 나머지를 얻는다면 그게 어떤 것이든 0 부터 9 사이의 값을 갖게 될 것입니다.

이렇게 얻은 0 부터 9를 각각 데이터를 담을 수 있는 바구니라고 생각해보죠. 만약 우리가 숫자 65를 10으로 나머지 연산을 하게 되면 5를 얻게 되죠. 따라서 65라는 데이터를 5번 바구니에 담습니다. 하나 더 해볼까요? 숫자 679를 10을 나머지 연산하면 9를 얻게됩니다. 9번 바구니에 담겠죠?

이렇게 특정 길이의 바구니를 만드는 것을 해시 함수가 하며 바구니 - 데이터로 이루어진 데이터 구조를 해시테이블이라고 합니다.

해시 충돌

그런데 잘 생각해보면 문제가 있죠. 65를 10으로 나누나 75를 10으로 나누나 둘 다 5번 바구니를 가르킵니다. 그럼 둘 다 같은 바구니에 들어가겠죠? 이렇게 해시 함수의 결과 값이 같아서 충돌하는 경우를 해시 충돌이라고 합니다.

충돌 해결하는 방법

자! 그럼 해시 충돌을 해결하는 방법을 살펴봅시다. 여러가지 방법이 있겠지만 여기서는 두 가지를 알아볼게요. 개방 주소법, 분리 연결법 입니다.

개방주소법

해시 충돌이 발생했을 때 비어있는 새로운 주소를 찾아서 충돌된 데이터를 입력하는 방식입니다. 총 4가지 방식이 있습니다.

1. 선형 탐사법

충돌이 발생했을 때 n칸만큼 옆 방으로 이동합니다. 만약 또 충돌이 발생하면 또 그 다음 n칸만큼 옆으로 이동하겠죠.

2. 제곱 탐사법

첫번째 충돌에서는 1^2만큼 두 번째 충돌에선 2^2, 세 번째는 3^2만큼 옆 주소로 이동해서 데이터를 입력합니다.

3. 이중 해싱

앞서 소개한 방법은 1이 반복해서 나오게 될 경우 충돌을 피할 수가 없다는 단점이 있습니다.. 이중 해싱은 이를 해결하기 위해 해시 함수를 이중으로 사용합니다.

최초 해시를 얻기 위해서, 그리고 충돌이 발생했을 경우, 이렇게 두 가지 경우에 해시 함수를 거칩니다.

분리 연결법

개방주소법처럼 옆에 비어있는 공간에 데이터를 입력하는 것이 아니라 해시 테이블 버킷 하나에 링크드 리스트로 값을 여러개 입력합니다. 링크드 리스트에 삽입할 때 맨 뒤보다 맨 앞에 추가하는 것이 더 효율적입니다. 다른 노드를 탐색할 필요없이 입력한 뒤에 포인터만 앞에 있었던 노드로 추가해주면 되기 때문이죠.