자바스크립트의 자료구조 2 : 해쉬 테이블(Hash Table)

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 해쉬 테이블(Hash Table)?

앞선 글에서 배열에 대해서 살펴보았다면 이번에는 객체에 대해서 살펴보자. 객체는 Hash Table이라는 자료구조의 종류 중 하나이다. Hash Table은 Key와 Value가 쌍을 이룬 형태로 데이터가 저장되어 있는 자료구조형을 지칭한다. 사실 배열 내 데이터도 Key와 Value로 이루어져 있기는 하나, 배열에서는 Key가 오직 index, 즉 숫자만 가능한 것에 비해 Hash Table에서는 문자열 또한 Key가 될 수 있다.

 

예를 들어 `basket.grapes = 10000` 라는 코드는, 메모리에 basket 이라는 이름의 객체 내에 key가 grapes, value가 10000인 데이터를 저장하도록 지시한다. 따라서 해당 메모리 주소를 참조하면, 이 주소 안에는 key 값인 grapes, value인 10000이 모두 저장되어 있다.

해쉬 테이블의 작업별 시간복잡도

 

2. 해쉬 함수(Hash Function)

Hash Table은 key가 input되면 Hash Function을 이용하여 무작위의 주솟값을 생성한 후, 생성된 주솟값에 key와 value를 저장하는 방식을 취한다. Hash Function의 종류는 다양하지만, MD5 해쉬 함수가 대표적이다. 해쉬 함수는 아래와 같은 두가지 특징을 지닌다.

 

1. 일방향 : key가 input되면 랜덤한 값을 output으로 생성해내는데, 이 랜덤한 output을 기반으로 input이 무엇인지를 알아낼 수 없다.

2. idemponent : input이 동일하면 항상 동일한 랜덤 output이 출력된다. input이 한 글자라도 달라지면 랜덤 output 또한 달라진다.

 

해쉬 함수를 이용하기 때문에 해쉬 테이블은 해쉬 충돌(Hash Collision)이라는 문제가 야기될 수 있다.

 

3. 해쉬 충돌(Hash Collision)

Key와 Value로 이루어져 있는 해쉬 테이블의 특성 상, search, lookup, insert, delete 같은 작업에서 해쉬 테이블은 아주 빠른 속도를 보인다. O(1), Constant Time이기 때문이다. 해쉬 테이블이 이렇게 뛰어난 성능을 발휘하는 자료구조라면, 모든 경우에서 사용하면 좋을 텐데 왜 그렇지 못할까? 바로 해쉬 충돌 때문이다.

 

해쉬 테이블의 가장 큰 단점은, 배열과 달리 자료 구조가 정렬되어 있지 않다는 점이다. 따라서 해쉬 테이블은 메모리 공간에서 주소에 순차적으로 값을 부여하지 않고, random하게 값을 부여하게 된다. 예를 들어 0, 1, 2, 3 총 4개의 메모리 주소가 있다고 가정했을 때, 첫번째 데이터가 0번째 메모리 주소에 들어갔다고 하더라도, 반드시 두번째 데이터가 1번째 메모리 주소에 들어가지 않는다는 점이다. 두번째 데이터의 key값을 해쉬 함수에 넣어서 출력된 결과물에 따라서 랜덤하게 주소가 배정되는 것이다. 따라서 상황에 따라서, 나머지 메모리 주소는 텅 비어 있어도 0번째 메모리 주소에만 수 많은 데이터가 저장되어 있을 수도 있는 것이다. 이러한 현상을 해쉬 충돌이라고 한다. 이곳에서 해쉬 테이블이 자료를 메모리 주소에 저장하는 과정을 볼 수 있다.

해쉬 함수로 인해 해쉬 충돌이 일어나는 사례

위 사진을 보면, John Smith라는 key와 Sandra Dee라는 key가 해쉬 함수에 input 되었을 때, 둘 모두 해쉬 함수의 결과물이 152이기 때문에 메모리 주소 152에 두 개의 데이터가 보관되어 있는 것을 알 수 있다. 즉, 메모리 주소 152에서 해쉬 충돌이 발생한 것이다.

이렇게 충돌이 발생하면 데이터를 읽는 속도가 느려질 수 밖에 없으며, 이 경우 O(n/k) (k는 해쉬 테이블의 크기)가 되며, 상수를 제거하면 결국 O(n)이 된다.

 

4. Map, Set

자바스크립트에서 해쉬 테이블은 Object가 대표적이지만, 다른 프로그래밍 언어에 존재하는 해쉬 테이블의 종류인 Map, Set 또한 ES6 이후 자바스크립트에 추가가 되었다. 이 글에서 자세히 살펴보진 않을 것이다. 간략한 차이점만 짚고 넘어가자.

- Map : 자바스크립트의 객체에서 key는 언제나 문자열만 가능하지만, Map은 key에 함수, 숫자, 배열 같은 타입이 들어오는 것도 가능하다. 또한 객체는 정렬되지 않은 반면, Map은 order가 있다.

- Set : Set은 Map과 거의 유사하지만, 메모리 공간에 value는 저장하지 않고 key만 저장한다는 점이 다르다.

 

5. Hash Table 메소드 구현

Hash Table의 메소드들을 직접 구현하면서 해쉬 테이블의 시간 복잡도를 이해해보자.

// code goes here...

 

6. 해쉬 테이블 결론

- 장점 : Fast Search(배열은 전체를 순회하며 값을 찾아야 하는 반면, 해쉬 테이블은 key를 통해 바로 찾고자 하는 값에 접근이 가능하다.), Fast Insertion and Deletion(해쉬 테이블은 데이터가 정렬되어 있지 않기 때문에, 바로 값을 추가하고 지울 수 있다.), Fast lookup(배열과 객체 모두 index 또는 key를 알고 있으면 되므로 lookup도 빠르다.)

- 단점 : 무작위 주소 할당으로 인한 문제.