해시 맵 Hash Map

해시 맵 (Hash Map)

해시 맵은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조로, 키를 해시 함수로 변환하여 평균 O(1) 시간에 데이터를 조회합니다.

JavaScript에서는 일반적으로 Map 객체를 사용합니다.

---

Map 객체의 주요 메소드

• set(key, value) : 키-값 쌍 저장
• get(key) : 키에 해당하는 값 조회
• has(key) : 키 존재 여부 확인
• delete(key) : 키 제거
• keys() : 키를 삽입 순서대로 갖는 iterable 객체 반환
• values() : 값을 삽입 순서대로 갖는 iterable 객체 반환
• entries() : [key, value]쌍을 삽입 순서대로 갖는 iterable 객체 반환
• size : 저장된 요소 개수

---

기본 사용법

const map = new Map();

---

set / get

map.set("apple", 1);
map.set("banana", 2);

map.get("apple"); // 1
map.get("orange"); // undefined

---

has / delete

map.has("banana"); // true
map.delete("banana");
map.has("banana"); // false

size

map.size; // 1

---

반복문

for (let [key, value] of map) {
  console.log(key, value);
}

---

배열 VS 해시 맵

배열은 순회하고, 해시 맵은 기억한다.

• 입력 크기가 작거나 순서가 중요하지 않다면 해시 맵이 유리
• 이중 for문은 대부분 시간초과
• 값을 찾기 위해 매번 처음부터 끝까지 같은 배열을 반복해서 탐색하는 경우, 해시 맵으로 생각 전환

---

배열 기반 사고

시간 복잡도 : O(N²)

let count = 0;
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    if (arr[i] === arr[j]) count++;
  }
}

---

해시 맵 사고

시간 복잡도 : O(N)

const map = new Map();

for (let x of arr) {
  map.set(x, (map.get(x) || 0) + 1);
}

---

자주 나오는 패턴

• 빈도수 카운팅

  map.set(x, (map.get(x) || 0) + 1);
  

• 존재 여부 체크

  if (map.has(x)) {
  ...
  }
  

• 쌍(pair) 찾기

  if (map.has(target - x)) {
    return true;
  }