[Data Structure] Hash table - 해시테이블, 객체

해쉬테이블은 파이썬에서 사용하는 dictionary, 자바스크립트에서 사용하는 객체와 같다. string 형태의 key와 값을 받아 저장하고, key를 알고 있으면 O(1)의 시간복잡도로 value를 가져올 수 있는 엄청난 자료구조이다! 개념을 명확히 알면 나중에 응용할 때에 더욱 빛을 발하는 자료구조이니 반드시 알아두자.

 

Hash function ( 해시 함수 )

해시함수는 입력받는 key에 따라 특정 index를 반환하는 함수이다. 같은 key에 대해 항상 같은 index를 반환하여야 하고, 최대한 일관성을 유지하는 것이 좋다.

위의 해시함수는 문자열 'cat'이 입력되면 항상 1을 반환하고, 'dog'이 입력되면 2를 반환한다.

이렇게 반환된 index에 입력된 key, value 가 해시테이블에 저장된다.

const hashTable = [ empty, ['cat', catValue],['dog', dogValue], empty];

우리는 key를 이용하여 언제든지 key에 해당하는 value에 접근할 수 있게 된다.

 

그런데 만약, 해시함수를 통해 반환된 index가 같으면 어떻게 될까?

 

 

Hash Table ( 해시 테이블 )

해시 테이블은 해시함수를 통해 반환된 인덱스에 입력된 데이터를 저장하는 자료구조이다. 그러니 당연히 입력, 출력에 똑같이 O(1)의 시간복잡도를 가진다. 하지만, 해시함수가 좀 구려서 입력되는 모든 값에 같은 index를 반환하면 어떻게 될까?

 

const hashTable = [ empty, [['cat', catValue], ['dog', dogValue]], empty, empty];

위 처럼, 하나의 index에 여러개의 key, value가 들어가고 만다! 이렇게되면 우리는 해시함수와는 상관없이 O(n)의 시간복잡도를 가지게 된다. 이럴거면 배열이나 링크드 리스트를 쓰지 왜 해시테이블을 쓰겠는가.

 

이래서 해시함수가 중요하고, 다음으로 중요한 것이 manage collision 이다. 충돌이 발생하는 경우는 위의 그림처럼 해시함수를 통해 나온 인덱스가 같은 곳을 가리키는 경우를 뜻한다. 이 경우는 위의 코드와 같이 하나의 인덱스에 두 개의 key-value pair를 저장하게 된다. 이 때 hashTable[1] 에 들어있는 [['cat', catValue], ['dog', dogValue]] 를 bucket 이라고 부르고, 들어있는 하나의 페어를 튜플이라고 부른다. 튜플은 관련 내용이 많지만 여기서는 다루지 않겠다.

 

이처럼 충돌을 관리하는 방법 중 하나로 버킷과 튜플을 사용할 수 있지만 해시테이블의 본 목적인 시간복잡도 O(1)이라는 취지에는 어긋난다. 그래서 충돌이 발생하지 않도록 해시함수를 잘 구성하고, 해시테이블에 저장된 총 데이터가 해시테이블의 전체 공간 중 특정 비율을 차지하면 해시테이블을 리사이징해서 시간복잡도가 다시 O(1)이 될 수 있도록 변경하는 작업을 해주어야 한다. ( 참고로 일반적인 해시테이블 리사이징의 시간복잡도는 O(n)이다. 그리고 언제나 그렇듯, 그보다 빠른 방법은 존재한다. )

 

리사이징을 통해 저장공간이 많아진 해시 테이블에 기존의 데이터를 다시 해싱하여 ( 해시 함수에 넣어 인덱스를 반환받아 ) 새로운 해시테이블로 거듭나게 된다. 그리고 리사이징된 해시테이블은 본 목적에 맞게 시간복잡도가 O(1)이 된다.

 

JavaScript에서 해시테이블은 객체{} 라는 이름으로 이미 존재한다. 그렇기에 해시테이블을 직접 구현할 때에는 해시테이블 내부에서 객체를 사용하지 않도록 하자.

 

자료구조를 이해할 때에는 직접 한 번 그려보는 게 도움이 많이 된다. 반드시 직접 그려보고 스스로 이해하도록 노력해보자!