[자료구조] HashTable 알아보기 (JavaScript)

해시(Hash)란 ❓

Hash는 hash function에서 얻어지는 값으로서, 유일한 값(반복되지 않는 값)을 저장하기 위한 자료구조입니다.

 

Dictionary(Map) 자료 구조와 같이 key,value의 형태로 저장되며 모든 데이터가 유일한 key를 가지고 있습니다.

 

유일한 key를 가지고 있기 때문에 특정한 값을 아주 빠르게 찾을 수 있다는 특징을 가지고 있습니다.

 

해시가 특정한 값(데이터)를 아주 빠르게 찾을 수 있는 이유는 데이터를 검색할 때 사용할 key와 value가 1:1 매칭으로 존재하기 때문에 O(1)의 시간복잡도를 가지기 때문입니다.

 

Hash Function(해시 함수) 란 ❓

해시 함수란 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말합니다.

 

즉 key를 고정된 길이의 해시로 변경해주는 역할을 하는 함수입니다.

 

해싱(Hasing) 란 ❓

해싱이란 hash function에 문자열 입력값을 넣어서 특정한 값으로 추출하는 프로세스를 의미합니다.

 

Hash Table 란 ❓

 

해시 함수에 key를 줄 경우에 key에 해당하는 index 주소를 반환하고, 주소에 value를 저장하는 원리로 Hash Table을 생성하는데, 바로 이 Table이 Hash Talbe입니다.

 

해시 테이블은 key, hash function, buckets로 구성되어있으며 buckets(또는 slot)는 여기서 실제 값이 저장되는 장소입니다.

 

해시 테이블은 각각의 key값에 해시 함수를 사용하여 배열의 고유한 index를 생성하는데 이 index를 활용하여 값을 저장, 검색, 삭제할 수 있습니다.

 

정리하자면  해시테이블은 해시 함수로 매핑한 key 값을 인덱스로 한 배열 혹은 객체입니다.

 

그렇다면 해시는 JavaScript의 객체(Object)와도 비슷한 방식으로 구현되는 것을 알 수있습니다.

 

그러면 객체와 해시는 같은걸까?

 

엄밀히 말하자면 JS에서의 객체(Object)는 Hash Table이 아닙니다. 자바스크립트 엔진은 객체의 속성을 관리하기 위해 해시 테이블과 비슷한 데이터 구조를 사용하지만, 내부적인 동작 방식과 최적화된 구현은 엔진마다 다를 수 있습니다.

(ES6)부터 도입된 Map, Set, WeakSet, WeakMap과 같은 데이터 구조들은 해시 테이블을 기반으로 구현되었습니다.
이러한 데이터 구조들은 객체보다 다양한 용도로 사용할 수 있고, 특히 Key-Value 형태의 쌍을 저장하고 검색하는 데에 더 효율적입니다.

V8 엔진의 경우 키를 저장하는 방식에 대한 최적화 사항을 개선하여 성능을 높였다는 것이 언급되어 있습니다.

따라서 자바스크립트 객체와 해시 테이블 사이에는 유사성이 있지만 완전히 같지는 않으며, ES6 부터 도입된 데이터 구조들은 내부적으로 해시 테이블을 사용하여 구현되었습니다.

	Object	Map
시간 복잡도	O(1)	O(1)
.get(Key)	X	O
.Key	O	X
[Key]	O	X
Key의 타입	String	Any
순서 보장	X	O
Iterator 구현	X	O

MDN에 따르면 데이터 크기가 크거나, entry들을 추가하거나 삭제하는 빈도가 더 높을 수록 object보다 Map을 사용하는 것이 좋다고 합니다. 

그 외에도 위 표를 보면 Object와 Map의 차이점을 알 수 있습니다.

 

해시 충돌(Collision) ❗

 

앞서 해시 함수를 사용하면서 각가에 대해 key주소를 생성했습니다. 근데 해싱을 한 이후에 두 개의 서로 다른 key가 동일한 지점을 목표로 하는 경우가 있을 경우가 있습니다. 

 

바로 이러한 경우를 해시 충돌이라고 부릅니다.

 

해시 함수를 사용하면  key값을 고정된 길이의 hash문자열로 바꿔주게 된다고 했는데, 만약에 내가 계속 입력하면 입력할 수 있기 때문에 입력값은 무한하지만 hash문자열은 유한합니다.

 

즉 무한한 값(Key)를 유한한 값(Hash)로 표현하게 되면서 서로 다른 두개 이상의 유한한 값이 동일한 Hash값을 가지게 되면서 충돌이 발생하는 것입니다.

 

충돌을 완화하기 위한 방법이 존재하는 데 이 충돌 완화 방법은 다음 포스팅에서 알아보겠습니다.