해쉬테이블, 해쉬맵

알고리즘 스터디에서 해쉬에 대해서 공부하면서 이번에 스터디하고 싶었던 주제는 해쉬였습니다.
최근에 쇼핑관련 회사에서 코테를 봤었는데, 해쉬맵 관련 문제를 많이 내주시더라고요.
저는 주로 객체를 사용해서 문제를 풀었었는데, 해쉬로는 어떻게 풀 수 있고, 장점이 무엇인지 알아보고자 합니다!

해쉬란?

해쉬함수는 key를 고정된 길이의 해시로 변경해주는 역할을 합니다. 이때 해쉬 함수를 통해 키 값을 해시로 변경하는 작업을 해싱이라고 합니다.

즉, 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.

• 해쉬
  해시는 해시함수의 결과물로, 해시 테이블의 저장소(bucket)을 가리키는 주소(인덱스)로 사용됩니다.
  즉, 해시 값이 값과 매칭되어 저장소에 저장됩니다.

즉 정리해보자면,
해시 함수: key -> hash로 변환해주는 함수
해시: 키 값이 해시 함수로 변환된 것, 저장소의 주소(인덱스)로 사용됨
해시 테이블: hash를 주소 삼아 value를 저장하는 자료구조

해쉬 테이블의 시간복잡도

해시테이블은 Insertion, Search, Deletion에서 평균적으로 O(1)의 시간복잡도를 갖는다. 따라서 매우 빠르게 데이터를 저장하고 탐색, 삭제할 수 있는 효율성이 좋은 자료구조입니다.

해쉬 테이블의 시간복잡도

그럼 해쉬 테이블은 언제 쓰는게 좋을까요?

• 큰 데이터에서 빠르게 값을 찾아야할 때,
• 리스트 대신 사용할 수 있을 때, (리스트를 사용한다면 검색할 때, 시간복잡도는 O(n))

자바스크립트의 Map

JS에서 해시테이블은 대표적으로 Object, Map, Set이 있습니다. JS에서 해쉬를 구현할 때에는 Map을 많이 사용하게 됩니다.

Map 객체란?

• 주로 Object와 비교됨
• key-value로 이루어진 해시 테이블
• 탐색은 get(), 삽입은 set()으로 한다.
• key는 고유값으로써, 단 한개만 존재한다.
• key 가능 자료형 : number, string, function, object, NaN
• 이터러블이기때문에 for of문과 스프레드 문법으로 디스트럭처링 할당의 대상이 될 수 있습니다.

Map 객체 생성

const map = new Map();
console.log(map) // Map(0){}
```Map객체는 Map 생성자 함수로 생성합니다.
 
### Map 객체 크기 확인
또한 Map 객체의 요소 개수를 확인할 때는 `Map.prototype.size`프로퍼티를 사용하면 됩니다.
```js
const map = new Map([['key1', 'value1'], ['key2', 'value2']]);
console.log(map.size) // 2

Map 객체 설정 및 삭제

const map = new Map();
map.set('x', 100);
map.set('y', 200);
 
map.delete('x');
map.delete('y');

Map 객체 요소 취득

const map = new Map();
map.set('x', 100);
map.set('y', 200);
 
map.get('x') // 100;

Map 객체 일괄 삭제

const map = new Map();
map.set('x', 100);
map.set('y', 200);
 
map.clear();
console.log(map); // Map(0) {}

Map 객체 순회

Map객체는 배열의 forEach 메서드로 순회할 수도 있고, for문으로도 순회할 수 있습니다. forEach메서드는 기존 배열과 같은 방식으로 돌아주면되고, for문은 아래와 같이 순회할 수 있습니다.

const map = new Map();
map.set('x', 100);
map.set('y', 200);
for(let [key, value] of map){
  console.log(key, value);
}

이외에도 Map.prototype.keys, Map.prototype.values, Map.prototype.entries를 사용할 수 있습니다.