해시 [Hash]

| 해시 테이블 이란?

해시는 유일한 값을 저장하기 위한 자료구조이다.

key-value 를 저장하기 위해 사용된다.

배열과는 다르게 순서를 가지지 않으며 거의 모든 언어에서 해시라는 구조가 사용된다.

그 이유는 값을 찾는데에 상당히 빠른 시간으로 처리할 수 있다.

기존 자료구조인 이진탐색트리 / 배열 에 비해 빠른 속도를 가진다.

Python 에서는 Dictionaries 가 있으며 JavaScript는 Objects / Maps 로 해시 테이블을 구현할 수 있다.

배열을 사용하여 값을 저장하고 그 값을 사용해야 할 때 우리는 해당 값을 가지고 있는 순서 즉 index를 알아야 한다.

하지만 해시는 내가 지정한 key로 원하는 값을 추출할 수 있다.

 

| 직접 주소 테이블 (Direct Address Table)

직접 주소 테이블은 입력 받은 value가 곧 key가 되는 데이터 매핑 방식이다.

내가 확인하고 싶은 값이 어디에 있는지 알고 있기에 값을 수월하게 찾을 수 있다.

 

직접 주소 테이블

위의 자료 사진처럼 key와 value는 동일하다.

그래서 빠르게 값을 찾을 수 있다.

하지만 위의 자료사진을 보았을 때 0~4, 6~7은 값이 비어있다.

이것을 잘 생각해보면 직접 주소 테이블의 단점을 catch 할 수 있다.

저장 된 데이터를 제외한 빈 공간은 값은 없지만 메모리 공간을 할당되어 있는 상태이다.

공간적인 효율성이 떨어진다.

코드로는 이렇게 구현 할 수 있다.

 

직접 주소 테이블 코드 구현

 

| 해시 함수

해시 함수는 임의의 크기의 데이터를 고정된 크기의 고유한 값으로 매핑하는 함수이다.

주로 데이터의 무결성을 확인하거나 데이터를 식별하는데에 사용한다.

직접 주소 테이블의 단점을 보완할 수 있는것이 해시 테이블 이다.

해시 테이블은 직접 주소 테이블 처럼 값을 index로 사용하는 것이 아닌 해시 함수를 한번 통과 시킨 이후

사용한다.

해시 함수는 임의의 길이를 가지는 데이터를 고정된 길이의 데이터로 매핑 하는 함수이다.

이때 이 함수가 리턴하는 결과물을 Hash라고 부른다.

 

해시 함수는 다음과 같은 특성을 가진다.

 

| 고정된 출력 크기

- 어떠한 입력 크기의 데이터도 고정된 크기의 출력으로 매핑한다.

 

- 고유한 출력

- 서로 다른 입력에 대해 동일한 해시 값이 생성되는 충돌을 최소화 해야한다.

해시 값은 고르게 분포되어야 하며 충돌을 최소화 해야한다.

충돌을 최소화 시키는 방법은 선형 탐사법 / 제곱 탐사법 / 이중해싱 / 분리 연결법 이 있다.

 

- 고속 연산

- 빠르게 계산될 수 있어야 한다.

 

 

| 해시 함수가 주로 사용 되는 곳

- 데이터 무결성 검증

- 파일이나 메시지의 무결성을 확인하기 위해 해시함수를 사용한다

 

- 비밀번호 저장

- 사용자의 비밀번호를 저장할 때 해시 값으로 저장해서 보안을 강화한다

 

- 데이터베이스 검색

- 해시 함수를 사용하여 데이터를 빠르게 검색하고 인덱싱을 한다.

 

 

| 프로그래머스 해시 문제풀이

레벨 1의 완주하지 못한 선수이다.

인자로 participant와 completion 이 주어진다.

participant 은 참여한 선수가 담긴 배열

completion 은 완주한 선수의 배열이다.

완주하지 못한 선수를 출력하면 된다.

 

function solution(participant, completion) {
  const participantMap = new Map();

  participant.forEach((value) => {
    if (participantMap.has(value)) {
      participantMap.set(`${value}`, participantMap.get(`${value}`) + 1);
    } else {
      participantMap.set(value, 1);
    }
  });

  completion.forEach((value) => {
    participantMap.set(`${value}`, participantMap.get(`${value}`) - 1);
    if (participantMap.get(`${value}`) === 0) {
      participantMap.delete(`${value}`);
    }
  });

  return Array.from(participantMap)[0][0];
}

 

예전에는 배열의 sort와 forEach로만 구현을 했었던 문제이다.

하지만 해시 단원에 있는 이유가 있을 것이고 충분히 해시로 구현이 가능하다고 생각해서 문제를 다시 풀었다.