해시맵 · 해시셋 — O(1) 조회의 비밀

// ━━━ JavaScript Map vs 객체 ━━━

// 1) Map — 권장 (키 타입 자유, 순회 쉬움, 크기 O(1))
const users = new Map();
users.set("짓친", { age: 25 });
users.set(42, "숫자 키도 OK");   // 객체 `{}`는 불가능
users.get("짓친");                // → { age: 25 }  O(1)
users.has("홍길동");              // → false          O(1)
users.size;                       // → 2
users.delete("짓친");

for (const [key, value] of users) { /* 순회 순서 = 삽입 순서 */ }

// 2) 일반 객체 — 간단할 때만
const cache = {};
cache["key1"] = "value1";
"key1" in cache;                  // → true

// 3) Set — 중복 제거 + 포함 여부 확인
const tags = new Set(["js", "ts", "js"]); // → {"js", "ts"}  자동 중복 제거
tags.has("ts");                   // → true  O(1)

// ❌ O(n²) — 1만 건이면 1억 번 비교 → 느림
const found = [];
for (const a of listA) {
  for (const b of listB) {
    if (a.id === b.id) found.push(a);
  }
}

// ✅ O(n) — Set으로 O(1) 조회
const idsInB = new Set(listB.map(b => b.id));
const found = listA.filter(a => idsInB.has(a.id));

// 실전: 두 배열의 교집합·차집합
const aSet = new Set(a);
const intersection = b.filter(x => aSet.has(x));     // 교집합
const difference   = a.filter(x => !new Set(b).has(x)); // 차집합

// ① 중복 제거
const unique = [...new Set(nums)];

// ② 빠른 포함 확인 — 게시판 차단 단어 리스트
const bannedWords = new Set(["spam", "abc", ...]); // 1만 개
const isBanned = (text) =>
  text.split(/\s+/).some(word => bannedWords.has(word));
// 리스트였다면 매 단어마다 O(1만), Set이므로 O(1)

// ③ 이미 처리한 항목 추적 — 무한루프 방지
const visited = new Set();
function walk(node) {
  if (visited.has(node.id)) return;
  visited.add(node.id);
  node.children.forEach(walk);
}