Map
map 을 사용하는 이유
array - 인덱스로 빠르게 읽기는 좋지만 유연하지 못하다.
list - 유연하지만 인덱스로 빠르게 읽지 못한다.
array와 list 두 가지의 장점을 합쳐 유연하면서도 빠르게 읽어내는 자료구조가 map입니다.
map에 어떠한 데이터(element)를 추가한다고 예를 들어보겠습니다.
추가하려는 데이터(element)가 유한한 array의 몇 번 index에 넣을지 정해야 합니다.
index가 정해지면 그곳에 연결된 리스트에 추가하면 됩니다.
위의 과정에서 의문이 생길것입니다.
- 저장하고자 하는 데이터의 index를 어떻게 지정할까
- 내가 저장하고자하는 데이터의 적절한 index 번호가 무엇인지
- 데이터를 적절하게 분산할려면 어떻게 index를 지정해야 할까?
위의 의문점을 해결하는 방법이 바로 key값 지정 방법입니다.
1.숫자가 아니라 key 라는 값을준다
2.key값만 준다면 array 어딘가에 매핑 되고 그곳에 연결된 리스트를 사용한다
hashing - key를 범위에 맞게 적절히 겹치지 않는 index로 변경한다.
hash function - hashing의 기능 수행 key 값을 hash 값으로 변환
hash- hash function을 통해 나온 값으로 index로 사용됨
데이터 삽입 및 삭제 시, 기존 데이터를 밀어내거나 채우지 않고 데이터와 연관된 고유한 숫자를 생성해 인덱스로 사용하는 방법
검색 속도가 매우 빠르다
bucket - hash 값을 사용하는 array
hash collision - key는 다르지만 같은 hash 값을 가지는 경우
위의 복잡한 과정을 단순하게 생각하면
위의 사진과 같이 표현할 수 있으면 map, mapping table이라고도 하지만 dictionary라고 부리기도 합니다.
시간복잡도는 O(1) 입니다. key만 주면 value를 얻기 때문에
