JavaScript에서 Map ( 자료구조, Not 고차함수)을 파헤쳐보자 - 작성중

이 글의 시작은 매우 간단했다. JavaScript로 문제를 코딩테스트 풀다가, Map이라는 자료구조를 사용할 일이 생겼다.

 

복잡한? 기능들을 사용하기는 귀찮아서 Object로 문제를 해결하려했는데, 그럼 시간 복잡도에 문제가 없을까?라는 생각이 들었다.

 

Stackoverflow에서 찾아보니, Object도 hash로 이루어져있어서 find에 O(1)의 시간 복잡도를 가진단다.

 

stackoverflow.com/questions/12241676/javascript-objects-as-hashes-is-the-complexity-greater-than-o1

JavaScript Objects as Hashes? Is the complexity greater than O(1)?

 

여기서 의문이 시작됐다. JavaScript에서 Object와 Map은 어떻게 이루어져있을까?? 물론 인터프리터, 컴파일러, 엔진에 따라 다르겠지만,내가 자주 쓰는 Node를 기준으로 어떻게 되어있는지 궁금했다. 이에 대해 개인 Notion에 러프하게 정리했었는데, 블로그에 깔끔히 정리해보려한다.

 

Map과 HashMap

먼저 Map과 HashMap에 대하여 알고 있어야 이해하기가 편할 것 같다.

 

HashMap = unordered Map

• HashMap은 key 와 value 를 hash 알고리즘에 의해 구현

• Hash 알고리즘으로 넣으므로 전체가 어떤 특정한 규칙으로 정렬이 되어 있지 않다.

• hash_map은 find에 이상적으로 O(1)의 시간을 소요한다.

• 하지만 hash_map은 실제로는 hash table의 크기에 반비례하는 O(n)의 시간을 소요한다.

  • 예를 들어 1000개 저장하는데, 테이블 크기가 100이라면, 시간은 10만큼 걸릴 것이다.

Map ( Tree Map ), Ordered Map

• Map( Tree Map)은 보통 red-black tree 알고리즘을 이용하여 구현

• Tree의 규칙대로 들어가므로, Order되어 있다, 즉 정렬되어 있다.

• Map( Tree Map )을 쓰는 경우, 최악의 경우 O(n), 최상의 경우 O(logn)의 시간복잡도

  • 이진 트리의 원리에 따라 일렬로 이루어졌을 경우 O(n)이 걸리고,
  • 균등하게 나누어져 있다면 O(logN)이 걸릴 것이다.