해시

관련 문제

프로그래머스

• 완주하지 못한 선수

  https://school.programmers.co.kr/learn/courses/30/lessons/42576

• javascript에서 해시를 이용하여 문제를 푸는 방법은 Map과 get, set 메소드를 이용하는 것이다.

Map

• 다음과 같이 선언한다.

let Object = new Map();

• Map은 같은 key를 가지는 pair는 최대 한 개만 존재할 수 있다.
• associative array, ditionary 라고 불리기도 한다.
• 전화번호부나 count를 해야하는 투표 같은 곳에 사용할 수 있다.
• 순서가 없는 배열에 관한 문제를 풀 때 주로 이용되는 알고리즘이다.

Hash function(해시 함수)란?

• 임의의 크리를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수이다.

• Hash table 에서 임의의 데이터를 정수로 변환하는 함수이다.

• 예를 들어 hash function의 input 값이 "문자열" 이라고 한다면 output값은 19283 같은 정수로 나오게 된다. 이 때 문자열 의 hash는 19283 이 된다.

• 이것을 모듈러 연산을 통해 hash table에 저장한다.

Hash table(hash map) 이란?

• 배열과 해시 함수를 사용하여 map을 구현한 자료 구조이다.
• 상수 시간으로 데이터에 접근하기 때문에 시간복잡도가 1에 수렴한다.

set("str", 1);

• set은 문자열과 정수를 인자로 받는다.
• Map에 주로 데이터를 추가 혹은 업데이트 할 때 사용하는 메소드이다.

let Object = new Map();
let str = "개발자";

console.log(Object.set(str, 1));

• 위와 같이 코드를 작성하게 되면 console => Map(1) { '개발자' => 1 } 이 찍힌다.

get("str")

• get은 문자열을 인자로 받으며 Map에 해당 문자열이 존재하지 않으면 undefined 를 반환한다. undefined는 논리연산 시 false로 인식한다.

let Object = new Map();
let str = "개발자";

Object.set(str, 1);
console.log(Object.get(str);

• console => undefined

hash table 동작 원리?

• 배열이 있다고 가정하자. 배열의 길이는 8이다. 이 때 배열의 길이 8은 Capacity라고 부르며 배열의 0~7 index의 공간은 bucket 혹은 slot 이라고 부른다.

• 예를 들어,
  ("010-1111-1111", "개발자") 라는 데이터가 존재한다. 이를 해시함수에 인자로 보내어 해시 값을 구한다. 그리고 해시 값을 Capacity 값으로 모듈러 연산을 하여 bucket을 구한 후 해당 bucket에 데이터를 저장한다.

피드백 환영입니다!