자바 자료구조#07. Map

Map이 필요한 이유

• Array : 인덱스로 빠르게 읽기는 좋은데 유연하지 못함
• List : 유연하기는 한데 인덱스로 빠르게 읽지 못함
• 유연하면서도 빠르게 읽어내는 것은 없을까?
  => 인덱스와 관계없이 Key만 알고 있으면 자료구조에 Mapping 된 데이터를 사용할 수 있는 자료구조

Hashing

• hash function : Key 를 범위(배열 크기)에 맞게 적절히 겹치지 않는 index로 변경한다.
• bucket : hash index가 저장된 array
• hash collision : key는 다르지만 hash값이 같은 경우 발생. 충돌이 일어나지 않도록 List로 구성

Map

• Mapping table : Key - Value 가 매핑된 테이블
  "Key는 곧 Value다." => Dictionary

Map의 시간복잡도

• O(1)