Post

Hash Map과 Javascript Map과 Set의 연관성

Hash Map과 Javascript Map과 Set의 연관성

해시 맵(Hash Map)과 JavaScript의 Set 및 Map은 모두 데이터를 저장하고 관리하는 데 사용되는 자료 구조입니다. 이들 간에는 몇 가지 연관성이 있습니다.

  • 해시 기반의 자료구조: 해시 맵, Set 및 Map은 내부적으로 해시 함수를 사용하여 요소를 저장하고 검색. 이를 통해 요소에 대한 빠른 검색과 접근이 가능.

  • 고유한 키와 값의 쌍 저장:

    • Map: 키-값(key-value) 쌍을 저장하고 관리하는 자료구조
    • Set: 고유한 값만을 저장하며, 값은 키와 동일
      • 해시 맵: 키와 값의 쌍을 저장하지만, 키는 고유해야 하지만 값은 고유할 필요가 없음.
  • 빠른 검색 및 삽입: 해시 기반의 자료구조는 해시 함수를 사용하여 요소를 저장하고 검색하기 때문에 매우 빠른 검색 및 삽입 속도를 제공 => 대량의 데이터를 다루거나 검색이 빈번한 상황에서 유용

  • 반복 가능한(iterable) 자료구조: JavaScript의 Set 및 Map은 반복 가능한(iterable) 자료구조 - 이는 for…of 루프나 forEach 메서드 등을 사용하여 요소를 반복하고 처리할 수 있음을 의미

  • 효율적인 메모리 관리: 해시 맵, Set, Map은 각 요소에 대해 고유한 해시 값을 사용하여 내부 저장 공간을 효율적으로 관리 => 중복 요소를 제거하거나 특정 요소에 빠르게 접근할 수 있도록 해줌.

Set

요소순회

Set 객체는 이터러블이다. 따라서 for…of문으로 순회 가능, 스프레드 문법과 배열 디스트럭처링의 대상 가능.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const set = new Set([1, 2, 3]);

// Set.prototype 의 Symbol.interator 메서드를 상속받는 이터러블
console.log(Symbol.iterator in set); // true

// for…of문으로 순회 가능
for (const value of set) {
  console.log(value); // 1 2 3
}

// 스프레드 문법의 대상
console.log([...set]); // [1,2,3]

// 배열 디스트럭처링 할당의 대상
const [a, ...rest] = set;
console.log(a, rest); // 1 , [2,3]
---

## 집합 연산

Set객체는 수학적 집합을 구현하기 위한 자료구조
=> 교집합, 합집합, 차집합  구현 가능

### 교집합:intersection

```jsx
// 사용자가 직접 intersection 메서드를 정의 후 함수 할당.
Set.prototype.intersection = function (set) {
  const result = new Set();

  for (const value of set) {
    // set의 공통요소가되는 요소이면 교집합의 대상
    // this: 현재객체; setA
    // set: 비교대상; setB
    if (this.has(value)) result.add(value);
  }

  return result;
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2]);

// setA와 setB의 교집합
console.log("교집합", setA.intersection(setB));

방안2

1
2
3
4
5
6
7
8
9
Set.prototype.intersection = function (set) {
  return new Set([...this].filter((v) => set.has(v)));
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2]);

// setA와 setB의 교집합
console.log("교집합", setA.intersection(setB));

합집합:union

A와 B의 중복없는 모든요소로 구성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Set.prototype.union = function (set) {
  const result = new Set(this);

  for (const value of set) {
    // 2개의 Set객체 모든요소 포함. 단 중복 요소 미포함
    result.add(value);
  }

  return result;
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2, 4]);

// setA와 setB의 합집합
console.log("합집합", setA.union(setB)); // [1,2,3,4]
---

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

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2, 4]);

// setA와 setB의 합집합
console.log("합집합", setA.union(setB));

차집합

A-B : A집합에는 존재하지만 B집합에는 존재하지 않음.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Set.prototype.difference = function (set) {
  // this(Set 객체)를 복사(얕은 복사(shallow copy))
  const result = new Set(this);

  for (const value of set) {
    result.delete(value);
  }

  return result;
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2, 4]);

// setA와 setB의 차집합
console.log("차집합", setA.difference(setB)); // [3]
---

```jsx
Set.prototype.difference = function (set) {
  // this(Set 객체)를 복사(얕은 복사(shallow copy))
  // this를 직접 수정하면 원래의 Set 객체가 변경될 수 있습니다.
  // 하지만 교집합이나 차집합을 계산할 때 원래의 Set 객체를 변경하지 않고 새로운 Set 객체를 반환
  return new Set([...this].filter((v) => !set.has(v)));
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1, 2, 4]);

