[37장] Set 과 Map

- 목표

1. Set Map 기본 정의
2. Set Map 내장 메서드
3. Set 수학적 집합 구현
4. 정리

---

Set Map 기본 정의

1. Set 

- 중복되지 않는 유일한 값들의 집합

- 수학적 집합을 구현하기 위한 자료구조

- 배열과 유사하지만 다음과 같은 차이가 있다.

구분	배열	Set
동일한 값을 중복하여 포함훌 수 있는가?	가능	불가능
요소 순서에 의미가 있는가?	가능	불가능
인덱스로 요소에 접근할 수 있는가?	가능	불가능

2. Map

- key value 쌍으로 이루어진 컬렉션

- 내부적으로 해시 테이블 구조를 사용하여 구현

   ㄴ hash table 구조로 특정 키를 조회(get)하거나 확인(has)할 때 일정한 시간 복잡도를 가진다. (평균적으로 O(1))

- 객체와 유사하지만 다음과 같은 차이가 있다.

구분	객체	Map
키로 사용할 수 있는 값의 Type	문자열 또는 Symbol 값	객체를 포함한 모든 값
Iterable	false	true
크기 확인	Object.keys(obj).length	map.size
해시 테이블 기반	false	true

---

Set Map 내장 메서드

구분	Set	Map
생성자	new Set([iterable])	new Map([iterable])
요소 추가	add(value)	set(key, value) // 갱신 가능
요소 가져오기	개별 접근 불가능 has 혹은 loop 를 통한 접근만 가능	get(key)
요소 삭제	delete(value)	delete(key)
모든 요소 삭제	clear()	clear()
요소 포함 여부 확인	has(value)	has(key)
크기 확인	size	size
Loop	forEach(value, value, set)	forEach(key, value, map)
	keys() : 값의 반복자 반환 (Set은 key와 value가 동일)	keys(): key의 반복자 반환
	entries(): [value, value] 쌍 반복자 반환	entries(): [key, value] 쌍 반복자 반환
	values(): value의 반복자 반환
	for...of

---

Set 수학적 집합 구현

 - Set A, B, C

const A = new Set([1, 2, 3, 4, 5]);
const B = new Set([2, 3, 4, 7, 8]);
const C = new Set([1, 2, 3]);

1. 합집합 A ∪ B

Set.prototype.union = function (set) {
  const result = new Set();
  for (const value of set) result.add(value);
  return result;
}
console.log(A.union(B));
// output : Set { 0: 2, 1: 3, 2: 4, 3: 7, 4: 8, λ: [...], ... }

 

다른 방법

Set.prototype.union = function (set) {
  return new Set([...this, ...set]);
}

2. 교집합 A ∩ B

Set.prototype.intersection = function (set) {
  const result = new Set();
  for (const value of set) this.has(value) && result.add(value);
  return result;
}
console.log(A.intersection(B));
// output : Set { 0: 2, 1: 3, 2: 4, λ: [...] }

 

다른 방법

Set.prototype.intersection = function (set) {
  return new Set([...this].filter(e => set.has(e)));
}

3. 차집합 A − B

Set.prototype.difference = function (set) {
  const result = new Set(this);
  for (const value of set) result.delete(value);
  return result;
}
console.log(A.difference(B));
// output : Set { 0: 1, 1: 5, λ: [...] }

 

다른 방법

Set.prototype.difference = function (set) {
  return new Set([...this].filter(e => !set.has(e)));
}

4. 부분 집합과 상위 집합 A ⊂ B / A ⊆ B

Set.prototype.isSuperset = function (set) {
  for (const value of set) {
    if(!this.has(value)) return false;
  }
  return true;
}
console.log(A.isSuperset(B)); // false
console.log(A.isSuperset(C)); // true

 

다른 방법

Set.prototype.isSuperset = function (set) {
  const supersetArr = [...this];
  return [...set].every(e => supersetArr.includes(e));
}

---

정리

set 을 사용하면 데이터의 중복을 손쉽게 다룰 수 있고 더 나아가 수학적 집합을 구현하는데 용이한 장점이 있다.

map 은 일반 객체와 형태가 비슷해 다음과 같은 특수한 상황에서 빛난다.

• 복잡한 데이터 구조
• 높은 성능이 요구되는 대량 데이터 작업
• 키가 꼭 다양한 데이터 타입이어야 하는 경우
• 순회 및 데이터 크기 확인 등의 편리성

특히, map 을 사용하면 앞서 말한바와 같이 모든 데이터 타입을 키로 사용 가능한 장점이 있는데 그 밖에도 아래와 같은 장점이 있다.

1. 키의 삽입 순서 유지
2. 조회 및 삭제에서 더 빠름
3. 크기 확인이 간편
4. 순회 메서드의 효율성
5. 순수 데이터 저장 용도
6. WeakMap과의 연계

---

🔥 배운점

배열의 중복을 없애기 위해 써왔던 자료구조 Set 이 수학적 집합을 구현하는데 쓰인다는 것을 알았다.

이것으로 알고리즘 문제에서 데이터의 교집합, 합집합, 차집합, 부분집합, 상위집합 여부를 구현하는 것이 보다 수월해질 것 같다.

평소에는 단순 배열에 반복문을 통한 비교연산으로 앞의 집합 기능을 구현해서 요소가 순서에 상관이 없는 경우 연산 속도가 느려지는 문제가 있었는데 {} 객체를 사용하면 이를 보다 효율적으로 관리할 수 있다는 점에서 앞으로의 알고리즘 풀이에 적극적으로 활용해봐야겠다.

그리고 Map 과 일반 객체가 형태가 유사해서 "단순히 Map 은 key 에 다양한 타입이 올 수 있다" 정도의 차이로만 인지했는데 내부적으로 Map 은 순수해시테이블 구조이고 일반 객체는 처음에는 Shape 기반 속성 사전을 사용하다가 상황에 따라 해시 테이블 구조로 변경되는 특징이 있어 대규모 동적 데이터를 관리할 때는 해시테이블 기반 Map 객체를, 소규모 정적 데이터를 관리할 때는 Sahpe 기반 속성 사전을 사용하는 일반 객체가 더 유리할 수 있다는 것을 알았다.

- 참고

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set

Set - JavaScript | MDN

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map

Map - JavaScript | MDN