[JS] 해시맵(HashMap) with Javascript

해시테이블은 Insertion, Search, Deletion에서 평균적으로 O(1)의 시간복잡도를 갖는다. 따라서 매우 빠르게 데이터를 저장하고 탐색, 삭제할 수 있는 효율성이 좋은 자료구조이다. 관련 개념은 다음 포스트를 참고하자.

오늘은 자바스크립트에서 해시테이블을 이용하는 방법을 정리해 보려 한다.

자바스크립트에서 해시테이블은 Map, Object, Set이 있다. 본래 자바스크립트에서 해시테이블 자료구조는 Object가 대표적이었으나, ES6에서 Map과 Set이 추가되었다고 한다.

대표적으로 해시맵이라고도 불리는 Map에 대해 정리해 보려 한다.

Map 객체

Map 객체는 key-value로 이루어진 해시테이블이다.
주요 함수는 다음과 같다.

• set(): key-value pair를 map에 삽입
• get(): key값으로 value를 찾아 리턴
• has(key): map에 해당 key의 value 존재 여부 확인
• map.size(): map의 크기
  • key에 들어갈 수 있는 자료형은 number, string, function, object, NaN 등이 가능하다.

Map 객체 생성

var map = new Map();

Map 탐색

//key, value 쌍으로 출력
for (let [key, value] of map) {
  console.log(key + ' = ' + value)
}

//key만 출력
for (let key of map.keys()) {
  console.log(key)
}

//value만 출력
for (let value of map.values()) {
  console.log(value)
}

Two sum 문제 풀이

Hash Table 자료구조를 이용하여 리트코드 Two sum 문제를 풀었다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    //map 객체 생성
    var map = new Map();
    //탐색 시작
    for (let i=0; i< nums.length; i++){
        //map에 target-nums[i]가 key로 저장되어 있다면 리턴
        if (map.has(target - nums[i])){
            //현재 탐색 중인 i보다 map에 저장된 인덱스가 앞쪽에 있으므로 다음과 같이 출력 
            return [map.get(target-nums[i]), i]
        }
        //아니라면 map에 요소 저장 
        map.set(nums[i], i)
    }

    return []

    
};