Hash Table

• 한정된 배열 공간에 key를 index로 변환하여 값들을 넣는다.
• key와 value를 받아서 key를 해싱(hashing)하여 나온 index에 값을 저장한다.
  • 즉, 같은 인풋을 주면 같은 아웃풋을 받도록 한다.
• 선형 자료구조이다.
• 삽입은 O(1)이며, 키를 알고 있다면, 삭제-탐색도 O(1)로 수행한다.
  • (해쉬 충돌이 일어나면 시간복잡도가 달라질 수 있다. 아래 내용 참고)

Hash란 무엇인가

입력 받은 값을 특정 범위 내의 숫자로 변경하는 함수이다.

→ 하지만, 해시 함수의 결과가 동인하게 겹친다면 해쉬 충돌 (Hash Collision)이 발생한다.

1. 선형 탐사법
   • 충돌이 발생하면 옆으로 한 칸 이동한다.
2. 제곱 탐사법
   • 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
3. 이중 해싱
   • 충돌 발생 시, 다른 해시 함수를 사용한다.
4. 분리 연결법
   • 충돌 발생시, 연결 리스트로 사용하여 리스트에 값을 추가한다.

언제 사용하는가

• 연결리스트는 찾을 때, O(n)의 시간복잡도가 걸린다.

  (일반 배열의 경우에도 index를 모른다면, 탐색에 O(n)의 시간복잡도가 소요된다.)

  ⇒ 해시 테이블을 사용하면 탐색에 O(1) 시간이 소요된다.

  즉, 빠르게 값을 찾아야 하는 경우에 유용하다,