자료 구조 : 해시 테이블

오늘은 

자료구조 해시 테이블에 대해 공부한 내용을 요약합니다.

 

해시 테이블 

Key & Value로 저장되는 자료구조입니다. 빠르게 데이터를 검색할 수 있으며 이는 해시 테이블 내부에 버킷으로 데이터를 저장하기 때문입니다. 해시 테이블은 각각의 Key 값에 해시 함수를 적용하여 index를 생성하고, 이 index에 해당하는 버킷에 값을 저장하거나 검색하는 데 사용하게 됩니다. 

 

시간 복잡도 

해시 테이블은 Key값으로 Value를 한 번에 불러올 수 있기 때문에 평균적으로 0(1)에 시간 복잡도를 가집니다. 

 

해시 충돌 

해시 함수가 index를 생성할 때 전부 Unique 한 값을 가지는 건 아닙니다. 글자 수를 환산해서 index를 반환하는 해시 함수가 있다면, Key 값의 글자 수가 같을 때 같은 index를 생성하게 될 것입니다. Value 값이 같은 index를 갖게 된다면, 같은 버킷에 저장되게 되며 버킷 안에 배열의 형태로 저장될 수 있습니다. 이때는 Key 검색 후 선형 탐색이 이뤄져야 하는데 극단적인 경우라면 시간 복잡도가 0(n)까지 증가할 수 있습니다. 

 

해결 방법 

1. 분리 연결볍 Separate Chaining

분리 연결법은 버킷에 값을 그대로 저장하는 것이 아닌, 버킷의 링크드리스트에 차곡차곡 저장합니다. 해시 충돌이 생겼을 때 링크드리스트에 추가하는 방식으로 해결하며 조회할 때에는 링크드리스트에서 키를 선형 탐색하게 됩니다. (위에서의 예시, 선형 탐색으로 시간복잡도가 증가할 수 있습니다.)

2. 개방 주소법 Open Addressing

개방 주소법은 해시 충돌이 생겼을 때, 다른 비어있는 버킷을 찾는 방법입니다. 비어있는 버킷을 찾을 때, 선형 탐색, 제곱 탐색, 이중 해시 등의 방법을 사용할 수 있습니다.