해시법이란

키를 받아서 배열의 인덱스로 변환하는 걸 의미한다

효율적으로 저장하고 관리하려고 쓴다

체인법

같은 해시값을 가진 애들끼리 리스트로 연결하는 걸 말한다

충돌이 나면 해당 인덱스에 연결 리스트로 이어붙인다

따라서 같은 해시값을 갖는 데이터가 여러개 가능 ㅇㅇ

예시)

hash_table = [[] for _ in range(10)]  # 10칸짜리 테이블

def insert(key, value):
    hash_index = key % 10
    hash_table[hash_index].append((key, value))

• 장점

  • 간단하고 직관적

  • 해시테이블 크기보다 많은 데이터를 저장할 수 있음

• 단점
  • 연결 리스트 탐색으로 성능이 떨어질 수 있음 (O(n))

오픈주소법

충돌 발생시 빈칸 찾아 넣는 방식이다

종류

1. 선형 탐사법 (Linear Probing)
   • → 충돌나면 +1, +2,… 로 한 칸씩 뒤를 검사
2. 이차 탐사법 (Quadratic Probing)
   • → +1², +2²,… (즉, 점점 멀리 떨어진 곳을 검사)
3. 이중 해싱 (Double Hashing)
   • → 다른 해시 함수를 하나 더 써서 탐사 간격을 계산

예시)

hash_table = [None] * 10

def insert(key, value):
    index = key % 10
    while hash_table[index] is not None:
        index = (index + 1) % 10
    hash_table[index] = (key, value)

• 장점
  • 연결 리스트가 없어서 메모리 낭비가 적음
• 단점

  • 삭제 및 재배치가 까다로움

  • 해시테이블이 꽉 차면 성능이 급격히 저하됨

요약 비교