해시 테이블

키를 해시 함수(Hash Function)로 배열 인덱스로 바꿔 값을 저장하는 자료구조. 조회·추가·삭제가 평균 O(1)이다. JavaScript의 객체와 Map·Set, 파이썬의 dict·set(파이썬 기본 컬렉션), 자바의 HashMap이 모두 해시 테이블이다.

좋은 해시 함수

• 빠르다(가능하면 상수 시간)
• 키를 인덱스 전체에 고르게 퍼뜨린다
• 같은 입력에는 항상 같은 출력을 낸다(결정적)

테이블 크기를 소수로 잡으면 충돌이 덜 생기는 경향이 있다.

충돌 다루기

서로 다른 키가 같은 인덱스로 가는 충돌(Collision)은 피할 수 없다.

• 분리 연결법(Separate Chaining): 각 칸에 리스트를 두고 같은 칸에 온 쌍을 이어 붙인다
• 선형 탐사(Linear Probing): 칸이 차 있으면 다음 빈칸을 찾아 넣는다. 한 칸에 하나만 둔다

function hash(key: string, size: number) {
  let h = 0
  for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % size
  return h
}

복잡도의 단서

평균은 O(1)이지만 충돌이 몰리면 최악 O(n)이 된다. 채워진 비율(적재율, Load Factor)이 높아지면 테이블을 키워 다시 배치한다. 해시 테이블 자체는 키의 순서를 보장하지 않는다(JavaScript Map과 파이썬 dict는 삽입 순서를 따로 기억한다). 정렬된 순서가 필요하면 다른 구조를 쓴다.

빈도 세기 같은 풀이 패턴과 "배열 find 대신 Map 조회"라는 실무 최적화의 바탕이다(빅오 표기법). 해시는 캐시(LRU 캐시와 캐시 계층 비교)와 샤딩(샤딩)의 데이터 분배에도 쓰인다. 비밀번호 해싱은 이름만 같고 목적이 다른 이야기다(비밀번호 저장: 인코딩·암호화·해싱).