HashTable

해쉬테이블은 데이터를 키와 값으로 저장하는 자료구조이다. 키를 인풋으로 해쉬 함수를 통해 값을 낸 뒤 모듈러 연산으로 다시 값(인덱스)을 내 배열의 특정 인덱스에 링크드리스트 자료구조 형태로 저장한다. 서로 값이 다른 키이지만 모듈러 연산 결과 값이 같을 경우 같은 인덱스에 데이터가 저장되게 되어 충돌이 발생하는데 이 때 해당 인덱스에 링크드리스트 형태로 값을 저장한다. 링크드리스트의 각 노드는 키를 참조하고 있으므로 충돌이 발생한 키값에 대한 값을 찾는 경우 노드가 참조하고 있는 값을 통해 원하는 값에 접근할 수 있다.

 

데이터를 삽입, 삭제, 탐색 하는 시간복잡도의 경우 평균적으로 O(1) 시간 복잡도를 갖는다. 최악의 경우 O(n)의 시간 복잡도를 갖는다.현대의 해쉬테이블은 강력한 해쉬 함수를 제공하여 모듈러 연산에 의한 인덱스 값이 서로 충돌하지 않게 설계가 되어 있다. 배열에 저장되어 있는 데이터가 전체 배열의 저장공간의 특정 퍼센트에 다다르게 되면 배열이 resize되는 현상이 발생한다. 즉 데이터의 크기에 기반해 배열의 크기를 조정하여 인덱스의 중복이 발생하지 않게 충돌을 방지하는 방법과 인덱스 충돌 시 링크드리스트를 통해 데이터를 저장하는 방법을 통해 해쉬테이블의 자료구조를 구현한다.