[개발 공부 113일차] Map과 Set 딥 다이브

< 목차 >
0. Map과 Set 딥 다이브 계기
1. Set
2. Map
3. Set과 Map 차이
4. Set과 Map, 일반 객체의 차이점
5. 왜 일반 객체는 키가 문자열로 변환되는 거고, Map은 객체나 배열도 키로 저장되게끔 설계된 걸까?

 

 

0. Map과 Set 딥 다이브 계기

 

여느 때처럼 알고리즘 문제를 풀기 위해 돌아다니던 중, '캐시'라는 문제를 발견했다.

기업에서 실제로 낸 코테 문제를 좋아하는 나는 어렵든 말든 일단 도전해봤다.

 

중요한 건... 문제가 이해되지 않는다는 것이다

 

LRU랑 cache hit, cache miss가 뭔지 도통 전혀 모르겠어서 다른 분의 풀이를 보며 찬찬히 이해하기 시작했다.

 

function solution(cacheSize, cities) { // DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정
    let answer = 0;
    let cache = [];
    
    if (cacheSize === 0) return cities.length * 5; // 캐시 크기가 0인 경우는 따로 처리
    
    while (cities.length) {
        const city = cities.shift().toLowerCase();
        
        if (cache.includes(city)) {
            cache.splice(cache.indexOf(city), 1);
            cache.push(city);
            answer += 1;
        } else {
            if (cache.length === cacheSize) {
                cache.shift();
            }
            cache.push(city);
            answer += 5;
        }
    }
    
    return answer;
}

 

코드는 대략 이해가 되었다.

이것보다 더 잘 작성하려면 어떻게 해야 할지 의문이 든 나는 바로 AI에게 리팩토링 해달라고 요청한 뒤, 다음의 코드를 받았다.

 

function solution(cacheSize, cities) {
    let answer = 0;
    const cache = new Map();  // LRU를 관리할 Map 사용

    // 캐시 크기가 0인 경우, 모든 요청은 캐시 미스가 발생하므로 총 실행시간은 cities.length * 5
    if (cacheSize === 0) return cities.length * 5;

    for (const city of cities) {
        const cityLower = city.toLowerCase();

        if (cache.has(cityLower)) {
            cache.delete(cityLower);  // LRU 정책에 따라 기존 위치 제거
            answer += 1;  // 캐시 히트일 경우 실행시간 1
        } else {
            if (cache.size === cacheSize) {
                const firstKey = cache.keys().next().value;
                cache.delete(firstKey);  // 가장 오래된 항목 제거
            }
            answer += 5;  // 캐시 미스일 경우 실행시간 5
        }

        cache.set(cityLower, true);  // 항상 최신 항목을 삽입
    }

    return answer;
}

 

Map이 생겼다.

알고리즘 문제를 풀 때, 종종 다른 분들의 코드를 읽곤 하는데 그때마다 Map과 Set으로 문제를 푸는 분들을 목격하곤 했다. 그동안 Map과 Set을 잘 몰랐던 나는, 코드 이해는 안 하고 그냥 '저렇게도 풀 수 있구나' 하고 넘어갔다.

 

그래서 오늘은 내가 모르는 Map과 Set에 대해서 알아보기로 했다.

다만 좀 깊게 들어간..

 

 

 

1. Set

: '중복되지 않는 고유한 값(value)들의 집합'을 저장

즉, 같은 값이 여러 번 들어갈 수 없고, 각 값이 유일하다.

 

 

특징

• 한 번 넣은 값은 다시 추가되지 않음
• 값의 순서는 중요하지 않음 (삽입된 순서 유지가 가능하지만 순서를 관리하기는 어려움)
• 빠른 조회 가능 (시간 복잡도: O(1), 검색 속도 빠름)

 

 

e.g.

const mySet = new Set();

mySet.add(1); // 값 추가
mySet.add(2);
mySet.add(2); // 중복된 값이므로 무시됨
console.log(mySet); // Set { 1, 2 }

mySet.delete(1); // 값 삭제

console.log(mySet.has(2)); // 값이 있는지 확인, true
console.log(mySet.has(3)); // false

 

 

2. Map

: 키(key)와 값(value)의 '쌍'으로 데이터를 저장

 

키를 이용해 값을 조회해, 효율적으로 찾을 수 있다.

Key에 모든 자료형(객체, 배열, 함수)을 저장 가능한 게 일반 객체와의 차이점이다.

 

 

특징

• 키(key)와 값(value) 쌍으로만 저장 가능
• 키 중복 허용 안 됨 (새로운 값을 저장하면 기존 값을 덮어씀)
• 삽입 순서를 기억함 (데이터를 추가하거나 제거할 때 활용하면 좋음)
• 빠른 키 조회 (시간 복잡도: O(1))

 

 

e.g.

const myMap = new Map();

// 키-값 쌍 추가
myMap.set('name', 'Alice');
myMap.set('age', 25);

console.log(myMap); // Map { 'name' => 'Alice', 'age' => 25 }

// 키에 해당하는 값 조회
console.log(myMap.get('name')); // Alice

// 키가 있는지 확인
console.log(myMap.has('age')); // true
console.log(myMap.has('gender')); // false

// 키-값 쌍 삭제
myMap.delete('age');
console.log(myMap); // Map { 'name' => 'Alice' }

 

알고리즘이 얼마나 효율적인지 분석할 때, 시간 복잡도가 중요한 역할을 한다.

 

배열에서 includes와 indexOf는 최악의 경우 O(n)의 시간 복잡도를 가진다.

반면 Map의 has와 delete는 O(1)로 빠르게 조회하고 삭제할 수 있다. 따라서, LRU 캐시 구현에 Map을 사용하면 성능을 향상시킬 수 있다.

 

 

