[JS] Object vs Map vs Set

알고리즘을 풀다가 너무 궁금해져서 정리하게 되었다. (이전에도 알고 있었지만 이렇게 정리해두지 않으면 날라간다.)

 

Object

C++ 구조체처럼 작동한다. 힙 메모리에 미리 공간을 할당해서 캐싱해버린다. (이 때문에 키 값이 String 혹은 Symbol만 된다.)

접근 속도가 매우 빠르다.

그러나 새로운 키가 추가되거나 삭제되는 순간이 자주 발생하면 Object는 다시 공간을 할당해야 하기 때문에 매우 느려지며 이 과정도 자주 반복되면 그냥 해시 테이블로 만들어버린다. (Object의 장점 소멸)

따라서 키 값은 그대로 있고 값만 바뀌며 빠르게 접근하고 싶은 경우에 사용한다.

Map

내부적으로 연결리스트 + 해시 테이블 구조를 사용한다.

좀 더 자세히 들어가면, 삽입 순서를 기억하는 데이터 배열(연결리스트 역할)과 빠른 탐색을 돕는 버킷 배열(해시 테이블 역할)을 사용한다. 값을 찾을 때는 키를 해시 함수에 넣어 버킷 배열에서 실제 위치(인덱스)를 찾아 이용하고, 순회하는 경우(for...of) 해시 테이블을 거치지 않고 데이터 배열만 순서대로 읽어 내려간다. (빠른 접근 속도 + 순서 보장)

보다시피 Object보다는 접근 속도가 느리다.

그러나 키 값에 String, Symbol뿐만 아니라 Number, 함수 등을 넣을 수 있고 키 값이 자주 추가/삭제 되어도 상관 없다. (속도가 일정하다.)

따라서 키 값으로 String, Symbol이 아닌 다른 타입을 사용하거나 키 값의 추가/삭제가 자주 일어나는 경우 사용한다.

Set

너무나도 잘 알다시피 Set안의 원소는 중복되지 않는다. 그 이유는 Map과 달리 키 값으로 진짜 값을 사용하기 때문이다.

다시 확인하면 진짜 값을 해시 함수에 넣어 해시 값을 만들고 해당 해시 값으로 해시테이블에 접근한다.

이 과정에서 알 수 있듯이 중복처리가 필수적이며 나머지는 같다.

 

 

하하하 해시테이블도 정리해야겠다.

참고로 Map과 Set은 연결 리스트로 되어 있기 때문에 순회가 가능하다. (for... of을 사용할 수 있는 이유)

 

그래서 정리하면

 

1. Object : 데이터 구조가 고정, 빠른 읽기/쓰기가 필요한 경우
2. Map : 데이터의 키 추가/삭제가 빈번, 순서 보장이 필요한 경우 (연결리스트 + 해시 테이블)
3. Set : 데이터 고유성(중복 제거) 보장, 빠른 존재 여부 확인(O(1))이 필요한 경우