자바스크립트를 예제로 하는 자료구조와 알고리즘 6 - 해시 테이블(Hash Tables)

자바스크립트에서 해시 테이블은 바로 객체다.

(자바에서는 HashMap, 파이썬과 C#에서는 Dictionary라고 부른다.)

엄청 빠른 속도를 자랑하기 때문에 두루두루 쓰인다.

 

const object = {
  1: '가',
  2: '나',
  3: '다'
}

 

해시 테이블은 데이터를 저장할 때 key와 value를 한 쌍으로 한다.

해시 테이블이 key를 받아 Hash Function에 통과 시키면

Hash Function은 value를 메모리 상 어디에 저장할지 알려준다.

 

마찬가지로 데이터를 가져올 때에도 해시 테이블이 key를 받아

Hash Function을 거쳐 key에 해당하는 value의 위치를 찾아 value를 반환한다.

 

Hash Function은 이렇듯 같은 인풋을 넣으면 같은 아웃풋을 보장하는 특징이 있다.

이 Hash Function 덕에 insert, lookup, delete와 같은 메소드의 시간 복잡도는 모두 O(1)이다.

(최악의 경우 O(n)이 나올 수도 있지만 거의 드문 경우라 일반적으로 O(1)로 취급한다.)

 

사실 key를 받은 Hash Function이 반환하는 값은 index이고 이 index에 해당하는 배열 공간에 value를 저장한다.

또한 Hash Function은 내부적으로 index의 값이 배열의 길이를 넘어가지 않도록 되어 있다.

 

때문에 다른 key를 Hash Function에 넣었음에도 같은 index가 나오는 경우가 있는데 (Collision)

이런 경우 링크드 리스트를 이용한 Chaining 방식이나

데이터의 빈 곳을 찾아 저장하는 Open Addressing이란 방식 등으로 중복 문제를 해결한다.