Hash Table

Clean·2025년 3월 31일

해시 테이블 (Hash Table)

Hash Table은 내부적으로 해시 함수를 통해 key를 배열 인덱스로 바꾸고, 그 인덱스에 value를 저장한다.

key로 value를 찾는 방식이다보니 탐색, 삽입, 삭제의 시간 복잡도가 빠르다.

탐색, 삽입, 삭제 모두 O(1)

다만 문제점은 key를 배열의 인덱스로 변경하다보니 값이 쌓이면 Key의 충돌이 일어날 수 있다.

다양한 타입의 key값을 *해싱하여 배열 인덱스로 만드는 함수를 해시 함수라고 한다.

해시 함수는 같은 key를 항상 같은 해시 값을 반환한다.

해시 충돌은 key를 정수값(배열 인덱스)로 변환하는 해시 함수가,
다른 key들을 같은 정수값으로 반환하는 것을 말한다.

즉, 하나의 값에 두개의 키가 생기는 것을 말한다.

모든 key들을 고유한 해시값으로 만드는 것은 불가능하며 key의 충돌은 피할 수 없다.

다만 피할 수는 없더라도 대처 방안은 존재한다.

해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식으로,
선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정한다.
장점 : 추가적인 저장공간이 필요하지 않고, 삽입삭제시 오버헤드가 적음
단점 : 해시 테이블에 자료 사용률에 따른 성능저하가 발생함