해시 테이블

해시 테이블

키(Key)와 값(Value)의 쌍을 저장하고 검색하는 데 사용되는 자료구조

 

용어

1. 해시 함수(Hash Function):
   • 키를 고정된 길이의 해시 값으로 변환하는 함수
   • 같은 입력값에 대해서는 값은 출력 값이 보장
2. 해시 값(Hash Value): 해시 함수에 의해 계산된 키의 고정된 길이의 결과물
3. 해시 충돌(Collision): 서로 다른 데이터가 동일한 해시 값으로 매핑되는 현상
4. 해시 버킷(Hash Bucket): 해시 테이블 내에서 각각의 데이터를 저장하는 공간
5. 적재율(load factor): 할당된 키의 개수 / 해시 버킷의 크기, 일정 수준 이상 되면 해시 테이블 확장 필요
6. 재할당(Rehashing): 적재율이 일정 이상 되면 해시 체이블을 새로 생성해 데이터 옮김

해시 충돌(Collision)

1. 비둘기집 원리에 따라 충돌 가능
   • n개의 비둘기를 m개의 집에 넣을 때, 적어도 한 집에는 ⌈n/m⌉ 마리 이상의 비둘기가 들어 있어야 함
2. 충돌 해결법
   • 체이닝(Chaining) : 같은 해시 값에 대한 데이터를 연결 리스트 등의 자료구조로 연결하여 저장
   • 개방 주소법(Open Addressing) : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
     • 선형 탐사(Linear Probing) : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
       • 특정 위치에 데이터가 집중되는 클러스터링(Clustering) 현상 발생 확률 높음
     • 제곱 탐사(Quadratic Probing): 충돌 횟수의 제곱수로 옮겨 해시값의 중복을 피함
     • 이중 해싱(Double Hashing): 두 번째 해시 함수를 이용하여 다음 해시 버킷을 검사하여 데이터를 옮김

시간복잡도

	평균	최악 (모든 항목이 하나의 버킷에 저장)
탐색	O(1)	O(N)
삽입	O(1)	O(N)
삭제	O(1)	O(N)

 

사용 목적

1. 데이터 검색 및 조회:  해시 함수를 사용하여 데이터를 해시 값으로 변환하고, 해당 해시 값에 대응하는 버킷에 데이터를 저장하고 검색
2. 데이터 무결성 확인: 데이터가 변경되면 해시 값도 변경되므로, 해시 값이 동일하면 데이터가 변경되지 않았음을 확인 가능
3. 암호화: 단방향 해시 함수는 암호화에 사용