1. 해시 테이블
학창시절 사물함이 기억하시나요? 사물함이 바로 해시 테이블의 예입니다.
해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게 된다. 그럼 index는 어떻게 구할까?
1.1 해시 테이블
- 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
- 삽입은 이며 키를 알고 있다면 삭제，탐색도 로 수행한다.
💡 Hash : 잘게 잘라 가공하는 것
- Hash Table : 입력받은 키를 잘게 잘라서 숫자로 만든다.
- cf. 해쉬 브라운(Hash Brown) : 고기와 감자를 잘게 다져 요리한 것
1.2 해시 함수
입력받은 값을 특정 범위 내 숫자로 변경하는 함수
1.3 해시 테이블의 문제점
만약 해시 함수의 결과가 동일하여 겹친다면? 해쉬 충돌이 발생할 수 있다.
2. Hash Collision(해쉬 충돌)
해쉬 충돌을 해결하기 위한 방법
2.1 선형 탐사법
- 충돌이 발생하면 옆으로 한 칸 이동한다.
- 단순하지만, 특정 영역에 데이터가 몰릴 수 있다는 단점이 존재
- 이동한 곳에서 또 충돌이 발생한다면, 충돌이 발생하지 않을 떄까지 이동
- 이름 그대로 최악의 경우, 선형 시간()의 탐색 시간이 걸릴 수 있습니다.
2.2 제곱 탐사법
- 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
- 충돌이 발생할 수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다 덜 합니다.
2.3 이중 해싱
- 충돌이 발생하면 다른 해시 함수를 이용한다.
- 또 충돌이 발생하면 충돌이 발생하지 않을 떄까지 또 다른 해시 함수를 사용한다.
2.4 분리 연결법
- 앞의 다른 3가지 방법들과 달리, 충돌이 발생할 경우 다른 인덱스로 이동하지 않습니다.
- 대신 해시 테이블의 요소를 연결 리스트로 만들어, 충돌이 발생한 버킷에 그대로 요소를 추가합니다.
- 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.
- 대신 최악의 경우, 하나의 버킷이 무한정 늘어날 수 있다는 단점이 존재
3. 어디에 사용하는가?
e.g. 학생 정보를 어떻게 관리할 것인가? 출석부!
연결 리스트를 사용하면 학생 정보가 알고 싶을 떄 시간복잡도가 걸린다.
배열은 인덱스를 모를 경우 탐색에 이 걸린다.
반면 해시 테이블을 사용하면 에 찾을 수 있다. 따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.
4. 구현
4.1 JavaScript Array ≈ Hash Table
배열은 사실 객체이기 때문에 객체처럼 사용할 수는 있지만 올바른 방법이 아니기 떄문에 추천하지 않습니다.
const table = [];
table['key'] = 100;
table['key2'] = 'Hello';
console.log(table['key']); // 100
table['key'] = 349;
console.log(table['key']); // 349
delete table['key'];
console.log(table['key']); // undefined4.2 JavaScript Object ≈ Hash Table
객체로 구현하는 것은 가장 간단한 방법입니다.
const table = {};
table['key'] = 100;
table['key2'] = 'Hello';
console.log(table['key']); // 100
table['key'] = 349;
console.log(table['key']); // 349
delete table['key'];
console.log(table['key']); // undefined4.3 Map
별도로 Map 객체를 사용할 수도 있습니다.
const table = new Map();
table.set('key', 100);
table.set('key2', 'Hello');
// 📝 Map 객체의 값을 가져올 떄는 get
console.log(table['key']); // undefined
console.log(table.get('key')); // 100
const object = { a: 1 };
table.set(object, 'A1'); // Map은 Object도 Key로 쓸 수 있다.
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // [Map Iterator] { 'key', 'key2' }
console.log(table.values()); // [Map Iterator] { 100, 'Hello' }
table.clear();
console.log(table.values()); // [Map Iterator] { }4.4 Set
또 다른 Hash Table로 Set으로 만들 수도 있습니다.
const table = new Set();
table.add('key'); // Key와 Value가 동일하게 들어간다
table.add('key2');
console.log(table.has('key')); // true
console.log(table.has('key3')); // false
table.delete('key2');
console.log(table.has('key2')); // false
table.add('key3');
console.log(table.size); // 2
table.clear();
console.log(table.size); // 03. 해시 테이블 실습 : 베스트 앨범
2.1 문제
2.2 풀이❌
// 1. 같은 장르끼리 묶기
// 2. 묶인 노래들을 재생 순으로 정렬하기
// 3. 노래를 2개까지 자르는 작업하기
// 핵심 키워드는 "묶는 것", "정렬"
function solution(genres, plays) {
const genreMap = new Map();
genres
// 1. 각 장르끼리 배열로 묶기 [장르명, 재생횟수]
.map((genre, index) => [genre, plays[index]])
// 2. 묶어준 장르로 데이터 만들기
.forEach(([genre, play], index) => {
const data = genreMap.get(genre) || { total: 0, songs: [] };
genreMap.set(genre, {
total: data.total + play,
songs: [...data.songs, { play, index }]
.sort((a, b) => b.play - a.play) // 재생 순으로 내림차순
.slice(0, 2),
});
});
return [...genreMap.entries()]
.sort((a, b) => b[1].total - a[1].total)
.flatMap((item) => item[1].songs)
.map((song) => song.index);
}[참고]
Front-end 공부 중... 책 읽는 걸 좋아합니다.