3. Set과 Map 차이

특성	Set	Map
저장 구조	고유한 값들	키와 값 쌍
중복 여부	값이 중복되지 않음	키가 중복되지 않음
키-값 쌍	값만 저장	키-값 쌍 저장
조회 방식	값이 존재하는지 확인	키를 통해 값 조회
사용 예시	중복되지 않는 값 목록	키로 특정 데이터 찾는 경우

 

 

4. Set과 Map, 일반 객체의 차이점

Set과 Map은 둘 다 객체(Object)다.

하지만, 특정한 기능을 수행하기 위해 고안된 '특수 객체'라서 일반적인 객체({})와는 사용 방식과 목적이 다르다.

 

• 일반 객체: 주로 문자열 키-값 쌍 관리
• Set 객체: 고유한 값들의 집합 관리. '값' 자체만을 저장
• Map 객체: 키-값 쌍 관리. 일반 객체와 달리 키로 문자열뿐만 아니라 모든 자료형(객체, 배열, 함수 등)을 사용 가능

 

Map은 일반 객체와 달리 모든 자료형을 Key로 사용 가능!

자바스크립트의 일반 객체에서는 키로 문자열 또는 심볼만 사용 가능하다.

하지만 Map은 모든 자료형(숫자, 배열, 객체, 함수 등)을 키로 사용 가능하다는 특징이 있다.

 

// [일반 객체에서 객체를 키로 사용할 경우] 사용 불가 (항상 문자열로 변환됨)
const obj = {};

const objKey = { id: 1 };
obj[objKey] = 'Object Key Value'; // 문자열로 변환되어 저장됨

console.log(obj); // { '[object Object]': 'Object Key Value' }
console.log(obj[objKey]); // 'Object Key Value'

// objKey 자체가 키가 된 게 아니라,
// objKey가 문자열로 변환된 '[object Object]'가 실제 키로 사용됨


----------------------------------------------


// [Map에서 객체를 키로 사용할 경우] 사용 가능
const map = new Map();

map.set(objKey, 'Map Key Value'); // 객체를 키로 저장

console.log(map); // Map { { id: 1 } => 'Map Key Value' }
console.log(map.get(objKey)); // 'Map Key Value'


// [그 외] 숫자나 배열도 키로 사용 가능
const numKey = 123;
const arrKey = [1, 2, 3];

map.set(numKey, 'Number Key Value');
map.set(arrKey, 'Array Key Value');

console.log(map.get(numKey)); // 'Number Key Value'
console.log(map.get(arrKey));  // 'Array Key Value'

 

 

일반 객체는

객체 objKey를 키로 사용하려고 하지만, 자바스크립트는 객체를 문자열로 자동 변환하여 [object Object]라는 문자열을 키로 사용한다. 객체를 키로 사용할 수 없다는 것을 알 수 있다.

 

 

Map은

객체 자체를 키로 인식하고, 변환 없이 사용할 수 있기 때문에 객체나 배열을 키로 사용해도 각각 고유한 값이 유지된다.

 

 

5. 왜 일반 객체는 키가 문자열로 변환되는 거고, Map은 객체나 배열도 키로 저장되게끔 설계된 걸까?

일반 객체(Object)는 초기에 자바스크립트가 간단한 문자열 기반의 키-값 구조로 설계되어, 객체나 배열을 키로 사용하면 자동으로 문자열로 변환된다.

 

반면, Map은 보다 다양하고 유연한 데이터 구조를 제공하기 위해 모든 자료형을 키로 사용할 수 있도록 설계되었고, 객체나 배열도 참조값을 그대로 키로 사용한다.

 

 

1. 일반 객체에서 키가 문자열로 변환되는 이유

자바스크립트의 초기 설계에서 객체의 키를 문자열만 사용할 수 있도록 만들었다.

이 설계는 주로 자바스크립트가 가벼운 스크립트 언어로 웹에서 빠르게 동작해야 했기 때문이다.

 

문자열 키는 다음과 같은 이유로 사용되었다.

• 문자열 키는 단순한 형태로, 내부적으로 처리하기도 쉽고 빠름
• 초기에 자바스크립트는 웹 브라우저에서 빠르게 동작해야 했음. 그래서 키를 문자열로 제한하는 방식이 성능 측면에서 더 효율적이었음

 

그래서, 객체의 키로 숫자나 객체를 사용하려고 하면 자바스크립트가 이를 자동으로 문자열로 변환해 처리하게 되었다.

 

 

2. Map은 객체나 배열을 키로 사용할 수 있는 이유

Map은 자바스크립트의 기본 객체가 가진 제약을 해결하기 위해 추가된 데이터 구조다.

 

Map은 모든 자료형(문자열, 숫자, 객체, 배열, 함수 등)을 키로 사용할 수 있도록 설계되었다. 이를 가능하게 하기 위해 Map은 객체의 '참조값'을 사용한다. 객체나 배열을 그대로 저장하고, 이를 이용해 조회할 수 있다.

 

 

왜 Map은 객체를 키로 사용할 수 있을까?

• 키로 전달된 객체나 배열을 문자열로 변환하지 않고, 객체 자체를 저장. 이를 위해 객체의 '참조(reference)'를 그대로 사용. 객체는 메모리에서 고유한 위치를 가지고 있기 때문에, 다른 객체와 구분할 수 있음
• Map은 다양한 자료형을 지원해, 키로 사용하는 복잡한 상황에서도 유연하게 동작할 수 있도록 설계됨

 

이 설계 덕분에 Map은 복잡한 키-값 구조를 다룰 때 더 효율적이고 강력한 도구가 된다.