Hash

Syoee·2023년 12월 14일

Algorithm

목록 보기

6/6

1. Hash란?

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수 알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.
그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다.
해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.
암호용 해시 함수는 매핑된 해싱 값만을 알아가지고는 원래 입력 값을 알아내기 힘들다는 사실에 의해 사용될 수 있다.
또한 전송된 데이터의 무결성을 확인해주는 데 사용되기도 하는데, 메시지가 누구에게서 온 것인지 입증해주는 HMAC를 구성하는 블록으로 사용된다.
해시 함수는 결정론적으로 작동해야 하며, 따라서 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다)
해시 함수의 질은 입력 영역에서의 해시 충돌 확률로 결정되는데, 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가하게 된다.

Recap

해시함수는 하나의 주어진 출력에 대하여 이 출력으로 사상시키는 하나의 입력을 찾는 것이 계산적으로 불가능하고, 하나의 주어진 입력에 대하여 같은 출력으로 사상시키는 또 다른 입력을 찾는 것이 계산적으로 불가능하다는 두 가지 성질을 만족하면서 임의의 비트열을 고정된 길이의 비트열로 사상시키는 함수이다.

2. Hash의 특징

같은 종류의 자료를 묶어서 파악할 수 있다.

3. 알고리즘

해시함수 알고리즘은 긴 길이의 데이터를 짧은 길이의 데이터로 변환하는 알고리즘으로 따라서 제3자는 짧은 길이의 데이터로부터 원래의 데이터를 복구할 수 없어야 하며, 동일한 출력을 갖는 서로 다른 데이터를 찾을 수 없어야 한다.

4. 예시

프로그래머스,해시,완주하지 못한 선수 with JavaScript

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
function solution(participant, completion) {
    var answer = '';
    return answer;
}

해답

function solution(participant, completion) {
    const map = new Map();
    for(let i = 0; i < participant.length; i++) {
        let a = participant[i], 
            b = completion[i];
        map.set(a, (map.get(a) || 0) + 1);
        map.set(b, (map.get(b) || 0) - 1);
    }
    for(let [k, v] of map) {
        if(v > 0) return k;
    }
    return 'nothing';
}