[key-value]

• key-value : 순서가 아니라 이미 알고 있는 정보를 이용해서 저장한 정보를 검색할 수 있는 데이터 유형

• key-value 쌍 : 하나의 key와 그 key에 해당하는 value를 합친 쌍
• 하나의 key에는 하나의 value만 있어야 한다.

[Direct Access Table]

• 배열 인덱스 접근 : O(1)
• 인덱스를 key로 생각하고 데이터 저장
• key(인덱스)를 이용해서 저장한 데이터인 value에 접근할 수 있음

• 배열의 크기는 943 칸인데, 사용하는 공간은 5 칸
  • 사용하는 인덱스 : 5
  • 낭비하는 인덱스 : 938
• Direct Access Table은 효율적으로 Key-Value를 가져올 수 있지만 낭비하는 공간이 커진다.

[해시 테이블 개념]

• 해시 테이블 : key를 해시함수에 넣어서 return되는 값을 index로 사용하는 자료구조

• 고정된 크기의 배열을 만든다.(배열 무한대로 커지지 않음)
• 해시 함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다
• 해시 함수 결과 값 인덱스에 key-value 쌍을 저장한다