1. 해시 테이블

학창시절 사물함이 기억하시나요? 사물함이 바로 해시 테이블의 예입니다. 해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게 된다. 그럼 index는 어떻게 구할까?

1.1 해시 테이블

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
삽입은 $O(1)$ 이며 키를 알고 있다면 삭제，탐색도 $O(1)$ 로 수행한다.

Data Structure_7_1

💡 Hash : 잘게 잘라 가공하는 것

Hash Table : 입력받은 키를 잘게 잘라서 숫자로 만든다.

cf. 해쉬 브라운(Hash Brown) : 고기와 감자를 잘게 다져 요리한 것

위키백과 해시 브라운

1.2 해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수

1.3 해시 테이블의 문제점

만약 해시 함수의 결과가 동일하여 겹친다면? 해쉬 충돌이 발생할 수 있다.

Data Structure_7_2

2. Hash Collision(해쉬 충돌)

해쉬 충돌을 해결하기 위한 방법

2.1 선형 탐사법

충돌이 발생하면 옆으로 한 칸 이동한다.
단순하지만, 특정 영역에 데이터가 몰릴 수 있다는 단점이 존재
이동한 곳에서 또 충돌이 발생한다면, 충돌이 발생하지 않을 떄까지 이동
이름 그대로 최악의 경우, 선형 시간( $O(n)$ )의 탐색 시간이 걸릴 수 있습니다.

Data Structure_7_3

2.2 제곱 탐사법

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
충돌이 발생할 수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다 덜 합니다.

Data Structure_7_4

2.3 이중 해싱

충돌이 발생하면 다른 해시 함수를 이용한다.
또 충돌이 발생하면 충돌이 발생하지 않을 떄까지 또 다른 해시 함수를 사용한다.

2.4 분리 연결법

앞의 다른 3가지 방법들과 달리, 충돌이 발생할 경우 다른 인덱스로 이동하지 않습니다.
대신 해시 테이블의 요소를 연결 리스트로 만들어, 충돌이 발생한 버킷에 그대로 요소를 추가합니다.
버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.
대신 최악의 경우, 하나의 버킷이 무한정 늘어날 수 있다는 단점이 존재

3. 어디에 사용하는가?

e.g. 학생 정보를 어떻게 관리할 것인가? 출석부!

연결 리스트를 사용하면 학생 정보가 알고 싶을 떄 $O(n)$ 시간복잡도가 걸린다.

**배열은 인덱스를 모를 경우 탐색에 $O(n)$ **이 걸린다.

반면 해시 테이블을 사용하면 $0(1)$ 에 찾을 수 있다. 따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.

4. 구현

4.1 JavaScript Array ≈ Hash Table

배열은 사실 객체이기 때문에 객체처럼 사용할 수는 있지만 올바른 방법이 아니기 떄문에 추천하지 않습니다.

1const table = []
2
3table['key'] = 100
4table['key2'] = 'Hello'
5console.log(table['key']) // 100
6
7table['key'] = 349
8console.log(table['key']) // 349
9
10delete table['key']
11console.log(table['key']) // undefined

4.2 JavaScript Object ≈ Hash Table

객체로 구현하는 것은 가장 간단한 방법입니다.

1const table = {}
2
3table['key'] = 100
4table['key2'] = 'Hello'
5console.log(table['key']) // 100
6
7table['key'] = 349
8console.log(table['key']) // 349
9
10delete table['key']
11console.log(table['key']) // undefined

4.3 Map

별도로 Map 객체를 사용할 수도 있습니다.

1const table = new Map()
2
3table.set('key', 100)
4table.set('key2', 'Hello')
5
6// 📝 Map 객체의 값을 가져올 떄는 get
7console.log(table['key']) // undefined
8console.log(table.get('key')) // 100
9
10const object = { a: 1 }
11table.set(object, 'A1') // Map은 Object도 Key로 쓸 수 있다.
12console.log(table.get(object)) // A1
13
14table.delete(object)
15console.log(table.get(object)) // undefined
16console.log(table.keys()) // [Map Iterator] { 'key', 'key2' }
17console.log(table.values()) // [Map Iterator] { 100, 'Hello' }
18
19table.clear()
20console.log(table.values()) // [Map Iterator] {  }

4.4 Set

또 다른 Hash Table로 Set으로 만들 수도 있습니다.

1const table = new Set()
2
3table.add('key') // Key와 Value가 동일하게 들어간다
4table.add('key2')
5console.log(table.has('key')) // true
6console.log(table.has('key3')) // false
7
8table.delete('key2')
9console.log(table.has('key2')) // false
10
11table.add('key3')
12console.log(table.size) // 2
13
14table.clear()
15console.log(table.size) // 0

3. 해시 테이블 실습 : 베스트 앨범

2.1 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42579

2.2 풀이❌

1// 1. 같은 장르끼리 묶기
2// 2. 묶인 노래들을 재생 순으로 정렬하기
3// 3. 노래를 2개까지 자르는 작업하기
4
5// 핵심 키워드는 "묶는 것", "정렬"
6function solution(genres, plays) {
7  const genreMap = new Map()
8
9  genres
10    // 1. 각 장르끼리 배열로 묶기 [장르명, 재생횟수]
11    .map((genre, index) => [genre, plays[index]])
12    // 2. 묶어준 장르로 데이터 만들기
13    .forEach(([genre, play], index) => {
14      const data = genreMap.get(genre) || { total: 0, songs: [] }
15      genreMap.set(genre, {
16        total: data.total + play,
17        songs: [...data.songs, { play, index }]
18          .sort((a, b) => b.play - a.play) // 재생 순으로 내림차순
19          .slice(0, 2),
20      })
21    })
22  return [...genreMap.entries()]
23    .sort((a, b) => b[1].total - a[1].total)
24    .flatMap(item => item[1].songs)
25    .map(song => song.index)
26}

[참고]

06-queue(큐)08-graph(그래프)