// setA와 setB의 차집합
console.log("차집합", setA.difference(setB));

얕은 복사(shallow copy)

  • Set 객체의 각 요소에 대한 참조만을 복사하여 새로운 배열을 생성
  • 요소가 객체나 배열 등의 참조형 자료일 경우, 배열에는 해당 요소들에 대한 참조가 복사되며, 원본 Set 객체와 복사된 배열은 같은 요소를 참조
  • 동일한 객체나 배열을 가리키게 되므로 두 객체나 배열의 변경사항이 서로에게 영향을 미칩니다

=> 따라서 요소가 객체나 배열 등의 참조형 자료일 경우에는 깊은 복사를 수행해야 함

깊은 복사(deep copy)

  • 객체의 모든 요소를 재귀적으로 복사하여 새로운 객체를 생성
  • 원본 객체와는 별개의 새로운 객체를 생성
  • 변경사항이 서로에게 영향을 미치지 않습니다.

부분집합과 상위 집합

A가 B에 포함되는 경우 A는 B의 부분집합(subset)이며, B는 A의 상위 집합(superset)이다.

1
2
3
4
5
6
7
8
9
10
11
12
Set.prototype.isSuperset = function (subset) {
  for (const value of subset) {
    if (!this.has(value)) return false;
  }
  return true;
};

const setA = new Set([1, 2, 3]);
const setB = new Set([1]);

// setA가 setB의 상위 집합인지 확인
console.log("상위집합", setA.isSuperset(setB));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Set.prototype.isSuperset = function(subset){
  const supersetArr = [...this]

  // every 메서드를 사용하여 subset의 모든 요소를 순회
  // 각 요소가 supersetArr에 포함되는지를 검사
  // 모든 요소가 포함되어 있다면 true 아니면 false

  return [...subset].every(v => supersetArr.includes(v))
}

const setA = new Set([1,2,3])
const setB = new Set([1])

// setA가 setB의 상위 집합인지 확인
console.log('상위집합', setA.isSuperset(setB))






[...subset] 전개 연산자를 사용하여
subset의 모든 요소를 새로운 배열로 만드는 것을 의미
=> subset의 모든 요소가 배열의  요소로 복사되어 들어가게 됩니다.
=> [1]
반면에 [subset] 배열 리터럴 표기법을 사용하여 배열을 생성하는 것을 의미
=> 하지만 여기서 subset이 Set 객체이므로
배열 리터럴 표기법을 사용하더라도 실제로 배열이 만들어지지 않습니다.
=> 대신에, 이렇게 하면
subset이라는 단일 요소를 가진 배열이 생성됨.
=> [ [1] ]


따라서 [...subset] subset의 모든 요소를 복사하여 새로운 배열을 만들지만,
[subset] subset 자체를 배열의  번째 요소로 가지는 배열을 만듭니다.

Map

Map 객체는 key-value 쌍으로 이루어진 컬렉션

  • key: 객체를 포함한 모든 값
  • 이터러블
  • 요소갯수 확인: map.size

Map 객체의 생성

  • Map생성자 함수
    • 이터러블을 인수로 전달받아 Map객체를 생성.
      • 인수로 전달되는 이터러블은 key-value의 쌍으로 이루어진 요소로 구성되어야 함.
      • 중복된 키를 갖는 요소가 존재할 경우 갚이 덮어씌워짐 => 중복된 키를 갖는 요소 존재 불가.
1
2
3
4
5
6
7
8
9
10
const map = new Map([
  ["key1", "value1"],
  ["key2", "value2"]
]);

const map = new Map([
  ["key1", "value1"],
  ["key1", "value2"]
]);
console.log(map); // {key1 => value2}

for…in 문

for…in 문은 객체의 열거 가능한 속성들을 반복하기 위해 사용됩니다. 그러나 배열에 대해서는 for…in을 사용하는 것이 권장되지 않는데, 이는 몇 가지 이유로 인해 그렇습니다:

인덱스 순서 보장 문제: for…in은 객체의 속성을 반복할 때 특정한 순서를 보장하지 않습니다. 이는 배열의 인덱스 순서를 보장하지 않아 예상치 못한 결과를 초래할 수 있습니다.

상속된 속성 문제: 배열 객체에는 상속된 속성이 존재할 수 있습니다. 예를 들어, 배열의 프로토타입인 Array.prototype에도 메서드와 속성이 존재합니다. for…in은 이러한 상속된 속성들도 열거하기 때문에 원치 않는 동작을 초래할 수 있습니다.

배열 요소 외의 속성 문제: for…in은 배열 요소 뿐만 아니라 배열 객체에 추가된 사용자 지정 속성도 열거합니다. 이는 배열 요소가 아닌 속성도 반복하게 되어 의도치 않은 동작을 초래할 수 있습니다.

