해시테이블(Hast Table)에 대해 설명해 주세요.

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

• 빠른 검색 속도를 할 수 있는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

  • 각 Key는 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회할 수 있다.

  • 하지만 index 값이 충돌하는 해시충돌 이 발생할 경우, Chaining에 연결된 리스트들까지 검색해야 하므로 O(N)까지 증가할 수 있다.