해시 테이블(Hash Table)

- 해시 테이블 (Hash Table)

Key 값을 해시 함수를 통해 변환한 값(해시 값)을 index로 삼아 Value 데이터를 저장하는 자료 구조이다.

내부적으로 배열을 사용하여 데이터를 저장하고, 고유의 index로 접근하기 때문에 빠른 검색 속도(충돌이 일어나지 않는 경우에 O(1))를 갖는다.

 

대표적인 해시 함수로는 Key 값을 테이블 크기로 나누어 계산(ex. 해시 값 = Key % 테이블 크기)하는 Division Method과 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘으로 Key 값을 ASCII 코드로 바꾸고 값을 합한 데이터를 이용하는 Digit Folding 등이 있다. 하지만 문제는 아무리 좋은 해시 함수를 이용한다해도 비둘기집의 원리에 의해 충돌이 발생할 확률이 있다.

이러한 충돌을 해결하는 방법으로 크게 두 가지가 있다.

 

1. 개방 주소법 (Open Addressing)

  충돌 발생 시 인접한 비어있는 버킷에 저장하며 세부적으로 3가지 종류가 있다.

  1) Linear Probing : 고정폭으로 이동하여 빈 공간을 찾음

  2) Quadratic probing : 제곱수로 이동하여 빈 공간을 찾음

  3) Double Hashing : 또 다른 해시 함수를 사용하여 빈 공간을 찾음

 

 

 - 장점

  1) 저장 공간을 추가할 필요 없이 해시 테이블 내에서 데이터 저장 및 처리가 가능

 

 - 단점

  1) 저장 공간을 찾는 과정이 길어지는 불필요한 상황이 발생할 수 있음

  2) 데이터 길이가 늘어나면 그에 해당하는 저장소를 마련해야 함

 

 

2. 분리 연결법 (Separate Chaining)

  Linked List 또는 RB Tree 등을 사용하여 추가적인 공간을 활용하여 해결하는 방식

 

 

 - 장점

  1) 한정된 저장소를 효율적으로 사용할 수 있다.

  2) 상대적으로 적은 메모리를 사용한다.

 

 - 단점

  1) 한 해시에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율이 낮아진다.

  2) 외부 저장 공간을 사용한다.