JavaScript의 Map과 Set객체는 HashTable구조를 활용한다

Data Structure에는 hash table이 있다.

hash table은 연관 배열 구조(associative array)로, 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료구조이다.

hash table은, 해시 함수가 주어진 키 값을 받아 유니크한 해시값으로 변환해 이를 key로 저장, 해당 키에 값을 매칭하는 방식으로 만들어진다.

 

위와 같은 방식으로 만들어진 hash table은 데이터를 저장, 검색하는 데 효율적으로 사용된다. 유니크한 키값을 활용한 덕분에 데이터 검색, 저장, 삭제시 O(1) 이라는 최적의 시간 복잡도가 나오게 된다. ( 해시 충돌로 인한 시간복잡도는 여기서는 논외로 하겠씀니다@_@ !!!!!!!!! )

 

JavaScript에서도
Hash Table의 개념이 사용된 자료구조가 있다.

이러한 개념은 알고리즘 풀이에서도 사용할 수 있다. 내가 사용하는 언어인 JavaScript에서는 Map과 Set객체의 내부 동작이 hash table을 활용해 구현되었다고 할 수 있다!!!

 

Set()

Set은 JavaScript의 내장객체로, 중복되지 않는 값들의 집합을 관리하는 자료구조다. ES6에서 추가된 문법이다. Set의 기본 주고는 다음과 같다

• new Set() : set객체 생성
• add(value) : 값을 추가
• delete(value) : 특정 값을 삭제
• has(value) : 특정 값이 존재하는지 확인
• clear() : 모든 값을 삭제
• size : 현재 Set에 저장된 값의 개수를 반환

const mySet = new Set();
mySet.add(1);
mySet.add(2);
mySet.add(2); // 중복된 값은 추가되지 않음
console.log(mySet.size); // 2
console.log(mySet.has(1)); // true

// set 객체 활용
const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);

// 교집합
const intersection = new Set([...setA].filter(x => setB.has(x)));
console.log(intersection); // Set { 2, 3 }

// 합집합
const union = new Set([...setA, ...setB]);
console.log(union); // Set { 1, 2, 3, 4 }

 

Map()

Map은 JavaScript의 내장객체로, Key-Value 쌍을 저장하고 관리하는 자료구조다. 이 때 key는 해시함수의 동작으로 유니크한 값으로 저장된다. ( 이를 활용해 map객체를 생성해 알고리즘 문제를 풀이 )

• new Map() : map객체 생성
• set(key, value) : 키와 값을 추가
• get(key) : 특정 키에 대한 값을 반환
• delete(key) : 특정 키와 그에 해당하는 값을 삭제
• has(key) : 특정 키가 존재하는지 확인
• clear() : 모든 키-값 쌍을 삭제
• size : 현재 Map에 저장된 키-값 쌍의 개수를 반환

const myMap = new Map();
myMap.set('a', 1);
myMap.set('b', 2);
myMap.set('b', 3); // 키 'b'의 값이 업데이트됨
console.log(myMap.size); // 2
console.log(myMap.get('a')); // 1

// 반복
myMap.set('x', 10).set('y', 20);

// forEach
myMap.forEach((value, key) => {
  console.log(`${key}: ${value}`); // 출력: x: 10, y: 2
});

// for...of
for (let [key, value] of myMap) {
  console.log(`${key}: ${value}`); // 출력: x: 10, y: 20
}

 

프로그래머스의 알고리즘 문제 풀이 ( hash편 )

• https://thdud4479.tistory.com/305

프로그래머스-포켓몬

• https://thdud4479.tistory.com/304

완주하지 못한 선수

 

 

이들 문제를 풀 때, map과 set을 사용해서 풀었다.

 

Question

Data-structure Hash는 값을 해시함수를 통해서 자료를 저장하는 구조잖아, 여기서 js의 map()객체의 key값은 유일하다고 했는데, map()객체도 hash함수를 통해서 데이터가 저장되는 구조인건가?

OO 맞음 Js의 map객체는 내부적으로 해시구조를 활용해서 키값이 고유하게 동작하도록 설계돼있다.
= 해시 함수와 비슷한 매커니즘을 통해 구현된다.

JavaScript의 Map객체를 사용하면 프로그래머가 직접 해시 함수를 구현하지 않아도, 유일한 키-값형태의 데이터 관리를 할 수 있고, 관련 메서드를 사용해 빠른 조회가 가능하다.

---

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

map 메서드, 프로퍼티 사용 https://medium.com/@ronfybish/a-quick-guide-to-javascript-es6-map-f2c4d3005619

js의 자료구조 map, weakMap, Object https://medium.com/before-semicolon/map-dictionary-data-structure-in-javascript-f9741b905ede

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

set은 언제 사용해야 하나?? https://medium.com/before-semicolon/set-data-structure-in-javascript-6bb27a8e44a

https://kellis.tistory.com/129

https://overcome-the-limits.tistory.com/9