해시 함수 / 해시 테이블

해시 함수 (Hash Function)

• 데이터를 고정된 크기의 값(해시값 또는 해시코드)으로 변환하는 함수
• 다양한 응용 분야, 특히 컴퓨터 과학, 암호학에서 중요한 역할

 

주요 특성

1. 고정된 출력 길이 : 입력데이터의 크기와 상관없이 해시 함수 출력은 항상 고정된 길이 가짐
2. 결정적 : 동일한 입력 데이터에 대해 항상 동일한 해시값 반환. 입력 같으면 출력 항상 같음
3. 빠른 계산 : 빠른 시간 내에 해시값 계산 가능
4. 충돌 저항성 : 서로 다른 두 입력이 동일한 해시값 생성할 가능성 매우 낮음
5. 역상 저항성 : 주어진 해시값에 대해 원래 입력값 찾기 매우 어려움
6. 균등 분포 : 모든 출력값이 균등하게 분포되도록 함. 충돌 최소화

 

용도

1. 해시 테이블
   
   • 해시 테이블에서 키를 인덱스로 변환하는 데 사용
   • 데이터 검색, 삽입, 삭제 작업이 평균적으로 O(1) 시간 복잡도로 수행됨
2. 데이터 무결성 검사
   • 데이터 전송 및 저장 시 해시값 사용해 데이터의 손상 또는 변경 여부 확인 가능
   • ex) 파일 체크섬 계산하여 파일 무결성 확인
3. 암호학적 응용
   
   • 비밀번호 저장, 디지털 서명, 메시지 인증 코드(MAC) 등 보안 관련 다양한 응용 분야에서 사용
   • ex) 비밀번호 해시값으로 저장하여 해킹당해서 원래 비밀번호 알 수 없게 함
4. 디지털 지문
   • 문서나 파일의 해시값을 디지털 지문으로 사용해 내용 동일한지 확인
   • 중복 파일 찾거나 데이터 무결성 확인

 

---

 

해시 테이블 (Hash Table)

• 데이터 관리 및 검색에서 매우 효율적인 자료 구조
• 해시 함수 사용하여 키를 인덱스로 변환 - 데이터를 빠르게 검색, 삽입, 삭제 가능

 

작동 원리

1. 해시 함수
   
   • 키를 입력받아 정수값(해시값) 출력.
   • 해시 테이블의 인덱스로 사용
2. 배열
   • 배열의 각 위치(버킷)는 하나의 슬롯 의미 - 해시 함수의 출력값을 배열의 인덱스로 사용해 데이터 저장
3. 삽입
   • 새로운 데이터 삽입시, 키를 해시 함수에 전달하여 인덱스 계산 후 해당 위치에 데이터 저장
4. 검색
   • 데이터 검색시, 키를 해시 함수에 전달하여 인덱스 계산 후 해당 위치에서 데이터 찾음
5. 삭제
   • 데이터 삭제시, 키를 해시 함수에 전달하여 인덱스 계산 후 해당 위치의 데이터 삭제

 

충돌 해결 방법

• 해시 함수는 서로 다른 키에 대해 동일한 인덱스 생성할 수 있음 <- 충돌
• 이를 해결하기 위한 방법들

 

체이닝 (Chaining)

• 각 슬롯을 연결 리스트로 만들어 충돌 발생시 해당 슬롯의 리스트에 데이터 추가
• 동일한 인덱스에 여러 개의 항목 저장 가능

hash_table = [[] for _ in range(10)]
def insert(table, key, value):
    index = hash(key) % len(table)
    table[index].append((key, value))

 

 

개방 주소법 (Open Addressing)

• 충돌 발생시 다른 슬롯 찾아 데이터 저장
  1. 선형 탐사 (Linear Probing) : 충돌 시 다음 슬롯 차례로 검사하여 빈 슬롯 찾는 방법
  2. 제곱 탐사 (Quadratic Probing) : 충돌 시 제곱 간격으로 슬롯 검사하여 빈 슬롯 찾는 방법
  3. 이중 해싱 (Double Hashing) : 두 번째 해시 함수 사용하여 충돌 시 이동할 슬롯 결정