[자료구조] 해시 테이블(Hash Table)

키(Key)에 데이터(Value)를 저장해, 키 값으로 데이터에 직접 접근이 가능한 자료구조

보통 해시 테이블 크기만큼 배열을 생성해 사용한다.

 

Python의 Dictionary가 해시 테이블에 해당한다.

 

 

• 해시(Hash): 임의의 값을 고정 길이로 변환하는 것
• 해싱 함수(Hashing Function): 산술 연산으로 키를 연산해 데이터의 위치를 찾을 수 있는 함수
• 해시 값(Hash Value) / 해시 주소(Hash Address): 데이터가 저장된 위치(주소)
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간

 

해시 테이블의 장단점과 주요 용도

 

• 장점: 키를 이용해 데이터를 바로 꺼낼 수 있기 때문에 데이터 저장/읽기 속도가 빠르다.
         키에 대응하는 데이터가 저장돼 있는지 바로 확인할 수 있기 때문에 데이터 중복 체크가 쉽다.
• 단점: 일반적으로 저장 공간이 조금 더 많이 필요하다.

         여러 키에 해당하는 주소가 동일한 경우(해시 충돌), 충돌 해결을 위한 별도의 자료구조가 필요하다.

해시 테이블은 검색이 많이 필요하거나 저장/삭제/읽기가 빈번한 경우, 캐시 구현(중복 확인이 쉽기 때문)에 주로 사용된다.

 

해시 테이블의 시간 복잡도는 O(1)

Collision이 모두 발생하는 최악의 경우 O(n)

 

 

충돌(Collision) 해결 알고리즘

1. Chaining 기법

개방 해싱(Open Hashing) 기법 중 하나로, 해시 테이블 저장 공간 외의 다른 공간을 활용하는 기법

충돌이 일어나면, 연결 리스트를 사용해 데이터를 뒤에 연결해 추가로 저장

 

 

2. Linear Probing 기법

폐쇄 해싱(Close Hashing) 기법 중 하나로, 해시 테이블 저장 공간 내에서 충돌 문제를 해결하는 기법

충돌이 일어나면, 해당 해시 주소의 다음 address부터 탐색해 가장 처음 나오는 빈 공간에 저장

  -> 저장공간의 활용도를 높이기 위한 기법이다.

 

충돌을 줄이기 위한 방법으로는 해시 함수를 재정의하거나, 해시 테이블의 저장공간을 확대하는 방법이 있다.