[TIL] 자료구조 - hash table

Hash table

1.개요

해시 테이블(Hash table)은 키(Key)와 밸류(Value) 쌍으로 자료를 저장하는 구조이다.
각 키는 고유하며 키를 이용하여 밸류에 빠르게 접근할 수 있다.
일반적으로 해시 맵(Hash map) 과 동일한 의미로 사용된다.

2.상세

데이터에 접근하는 경우에도 O(1)의 시간 복잡도를 가진다.

해시 테이블은 해시 함수(Hash function)을 이용하여 구현된다.

해시 테이블의 성능은 이 해시 함수 성능에 많은 영향을 받는다.

함수는 키를 해시 값으로 변환하는 역할을 하며, 서로 다른 키가

같은 해시 값을 가지는 경우 해시 충돌(Hash collision)이 발생하여 성능이 저하된다.

또한 해시 테이블은 동적으로 메모리를 할당해 메모리가 제한된 경우에는 사용하기 어렵다.

때문에 데이터가 매우 적은 경우나 순서가 중요한 경우에는 배열을 사용하는 것이 좋다.