해시 테이블 (Hash Table)

해시 테이블 (비선형)

키를 해시 함수에 의해 해시 값으로 변환하여 저장하는 자료 구조

• 삽입 / 삭제 / 탐색이 O(1)
• 서로 다른 키가 같은 인덱스로 해싱되는 경우 충돌 해결이 필요하다.
  • Chaining: 같은 인덱스에 연결 리스트로 여러 개의 값을 저장
  • 개방 주소법: 충돌 시 다른 빈 공간을 찾아 저장
• 중복 없는 데이터 저장 (set 구현 가능), API 요청 결과를 저장하여 반복적인 요청을 줄이는 캐싱과 메모이제이션에 활용 가능