Hash Map

---

Map은 키와 value를 pair로 갖고 있는 자료구조이다. 학번과 이름의 관계와 비슷하다. 학생을 나타내는 고유한 키값(학변)을 이용하면 동일 인물도 구분할 수 있다. 따라서 이 두가지 데이터를 하나의 쌍으로 저장하는 형식이 Map이다.(일반적인 Object와 매우 유사하지만 차이점 존재. 대표적으로 map은 어떠한 데이터 타입도 key값으로 저장 가능.)

: Hash Map은 Map과 같이 key&value를 쌍으로 저장한다는 점에서 동일하지만, Hash Function을 통해 key를 index로 변환한다는 차이점이 있다. 필요한 경우에만 할당된 메모리 크기를 조절하며 가능한 작은 크기를 유지한다.

What is Hash Function

: 어떠한 값을 넣으면 특정 값으로 변환 후 반환해주는 함수이다. 이때 동일한 input일 경우 항상 같은 ouput을 반환해주어야 좋은 hash function이라 할 수 있다. git commit이 대표적인 hash function을 사용한 예시이다. hash function은 비밀번호와 같이 암호화 후 저장해야 할 경우에 많이 사용된다.(※ 암호화 코드는 충분히 검증된 것을 사용해야 함. 만들어서 사용하려는 생각은 버리자 !)

아래는 스트링 값을 넣어주게될 경우 특정 interger값을 반환해 주는 간단한 hash function이다.

hashCode = function(str) {
    var hash = 0;
    if (str.length == 0) {
        return hash;
    }
    for (var i = 0; i < str.length; i++) {
        var char = str.charCodeAt(i); // returns an integer between 0 and 65535
        hash = ((hash<<5)-hash)+char;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

Hash Collisions

: hash code로 생성된 index가 key별 unique한게 가장 이상적이지만, 겹치는 경우는 어떻게 될까. 여러개의 key가 동일한 index를 부여받을 때 이를 hash collision이라 한다. 여러 방법이 있지만, 나는 충돌이 발생한 index번째 버킷에 key와 value를 쌍으로 하는 튜블을 배열의 형태로 추가해 해결했다.

Map을 이용한 알고리즘: 완주하지 못한 선수

---

문제: 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 찾는 알고리즘이다. 동명이인이 있는데 완료명단에는 한명의 이름만 있을 경우, 해당 선수는 완료하지 못했다고 가정한다.
(문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42576)

해결: 참여 선수명단을 이용해 선수명을 key로 참여횟수를 value로하는 map object를 생성했다. 이후 완료 명단에 있을 경우 참여횟수를 1씩 줄였다. 최종적으로 참여횟수가 1이 넘어갈 경우 해당 선수를 완료하지 못한 선수로 가정했다.

map도 보통의 객체처럼 object[key]와 같은 형식으로 value값을 찾을 수 있지만, object.get(key)처럼 get method를 사용하는 것이 바람직하다. value를 지정할 때도 object[key] = 1이 아닌 object.set(key,1)를 사용하자!

function solution(participant, completion) {
    const map = new Map();
    
  	// 참여선수 이름을 key로 default value로 1, 동명이인일 경우 +1
    participant.forEach(name => {
        if(map.get(name)===undefined){
            map.set(name,1);
        } else {
            map.set(name,map.get(name)+1);
        }
    });
  
  	// 완료선수명단에 이름이 있을 경우 value -1
    completion.forEach(name => {
        if(map.get(name)){
            map.set(name,map.get(name)-1);
        }
    });
    
    for(let [key, value] of map){
        if(value >= 1){
            return key;
        }
    }
}