[자료구조]해시 테이블

해시테이블이란

 

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조이다.

 

삽입은 O(1) 이며 키를 알고 있다면  삭제, 탐색도 O(1)로 수행한다.

(상수시간만큼 걸린다는 의미)

 

간단히 말해서

 

사물함처럼 한정된 배열에 key를 index로 변환하여 값들을 넣는다.

 

hashBrown처럼 값들을 잘게 잘라 값으로 넣는다고 생각하면 쉽다.

 

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

 

---

HashCollision / 해시충돌이 일어난다면?

 

선형 탐사법 : 충돌이 발생하면 옆으로 한칸 이동한다.

제곱 탐사법 : 충돌이 발생하면 발생한 횟수의 제곱만큼 옆으로 이동한다.

이중 해싱 : 충돌이 발생하면 달느 해시 함수를 이용한다.

분리 연결법 : 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

---

 

function solution(genres, plays) {
    let genreTotalPlays = {};
    let genreSongs = {};
    for (let i = 0; i < genres.length; i++) {
        let genre = genres[i];
        let play = plays[i];
        if (genreTotalPlays[genre] == undefined) {
            genreTotalPlays[genre] = play;
            genreSongs[genre] = [{id: i, play: play}];
        } else {
            genreTotalPlays[genre] += play;
            genreSongs[genre].push({id: i, play: play});
        }
    }

    let sortedGenres = [];
    for (let genre in genreTotalPlays) {
        sortedGenres.push([genre, genreTotalPlays[genre]]);
    }
    sortedGenres.sort(function(a, b) {
        return b[1] - a[1];
    });

    let answer = [];
    for (let i = 0; i < sortedGenres.length; i++) {
        let genre = sortedGenres[i][0];
        let songs = genreSongs[genre];
        songs.sort(function(a, b) {
            if (a.play == b.play) {
                return a.id - b.id;
            }
            return b.play - a.play;
        });
        answer.push(songs[0].id);
        if (songs.length > 1) {
            answer.push(songs[1].id);
        }
    }

    return answer;
}

응용코드

 

 

강의출처 : 프래그래머스

https://school.programmers.co.kr/learn/courses/13213/lessons