해시 테이블 (Hash Table)

해시 테이블은 효율적인 탐색을 위한 자료구조로서 key-value 쌍의 데이터를 입력받는다. hash function h 에 key값을 입력으로 넣어 얻은 해시값 h(k) 에 해당하는 인덱스에 (key, value) 데이터 쌍을 저장한다. (key, value) 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 한다.

모든 데이터에 key 값은 무조건 존재해야 하며, 중복되는 key 값이 있어서는 안 된다.

특징

직접 주소화 테이블 (Direct Address Table)

해시 테이블의 기초가 되는 아이디어는 직접 주소화 테이블이다. 직접 주소화 테이블이란, key 값이 k인 데이터를 index k 위치에 저장한다. 예를 들어, key가 3이고 값이 '가'인 데이터는 배열의 3 인덱스 위치에 값 '가'를 저장하는 식이다.

직접 주소화 테이블을 사용했을 때, key 값에 따라 사용하지 않는 공간이 많이 생길 있으므로 공간 효율성이 떨어진다. 따라서 직접 주소화 방식은 (key, value) 데이터 쌍을 저장하기 위한 방식으로 한계가 있다.

해시 함수 (Hash Function)

해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 함수이다. 해시 테이블에서는 이 함수가 키를 받아 배열의 인덱스로 변환하는 데 사용된다. 이상적인 해시 함수는 서로 다른 키에 대해 충돌(같은 인덱스 할당)이 적게 발생하도록 설계되어야 한다.

해시충돌 (Hash Collision)

해시 함수가 서로 다른 두 키를 동일한 인덱스로 매핑하는 경우, 이를 해시 충돌이라고 한다. 충돌을 처리하는 방법은 여러 가지가 있다.

• 체이닝 (Chaining)
  • 충돌이 발생하면 같은 해시값을 갖는 키들을 동일한 인덱스(버킷)에 연결 리스트 형태로 저장한다.
• 오픈 어드레싱 (Open Addressing)
  • 충돌이 발생하면 다른 인덱스를 찾아 데이터를 저장한다. 탐사 방식에 따라 선형 탐사, 제곱 탐사, 이중 해싱 등이 있다.
  • 선형 탐사
    • 충돌이 발생하면 인덱스를 순차적으로 증가시켜 빈 공간을 찾아 저장한다. 밀집된 데이터 군집이 형성될 수 있는 단점이 있다. 데이터의 밀집도가 높아지게 되면 밀집도가 높은 구간에서 해시 충돌이 날 확률이 올라가고, 충돌이 발생한 값이 밀집도를 가중시키므로 악순환이 될 수 있다.
  • 제곱 탐사
    • 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭이 아니라 제곱으로 늘어난다. 데이터의 밀집도가 선형 탐사법보다는 낮지만 데이터의 군집을 완전히 피할 수는 없다.
  • 이중 해싱
    • 두 개의 해시 함수를 사용해 충돌 시 다른 해시 함수를 통해 새로운 인덱스를 찾는다. 선형 탐사 및 제곱 탐사에 비해 연쇄적으로 충돌이 발생할 가능성이 낮아진다.

장점

• 빠른 데이터 접근
  • 해시 테이블의 가장 큰 장점은 평균적으로 데이터 접근, 삽입, 삭제가 상수 시간 복잡도(O(1))로 이루어진다는 것이다. 이는 데이터의 키를 해시 함수에 적용하여 배열의 인덱스를 직접 참조함으로써 이루어진다.
• 효율적인 키 기반 검색
  • 해시 테이블은 데이터가 특정 키에 매핑되므로, 키를 알고 있을 때 해당 데이터의 위치를 빠르게 찾을 수 있다. 이는 대량의 데이터에서 키에 기반한 검색을 신속하게 수행할 수 있게 한다.

단점

• 공간 효율성이 떨어진다.
  • 데이터가 저장되기 전에 미리 저장공간을 확보해야 하므로 저장공간이 부족하거나 공간이 낭비되는 경우가 생길 수 있다.
• 순차 접근이 어려움
  • 해시 테이블은 데이터가 저장되는 위치가 키와 해시 함수에 의해 결정되어 비순차적으로 저장된다. 데이터는 물리적 배열의 특정 위치(버킷)에 저장되며 이 위치는 일반적으로 입력된 키와는 관련이 없다. 따라서 데이터는 배열 내에서 무작위로 분포하게 되며, 이는 데이터를 순차적으로 저장하거나 접근하기 어렵게 만든다.
  • 해시 테이블은 순차적 데이터 탐색보다는 특정 키에 대한 빠른 접근을 목표로 설계되었다.
• 충돌 관리의 필요성
  • 해시 함수가 완벽하지 않기 때문에 충돌이 발생할 수 있으며, 이를 효과적으로 관리하지 못하면 성능이 저하될 수 있다.

시간복잡도

	Hash table	Linked list	Array
access	O(1)	O(n)	O(1)
insert	O(1)	O(1)	O(n)
append		O(1)	O(1)
delete	O(1)	O(1)	O(n)

시간복잡도는 저장, 삭제, 검색 모두 평균적으로 O(1)이지만 해시충돌로 인해 최악의 경우 O(n)이 될 수 있다.