[2023-09-25] 자료구조 & 알고리즘 - 해시테이블

해시테일블은 사물함이라고 생각하면 된다. 

사물함 각 칸에는 이름과 번호가 있어서 쉽게 위치를 찾을 수 있다.

 

해시테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게된다.

그럼 index는 어떻게 구할까?

 

해시테이블

- 키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형자료구조

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

 

 

해시 함수

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

- 해시함수는 특정한 구현 방법이 있지 않아서 사용자 임의대로 만들면 된다.

- 예를 들어 입력받은 문자열을 각 문자열의 아스키코드를 더한 값을 해시로 정할 수 있다.

 

해시테이블의 문제점

만약 해시 함수의 결과가 동일하여 겹친다면 문제가 생긴다.

-> 이를 해시 충돌이라고 부른다.

 

해시충돌을 해결하는 방법은 4가지가 있다.

 

1. 선형 탐사법

- 충돌이 발생하면 단순히 인덱스를 옆으로 한 칸 이동한다.

- 특정영역에 데이터가 몰릴 수 있다는 단점이 있다.

- 이동한 버킷에서 또 충돌이 발생하면 충돌이 발생하지 않을 때까지 이동한다. 최악의 경우 선형시간이 걸리게 된다.

 

2. 제곱 탐사법

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

- 충돌이 발생할 수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형탐색법보다 덜하다.

 

3. 이중 해싱

- 충돌이 발생하면 다른 해시함수를 이용하여 새로운 인덱스를 만든다.

- 만약 또 충돌이 발생하면 충돌이 발생하지 않을 때까지 두번째 해시함수로 인덱스를 계속해서 만든다.

 

4. 분리 연결법

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

- 즉 해시테이블의 요소를 연결리스트로 만들어 충돌이 발생한 버킷에 그대로 요소를 추가한다.

-대신 이 방법은 최악의 경우 하나의 버킷이 무한정 늘어날 수 있다는 단점이 있다.

 

 

 

연결리스트는 데이터를 찾을 때 O(n) 즉 선형시간만큼 걸린다.

 

배열은 인덱스를 모를 경우 O(n) 즉 선형시간만큼 걸린다.

 

반면 해시테이블을 사용하면 O(1)에 찾을 수 있다.]

따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.

최악의 경우 탐색이 선형시간만큼 걸릴 때도 있지만 연결리스트와 배열보다는 안정적이다.

 

 

 

JavaScript에서 사용하는 방법

1. Array를 이용한 방법

const table = [];
table["key"] = 100;
console.log(table["key"]); // 100
delete table["key"];

- 배열은 실제로 객체타입이라 해시테이블처럼 사용할 수 있지만 올바른 사용방법이 아니다.

 

2. Object를 이용한 방법

const table = {};
table["key"] = 100;
console.log(table["key"]); // 100
delete table["key"];

- 제일 간단하고 정석적인 방법

 

3. Map을 이용한 방법

- 기존 객체와 다르게 Key값으로 object타입이나 배열같은 복잡한 타입도 Key로 사용가능하다.

- 객체의 경우 들어오는 값이 정수가 아닌 경우 전부 문자열로 바꾸기 때문에 다양한 타입으로 하려면 Map을 이용하는 것이 좋다.

- 여러 편한 메소드와 순회를 편하게 할 수 있다.

const table = new Map();
table.set("key",100);
console.log(table["key"]); // undefined
console.log(table.get("key"); // 100

const object = { a : 1}
table.set(object, "A1"); // Map은 Object도 key로 쓸 수 있다.
table.delete(object);

console.log(table.keys()); // { "Key" }
console.log(table.values()); // { 100 }
table.clear();
console.log(table.values()); // { }

 

4. 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");
table.add("key3");
console.log(table.size) // 2

table.clear();
console.log(table.size) // 0

 

해시테이블관련 코딩테스트

https://school.programmers.co.kr/tryouts/101814/challenges?language=javascr 

 

내 코드

function solution(genres, plays) {
    var answer = [];
    let arr=[];
    let so=new Map();
    for(var i=0;i<genres.length;i++){
        let [gen,pla,idx,gen_sort]=[genres[i],plays[i],i,0];
        if(so.has(gen)) so.set(gen,so.get(gen)+pla)
        else so.set(gen,pla);
        arr.push([gen,pla,idx,gen_sort]);
    }
    let so_arr=[...so];
    so_arr=so_arr.sort((a,b)=>b[1]-a[1]);
    for(var i=0;i<so_arr.length;i++){
        for(var j=0;j<arr.length;j++){
            if(so_arr[i][0]==arr[j][0]) arr[j][3]=i;
            
        }   
    }
    arr=arr.sort((a,b)=>{
        if(a[3]<b[3]) return -1; //-1은 자리바꿈하지않음 (default인 오름차순)
        else if(a[3]>b[3]) return 1; //1은 자리바꿈함 (내림차순)
        else if(a[1]<b[1]) return 1;
        else if(a[1]>b[1]) return -1
        else if(a[2]<b[2]) return -1;
        else if(a[2]>b[2]) return 1;

        
    });
    for(var i=0;i<so_arr.length;i++){
        let cnt=0;
        for(var j=0;j<arr.length;j++){
            if(so_arr[i][0]==arr[j][0] && cnt!=2){
                cnt++;
                answer.push(arr[j][2]);
            }
            if(cnt>2) break;
        }   
    }
    
    return answer;
}

 

다른 풀이

// 1, 같은 장르끼리 묶어야한다.
// 2. 묶인노래들을 재생 순으로 정렬을 해야한다.
// 3. 노래를 2개까지 자르는 작업을 해야한다.

// 핵심키워드는 "묶는 것" 과 "정렬"

function solution(genres, plays){
	const genreMap = new Map();
    geres.map((genre,index) => [genre,plays[index]])
    .forEach(([genre,play], index)=>{
    	const data = genreMap.get(genre) || { total : 0 , songs : [] };
    	genreMap.set(genre, {
        	total : data.total + play
            songs: [...data.songs, {play,inde}].sort((a,b)) => b.play - a.play).slice(0,2)
        })
    })
 	//Map을 배열로 만드는 entries
    //객체를 하나의 배열로 만드는 flatMap()
    return [...genreMap.entries()]
    		.sort((a,b) => b[1].total - a[1].total)
    		.flatMap(item => item[1].songs)
    		.map(song => song.index)
}

 

 

[참고] flatMap

위와 같은 데이터를 아래와 같이 바꿔준다.