[5.3.5] 맵 - [5.3.7] 해시 테이블

비선형 자료구조

- 트리, 그래프, 힙, 우선순위 큐, 맵, 셋, 해시테이블

1. 맵 

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조

 

string : int 형태로 값을 할당해야 할 때 사용

map<string, int> 형태로 구현 (C++)

clear() : 모든 요소를 삭제

size() : map의 크기를 구함

erase() : 해당 키와 키에 매핑된 값을 삭제

 

해시 테이블을 구현할때 사용 

 

종류

1) 정렬을 보장하지 않는 unordered_map

2) 정렬을 보장하는 map

---

자바스크립트 Map 객체 

 

const map1 = new Map();

map1.set('a', 1);
map1.set('b', 2);
map1.set('c', 3);

console.log(map1.get('a'));
// Expected output: 1

//값 수정
map1.set('a', 97);

console.log(map1.get('a'));
// Expected output: 97

//크기 
console.log(map1.size);
// Expected output: 3

//삭제
map1.delete('b');

console.log(map1.size);
// Expected output: 2

 

for ... of 반복문을 사용하면 각 반복에 대해  [key, value]  배열을 반환한다. 

 

Object와 Map이 유사하며, 이전에는 Object가 Map으로 사용되어왔다. 

구분	Map	Object
우발적 키	default key가 존재하지 않는다	default key가 존재한다 자신의 키와 충돌이 가능
보안	사용자가 제공하는 키-값을 안전하게 사용가능	객체의 프로토타입을 재정의하여 객체 주입 공격 발생시킬 수 있음
키 유형	모든 값 (함수, 객체, 원시값)  자료형 제약이 없음	String 또는 Symbol
키 순서	삽입한 순서대로 정렬	순서를 보장할 수 없다
크기	size 속성으로 반환	아이템 수를 수동으로 결정해야함
순회	순회가능 (Iterable)	iteration protocol을 구현하지 않으므로  for...of 를 사용해 직접적으로 반복할 수 없다
빈번한 키-값 쌍추가/삭제 성능	객체보다 성능이 좋음	최적화되지 않음

 

출처 : MDN

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

---

 

2. 셋 

특정 순서에 따라 고유한 요소를 저장하는 컨테이너,

중복되는 요소 없이 오로지 희소한 (unique) 값만 저장하는 자료구조

 

자바스크립트 Set 객체 

add() 메서드에 의한 삽입 순서에 따라 요소들을 순회할 수 있다.

const mySet1 = new Set();

mySet1.add(1); // Set(1) { 1 }
mySet1.add(5); // Set(2) { 1, 5 }
mySet1.add(5); // Set(2) { 1, 5 }
// 중복이 허용되지 않음 

mySet1.add("some text"); // Set(3) { 1, 5, 'some text' }
const o = { a: 1, b: 2 };
mySet1.add(o);

mySet1.add({ a: 1, b: 2 }); // o 는 다른 객체를 참조하고 있기 때문에 이는 중복이 아님 

mySet1.has(1); // true
mySet1.has(3); // false, 3 이 set에 추가되지 않았기 때문입니다.
mySet1.has(5); // true
mySet1.has(Math.sqrt(25)); // true
mySet1.has("Some Text".toLowerCase()); // true
mySet1.has(o); // true

mySet1.size; // 5

mySet1.delete(5); // set에서 5 제거
mySet1.has(5); // false, 5 는 제거되었습니다.

mySet1.size; // 4, 하나를 제거했기 때문에

mySet1.add(5); // Set(5) { 1, 'some text', {...}, {...}, 5 } - 이전에 삭제된 아이템이 새로운 아이템으로 추가되나, 삭제 전 원래 위치를 유지하진 못합니다.

console.log(mySet1); // Set(5) { 1, "some text", {…}, {…}, 5 }

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

 

---

3.  해시테이블 (해시 맵)

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블.

이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리할 수 있다.

unordered_map으로 구현 

각각의 키 값에 해시 함수를 적용해서 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다.

실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 

 

해시 함수

'임의 크기 데이터'를 '고정 크기 값'으로 매핑하는데 사용하는 단방향 함수

= 키                           = 해시 (값) 

즉, 키를 해시값으로 인코딩하는 함수 

 

→ 삽입, 삭제, 탐색 시 평균적으로 상수시간 O(1) 의 시간 복잡도를 갖는다.

= 빠르게 데이터를 검색할 수 있다

 

 

단점

- 순서를 보장하지 않는다 

- 데이터가 pseudo-random 위치에 저장되기 때문에, 정렬된 순서로 접근할때 비용이 높다 

 

 

자바스크립트에서 구현하는 방법

- 배열

- 객체

- Map

- Set 

 

https://velog.io/@93minki/JavaScript-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table

https://ko.javascript.info/map-set