자료구조 | 해시(Hash) with JS

해시(Hash)

임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것

 

특정한 배열의 인덱스나 위치를 입력하고자하는 데이터의 값을 이요해 저장하거나 찾을 수 있다. 

해쉬를 이용하면 즉시 저장하거나 찾고자하는 위치를 참조할 수 있으므로 빠른 속도로 처리할 수 있다. 

 

저장된 데이터에 바로 접근해서 값을 가져올 수 있다. 찾고자하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간복잡도는 O(1)이다. 

 

테이블에 있는 값을 삽입, 수정, 삭제 하는 행위도 값이 어디있는지만 알고있으면 모두 한 방에 해결할 수 있다. 

 

해시테이블

해시함수라는 것에 한 번 통과시켜서 사용한다. 

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

 

어떤 값이 들어오든 간에 다 뭉개서 내가 원하는 길이의 값으로 만든다. 

 

key와 value로 이루어진 Map이라는 객체를 사용해서 해시테이블을 만들어서 사용한다. 

자바스크립트의 Map은 시간복잡도를 줄이는데 결정적인 역할을 한다.

 

Map 객체 사용하기

Map 객체 생성

const map = new Map();

 Map의 메소드인 set함수 사용해서 객체에 요소 추가

map.set('B', 1)

기존 값에다가 증가시키기

map.get('B', 1)

 

 

예제문제 | 학급회장

문제

학급회장을 뽑는데 후보로 기호 A,B,C,D,E 후보가 등록을 했다. 투표 용지에는 반 학생들이 쓴 후보의 기호가 쓰여있으며, 선생님은 그 기호를 발표하고 있다. 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력해라. 

 

입력예제 | BACBACCACCBDEDE

출력예제 | C

 

코드

const solution = (str) => {
  let answer;
  let student = new Map();

  for (let x of str) {
    if (student.has(x)) {
      student.set(x, student.get(x) + 1);
    } else {
      student.set(x, 1);
    }
  }

  // 가장 작은 정수를 비교군으로 설정
  let max = Number.MIN_SAFE_INTEGER;

  for (let [key, value] of student) {
    if (value > max) {
      max = value;
      answer = key;
    }
  }
  return answer;
}

const str = "BACBACCACCBDEDE";
console.log(solution(str));

 

 

예제문제 | 아나그램

문제

아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 주어지는 두 단어가 아나그램이면 YES를 출력하고, 아니면 NO를 출력해라.

 

입력예제 | AbaAeCe, baeeACA

출력예제 | YES

 

코드

const solution = (word1, word2) => {
  // 아나그램 : 알파벳 나열 순서는 다르지만 그 구성(알파벳과 그 개수)이 일치
  // 길이가 다른 두 개의 단어가 주어지면, 그 두 단어가 아나그램인지 판별
  // 대소문자 구별

  let answer = "Yes";

  // map1 을 기준 객체로 만들어 놓고 
  // map1 과 word2를 비교해서 key가 존재하는지 보고, 있으면 value 비교
  let map1 = new Map();

  for (let x of word1) {
    if (map1.has(x)) {
      map1.set(x, map1.get(x) + 1);
    } else {
      map1.set(x, 1);
    }
  }

  for (let x of word2) {
    if (!map1.has(x) || map1.get(x) === 0) {
      return "No";
    }
    map1.set(x, map1.get(x) - 1);
  }

  return answer;
}

const word1 = "abaCC";
const word2 = "Caaab";
console.log(solution(word1, word2));