해시 테이블(Hash Table)이란?
선형 자료 중에 하나인 해시 테이블은 키와 값을 받아 키를 해싱(Hashing)하여 나온 index 에 값을 저장하는 선형 자료구조로써, 삽입의 시간 복잡도는 상수시간 O(1) 소요되고 삭제, 탐색의 시간 복잡도는 키를 알고 있다면 상수 시간 O(1)이 소요된다. 고등 학생 때 사용하던 사물함과 비슷한다. 사물함의 각 칸에는 이름과 번호가 있기 때문에 쉽게 위치를 찾을 수 있기 때문이다.
각 테이블에 해당하는 index 를 해시 테이블에서는 bucket 이라고 부른다. 그리고 테이블의 각 요소는 키와 값을 둘다 저장하고 있어야 한다. 또한, 해시는 쉽게 연상 가능한 해시 브라운에 그 해시가 맞다. 해시 브라운에 해시는 고기와 감자를 잘게 다져 요리한 것을 의미한다. 해시 테이블에 해시도 입력 받은 key 를 잘게 잘라 숫자로 만든다는 점이 비슷하다.
해시 함수(Hash Function)
해시 함수는 입력 받은 값을 특정 범위 내 숫자로 변경하는 함수이다. 해시 함수는 특정한 구현 방법이 있지는 않다. 따라서 개발자 마음대로 구현하면 된다. 예를 들어 단순하게 구현한다면 입력받은 문자열을 각 문자열에 아스키 값을 더한 것으로 해시를 정할 수 있다.
이렇게 해시 함수를 이용한 해시 테이블은 완벽해 보이지만 문제점이 하나 있다. 해시 함수의 결과가 동일하여 겹치는 경우이다. 이를 해시 충돌이라고 부른다.
해시 충돌(Hash Collision)
해시 충돌을 해결하기 위한 방법은 총 4가지가 있다.
선형 탐사법
첫번째 방법은 굉장히 단순한 방법으로 만약 충돌이 발생한다면 단순히 index 한칸 옆으로 이동하는 방식이다. 이 방법은 개방 주소법이라는 해결 방법 중 하나로, 선형 탐사법이라고 부른다. 단순하지만 특정 영역에 데이터가 몰릴 수 있는 단점이 있으며, 이동한 버킷에서 또 충돌이 발생한다면 충돌이 발생하지 않을 때까지 이동한다. 그래서 이름 그대로 최악의 경우에 탐색에 선형 시간이 걸릴 수 있다.
제곱 탐사법
그래서 특정 영역에 데이터가 몰리지 않게끔 제곱 탐사법이라는 방식을 사용할 수 있다. 제곱 탐사법은 충돌이 발생하면 충돌이 발생한 지점에서 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다. 충돌이 발생하는 횟수가 클수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다 덜하다는 차이점이 있다.
이중 해싱
세번째 방법은 또 다른 해시 함수를 사용하는 방법이다. 충돌이 발생할 경우 기존 해시 함수가 아닌 두번째 해시 함수를 이용하여 새로운 index 를 만들어낸다. 또 충돌이 발생하면 충돌이 발생하지 않을 때까지 두번째 해쉬로 index 를 계속해서 만들어낸다.
분리 연결법
마지막은 분리 연결법이라는 방법이다. 앞서 소개한 3가지 방법과는 다르게 충돌이 발생할 경우 다른 index 로 이동하지 않는다. 대신 해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버킷에 그대로 요소를 추가한다. 대신 이 방법은 최악의 경우에 하나의 버킷이 무한정 늘어날 수 있는 단점이 있다.
해시 테이블의 사용
하나의 예시로 설명하자면, 우리가 학생 정보를 관리하는 소프트웨어를 하나 만들어낸다고 가정해보자. 어떻게 만들어야 학생 정보를 빠르게 기억하고 찾을 수 있을까? 먼저 연결 리스트를 사용할 수 있다. 학생을 추가하거나 제거하는데 빠르지만 찾을때는 선형시간 O(n) 만큼 시간 복잡도의 시간이 소요된다. 그래서 배열을 이용할 수 있지만 만약 index 를 모를 경우에는 모두 찾아 봐야 하기 때문에 탐색에 선형 시간 O(n)이 걸린다.
따라서, 이런 경우에는 해시 테이블을 사용하는 것이 유리하다. 이름을 키로 하여 탐삭과 삽입, 삭제가 모두 상수 시간 만에 끝난다. 최악의 경우에는 탐색에 선형시간이 걸릴 때도 있지만 연결리스트나 배열보다는 안정적이라고 할 수 있다.
자바스크립트에서 사용법
JavaScript Array = Hash Table
자바스크립트에선 해시 테이블의 사용이 너무 간단하다. 우선 우리가 사용하는 배열은 실제로는 객체 타입이라 해시 테이블처럼 사용할 수 있다. 단 이 방법은 올바른 사용법이라고 할 수는 없기 때문에 추천하지는 않는다.
const table = []; table[‘key’] = 100; table[‘key2’] = ‘Hello’; console.log(table[‘key’]) // 100 table[‘key’] = 349; console.log(table[‘key’]) // 349 delete table[‘key’]; console.log(table[‘key’]); // undefined
JavaScript Object = Hash Table
다음으로 객체를 이용할 수 있다. 이 방법은 제일 간단한 방법이라고 볼 수 있다.
const table = {}; table[‘key’] = 100; table[‘key2’] = ‘Hello’; console.log(table[‘key’]) // 100 table[‘key’] = 349; console.log(table[‘key’]) // 349 delete table[‘key’]; console.log(table[‘key’]); // undefined
Map
별로로 Map 객체로 사용할 수 있다. Map 은 set 함수를 사용하여 값을 넣고 get 함수를 이용하여 값을 찾을 수 있다. 기존 객체와는 다르게 키 값으로 오브젝트나 배열같은 복잡한 타입도 키로 사용할 수 있다. 객체에서 들어오는 값이 정수가 아닌 경우 전부 문자열로 바꿔버리기 때문에 다양한 타입을 넣고 싶다면 Map 을 이용하느 것이 유리하다. 그리고 또 다른 장점으로는 여러 편한 메서드를 제공해주고 순회를 편하게 할 수 있다.
Set
또 다른 해시 테이블로 Set 을 사용할 수 있다. set 은 키와 값이 동일하게 저장되는 방식을 채택하고 있다. 일종의 집합 연산이라고 볼 수 있다. 따라서 중복된 내용을 전부 제거될 때 사용할 수 있다.
