해시(Hash)

해시(Hash)란?

해시는 데이터를 고정된 크기의 값으로 변환하는 함수 또는 과정을 의미함.
쉽게 말해, 입력값을 일정한 규칙으로 ‘압축’하여 짧은 고유 값으로 바꾸는 기술임.

예를 들어, "apple" → 1024, "banana" → 5321" 과 같이 임의의 데이터를 일정한 크기의 숫자나 문자열로 매핑함.
이렇게 생성된 값을 해시값(Hash Value) 또는 해시코드(Hash Code) 라고 부름.

---

왜 사용하는가?

1. 빠른 탐색
   • 배열처럼 인덱스로 접근하기 어려운 데이터를 O(1) 시간에 접근 가능하게 함.
   • 예를 들어, 회원 이름으로 ID를 찾는 경우, 일일이 순회하지 않고 해시값을 키로 즉시 접근 가능함.
2. 중복 검사
   • 데이터의 무결성 확인에 활용함.
   • 파일 다운로드 시 해시값을 비교해 원본과 동일한지 검증할 수 있음.
3. 암호화
   • 비밀번호를 저장할 때 원문 대신 해시값으로 변환해 보관함.
   • 원래 비밀번호를 역으로 계산하기 어렵기 때문에 보안에 유리함.

---

해시 함수(Hash Function)

해시 함수는 임의의 길이 데이터를 고정된 크기의 해시값으로 매핑하는 함수임.
좋은 해시 함수의 조건은 다음과 같음.

조건	설명
균등 분포성	입력값이 다르면 해시값도 고르게 분포해야 함
결정적 특성	같은 입력값은 항상 같은 해시값을 반환해야 함
충돌 최소화	서로 다른 입력값이 같은 해시값을 갖는 경우를 줄여야 함

예시 (간단한 해시 함수):

function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash + str.charCodeAt(i) * 31) % 100;
  }
  return hash;
}

console.log(simpleHash("apple")); // 예: 42
console.log(simpleHash("banana")); // 예: 17

---

해시 충돌(Hash Collision)

서로 다른 입력값이 같은 해시값을 가질 때 충돌(Collision) 이 발생함. 충돌은 해시 구조의 필연적인 문제이므로, 보완 방법이 필요함.

1️⃣ 체이닝(Chaining)

• 같은 해시 인덱스에 여러 데이터를 연결 리스트 형태로 저장함.
• 충돌 시 해당 인덱스 리스트에 노드를 추가함.

2️⃣ 개방 주소법(Open Addressing)

• 충돌이 발생하면 빈 슬롯을 탐색해 다른 위치에 저장함.
• 예: 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing)

---

해시 테이블(Hash Table)

해시 테이블은 해시 함수를 사용해 (Key, Value) 형태로 데이터를 저장하는 자료구조임. 자바스크립트의 Map이나 Object, 파이썬의 dict, 자바의 HashMap 등이 이에 해당함.

const hashTable = new Map();
hashTable.set("apple", 10);
hashTable.set("banana", 20);

console.log(hashTable.get("apple")); // 10
console.log(hashTable.has("banana")); // true

• 삽입, 탐색, 삭제 모두 평균적으로 O(1)에 수행 가능함.
• 단, 충돌이 많아지면 성능이 O(n)까지 떨어질 수 있음.

---

알고리즘 예시

프로그래머스 - 완주하지 못한 선수

내가 푼 방식

function solution(participant, completion) {
    var answer = '';
    participant.sort();
    completion.sort();
    
    for(let i = 0 ; i < participant.length ; i++) { 
        if(participant[i] !== completion[i]) return participant[i];   
    }
    return answer;
}

• 정렬 후 비교 방식
• 시간 복잡도 O(n log n)

HashMap(해시 테이블) 방식 풀이

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

  // 참가자 이름을 해시맵에 저장
  for (let p of participant) {
    map.set(p, (map.get(p) || 0) + 1);
  }

  // 완주한 사람은 -1 처리
  for (let c of completion) {
    map.set(c, map.get(c) - 1);
  }

  // 값이 1인(=완주하지 못한) 사람 찾기
  for (let [key, value] of map) {
    if (value > 0) return key;
  }
}

• 이름별 카운트 저장
• 시간 복잡도 O(n)

해시(Map)을 이용하면 “이름별 등장 횟수”를 빠르게 기록하고, 완주자 목록에서 하나씩 차감하여 남은 1명을 O(n)에 찾을 수 있음.

프로그래머스 - 전화번호 목록

function solution(phone_book) {
  var answer = true;
  const phoneBookSet = new Set(phone_book);

  for (let phone of phone_book) {
    for (let i = 1; i < phone.length; i++) {
      const prefix = phone.slice(0, i);
      if (phoneBookSet.has(prefix)) return false;
    }
  }
  return answer;
}

• 접두어 해시 탐색
• 시간 복잡도 O(n * m)

---

END