배열 내장 메서드 사용 권장: 배열을 반복할 때는 for…in 대신 forEach, for…of, map 등의 내장 반복 메서드나 루프 구문을 사용하는 것이 좋습니다. 이러한 메서드들은 배열 요소를 효과적으로 반복하면서 위의 문제들을 피할 수 있습니다.

따라서, 배열을 반복할 때는 for…in 대신에 for…of나 배열의 내장 반복 메서드를 사용하는 것이 좋습니다.

배열(Array)과 Map객체 비교

배열 (Array): 순차적인 데이터를 관리

  • 순서가 있는 값의 집합
  • 각 요소는 인덱스를 통해 접근가능
  • 동일한 타입이 아닌 다양한 데이터 타입의 요소를 포함가능.
  • 배열의 크기는 동적으로 조절 => 요소를 추가/삭제 가능.
  • 반복문을 사용하여 요소에 접근/수정.
  • 사용 목적: 순차적인 데이터를 저장하고 관리
    • 리스트나 스택, 큐 등을 구현

      배열의 요소를 정렬하고 조건을 만족하는 요소가 있는지 확인

    • sort() 메서드: 배열의 요소를 정렬. 이때 원본 배열이 변경되며, 정렬된 배열이 반환.
    • some() 메서드: 배열의 각 요소에 대해 주어진 함수를 실행하고, 콜백 함수가 하나라도 true를 반환하면 some() 메서드는 즉시 true를 반환하고 반복을 중지.

Map: 키-값 쌍을 저장하고 검색

  • 키-값(key-value) 쌍을 저장하는 자료구조
  • 각 키는 유일해야 합니다. 키에 해당하는 값에 접근하기 위해 사용.
  • 키와 값의 쌍을 연결하여 저장. 순서가 보장되지 않음.
  • 다양한 데이터 타입의 키와 값 모두 저장 가능
  • Map 객체의 크기는 size 속성을 통해 확인.
  • 요소를 추가, 삭제, 수정할 수 있습니다.
  • 사용 목적: 특정 키와 연관된 값을 저장하고 검색
  • 객체와 유사하지만 객체보다 다양한 데이터 타입의 키를 사용할 수 있고 순서가 보장되는 등의 장점

프로그래머스: 전화번호 목록

배열 메서드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(phoneBook) {

  // !phoneBook.sort(): 항상 true를 반환하게 되어 some() 함수의 콜백 함수가 항상 실행
    return !phoneBook.sort().some((t,i)=> {
      // 배열의 마지막 요소인지를 확인
      // 만약 마지막 요소라면 중복이 없다는 것을 나타내기 위해 false를 반환.

 구문은 반복문이 마지막 요소까지 도달했을 , 다음 요소가 없기 때문에 중복이 발생하지 않음을 나타내기 위한 
        if(i === phoneBook.length -1) return false;
	   // 이웃하는 두 번호가 동일한 접두사를 가지는지 확인
       // 동일한 접두사를 가진다면, some() 함수는 true를 반환
       // 이는 전화번호부에 중복된 접두사를 가진 번호가 있다는 것을 의미
        return phoneBook[i+1].startsWith(phoneBook[i]);
    })
}

일반 객체를 사용하여 해시맵을 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function solution(phone_book) {
  var answer = true;
  const hashMap = {};

  // hashMap의 key를 전화번호로 저장.
  phone_book.forEach((num) => {
    hashMap[num] = true;
  });

  for (const number of phone_book) {
    if (!answer) break;

    let prefix = "";

    // 현재 검사 중인 전화번호(number)의 각 자릿수(digit)에 대해 반복
    for (const digit of number) {
      // 1. 접두사 생성.
      // 현재까지의 접두사에 현재 자릿수를 더한다.
      // 이렇게 하면 접두사가 하나씩 늘어난다.
      // 접두사의 길이에 따라서 점차적으로 전체 전화번호의 자릿수를 확인가능
      prefix += digit;

      // 2. 현재 전화번호가 다른 전화번호의 접두사인지를 확인

      // hashMap[prefix]
      // 현재까지 만들어진 접두사가 해시맵에 존재하는지 확인
      // 만약 존재한다면, 해당 접두사가 이미 다른 전화번호의 접두사임을 의미

      // prefix !== number
      // 현재까지 만들어진 접두사가 현재 검사 중인 전화번호(number)와 같지 않은지 확인
      // 만약 같다면, 이는 자기 자신의 전화번호를 검사하는 것이므로 접두사가 아님.
      if (hashMap[prefix] && prefix !== number) {
        answer = false;
        break;
      }
    }
  }
  return answer;
}
This post is licensed under CC BY 4.0 by the author.