해시(Hash)

데이터를 키(Key)로 접근할 수 있도록 해주는 자료구조

해시 함수를 통해 데이터를 인덱스로 매핑하여 빠른 검색과 삽입, 삭제를 가능하게 함

주로 해시 테이블로 구현되며, JavaScript의 Object, Map, Set 등이 해시 구조 기반

• 빠른 탐색 속도로 알고리즘 문제에서 자주 사용
• 주어진 값의 존재 여부, 빈도 수, 짝 찾기, 중복 처리 등에 효과적
• 충돌(Collision) 발생 가능 → 해결 방식 필요
• 주요 구조: Hash Table, Set, Map, Counter, DefaultDict 등

해시 테이블(Hash Table)

Key-Value 쌍으로 데이터를 저장하는 자료구조

해시 함수를 통해 Key를 배열의 인덱스로 변환하고, 해당 위치에 데이터를 저장함

• 충돌 해결 방식: 체이닝, 오픈 어드레싱
• JS에서 Object, Map이 대표적인 해시 테이블 구현

// Object를 이용한 해시 테이블
const hashTable = {};
hashTable["apple"] = 3;
hashTable["banana"] = 5;

console.log(hashTable["apple"]); // 3

시간 복잡도

충돌 없이 잘 구성된 해시 함수가 핵심

• 시간 복잡도
  • 평균: O(1) → 해시 함수 충돌이 거의 없고, 균등하게 분산될 경우
  • 최악: O(n) → 모든 키가 충돌할 경우 (예: 같은 버킷에 몰릴 경우)
  • 탐색/삽입/삭제 모두 평균적으로 O(1)
• 공간 복잡도
  • O(n): 저장되는 데이터 수에 비례하는 메모리 사용
  • 해시 테이블은 보통 실제 데이터 수보다 더 큰 공간(버킷 수)을 잡아두어 충돌을 줄임
  • 부가적으로 해시 함수가 사용하는 상수 공간도 있음

구현 코드

// 숫자 배열의 중복 여부 확인
const hasDuplicate = (nums) => {
  const seen = new Set();
  for (let num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
};

// 문자 등장 빈도수 카운트
const getCharCount = (str) => {
  const hash = {};
  for (let char of str) {
    hash[char] = (hash[char] || 0) + 1;
  }
  return hash;
};

대표 문제 유형 및 핵심

문제 유형	패턴	해시 구조	핵심 포인트
중복 확인	단일 배열 확인	Set	빠른 존재 확인
짝 찾기	인덱스 저장	Map	target - num 탐색
아나그램	문자 빈도 비교	Object	동일한 문자 개수
최빈값	정렬 없이 빈도	Map	값 + 빈도 저장
교집합	배열 비교	Set	includes()보다 빠름