해시 개념 이해하기

해시 자료구조란?

데이터를 효율적으로 저장하고 검색하기 위한 데이터 구조로 주로 키-값 쌍으로 데이터를 저장한다. ex) Object, Map 객체 등

키를 해시 함수에 입력하여 해시 값을 얻고, 이 해시 값을 통해 데이터를 저장하거나 검색한다.

마치 도서관에서 원하는 책을 찾을 때 도서 분류 번호로 찾으면 빠르게 찾을 수 있는 원리와 같다.

 

예시

//간단한 해시 테이블 구현
class SimpleHashTable {
 constructor() {
  this.table = {};
 }
 
 //데이터 저장하기
 set(key, value) {
  this.table[key] = value;
 }
 
 //데이터 가져오기
 get(key) {
  return this.table[key];
 }
}

//사용 예시
const phoneBook = new SimpleHashTable();

//연락처 저장하기
phoneBook.set("철수", "010-1234-5678");
phoneBook.set("영수", "010-8765-4321");

//연락처 찾기
console.log(phoneBook.get("철수")); // 010-1234-5678

 

Map 객체

• Map은 키-값 쌍을 저장하는 자료구조
• 객체를 키로 사용할 수 있어서 일반 객체보다 더 유연함
• Map은 키의 순서를 보장하며, 반복 잡업에 최적화되어 있음

// Map 예시
const userMap = new Map();

// 데이터 추가 (키-값 쌍)
userMap.set('name', 'Alice');
userMap.set('age', 25);
userMap.set({id: 1}, 'object as key'); // 객체도 키로 사용 가능

// 데이터 접근
console.log(userMap.get('name')); // 출력: Alice

// 키 존재 여부 확인
console.log(userMap.has('age')); // 출력: true

// Map의 크기
console.log(userMap.size); // 출력: 3

// 데이터 삭제
userMap.delete('age');

 

Set 객체

Set 객체는 키 - 값 쌍으로 이루어지진 않았지만 내부적으로 해시 테이블을 사용하여 구현되어 있다.

그래서 검색속도가 빠름. 요소의 존재 여부를 확인할 때 O(1)의 시간 복잡도를 가진다.

해시 테이블의 특성을 이용해 자동으로 중복된 값을 제거한다. 각 값은 고유한 해시 값으로 변환되어 저장되기 때문이다.

 

const mySet = new Set();

//추가: 0(1) 시간 복잡도
mySet.add("사과");
mySet.add("바나나");

//검색: 0(1) 시간 복잡도
console.log(mySet.has("사과")); //true

//자동으로 중복 제거함
mySet.add("사과"); // 무시됨
console.log(mySet.size); // 2

 

해시(Hash) 함수

데이터를 특정 값으로 변환하는 함수

마치 우편번호처럼 데이터의 "주소값"을 만드는 것

 

// 해시 함수의 예시
function 해시함수(데이터) {
 let 해시값 = 0;
 for (let i = 0; i < 데이터.length; i++) {
  해시값 += 데이터.charCodeAt(i);
 }
 return 해시값;
}

console.log(해시함수("안녕")); // 45796
console.log(해시함수("안녕")); // 항상 같은 값(45796)

 

해시 테이블(Hash Table)

해시 함수를 사용해서 데이터를 저장하고 관리하는 자료구조 전체를 의미

마치 해시 값을 이용해 데이터를 정리해둔 창고 같은 것

class 간단한해시테이블 {
 constructor() {
  this.table = new Array(100);
  }

 저장하기(키, 값) {
  const 위치 = 해시함수(키);
  this.table[위치] = 값;
 }

 찾기(키) {
  const 위치 = 해시함수(키);
  return this.table[위치];
 }
}

const 저장소 = new 간단한해시테이블();
저장소.저장하기("사과", "빨간색");
console.log(저장소.찾기("사과"))

 

문제풀어보기 (프로그래머스)

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

프로그래머스

 

function solution(participant, completion) {
    var answer = '';
    
    // 1. Map 객체를 생성합니다. (이름-등장횟수를 저장)
    let participantMap = new Map();

    // 2. participant 배열을 순회하며 등장 횟수를 카운트합니다.
    for (let name of participant) {
        if (participantMap.has(name)) {
            // 이미 존재하면 등장 횟수 증가
            participantMap.set(name, participantMap.get(name) + 1);
        } else {
            // 처음 등장한 이름이면 1로 초기화
            participantMap.set(name, 1);
        }
    }

    // 3. completion 배열을 순회하며 등장 횟수를 감소시킵니다.
    for (let name of completion) {
        if (participantMap.has(name)) {
            participantMap.set(name, participantMap.get(name) - 1);
        }
    }

    // 4. Map을 순회하며 값이 1 이상인 키(이름)를 찾습니다.
    for (let [key, value] of participantMap) {
        if (value > 0) {
            answer = key; // 완주하지 못한 선수의 이름 저장
            break;
        }
    }

    // 5. 결과 반환
    return answer;
}