해쉬 테이블

해시테이블은 key, value 형태로 데이터를 저장한다. key 값에 해시함수를 적용하여 value의 인덱스를 만들어 낸다. 이 고유한 인덱스로 데이터를 조회하기 때문에 시간복잡도는 O(1) 를 가진다. 하지만 인덱스 값 충돌이 발생하므로 시간복잡도가 O(N) 까지도 나온다.

 

 

 

구현