HashTable

데이터를 해시 함수를 이용하여 효율적으로 테이블에 저장, 검색하는 자료구조

• 연관 배열 구조 : key-value가 1:1로 연관되어있는 자료구조
• 버킷(인덱스)과 엔트리(데이터) 형태로 구성된다.
• 해시 함수를 통해 해싱된 데이터를 해시 테이블의 인덱스로 사용하여 저장한다.
• 삽입, 삭제, 검색이 용이하다.(key만으로 데이터 검색)
• 해시 충돌이 발생할 수 있다.(서로 다른 키가 값은 해시 값을 갖게 됨)
• 공간 효율성이 떨어진다.(저장 공간을 미리 확보)
• 해시 함수에 대한 의존도가 높다.(해시 함수가 복잡하다면 연산 속도 증가)

• key :고유한 값, 해시 함수의 input
• hash function : 키를 고정된 길이의 데이터로 변경해줌
  → 키는 해시 함수를 통해 해시로 변경되고 데이터(value)와 매칭되어 저장된다.
• value : 저장소(버킷)에 최종적으로 저장되는 데이터

시간 복잡도
삽입/삭제/탐색 : O(1)