Map

key-value pair들을 저장하는 ADT이다. 같은 key를 가지는 pair는 하나만 존재할 수 있다(중복 X). associative array, dictionary라고 부르기도 한다.

map 구현체

• hash table
• tree-based

Hash table (hash map)

배열과 해시 함수를 사용하여 map을 구현한 자료 구조이다. 일반적으로 상수 시간으로 데이터에 접근할 수 있다.

저장(put)
key값을 hash function에 넣음 → 나온 값을 배열의 크기(capacity)로 나눔 → 나머지 값을 배열의 인덱스를 위치로 key,value,hash 값을 저장

조회(get)
key값을 hash function에 넣음 → 나온 값을 배열의 크기(capacity)로 나눔 → 나머지값 인덱스에서 key값이 동일한 데이터 검색

Hash function

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
• (hash table에서) 임의의 데이터를 정수로 변환하는 함수
  • ex) “kim” → hash function → 3075

hash collision

1. key값이 다른데 hash가 같을 경우
   -> hash function에 key를 넣었을 때 우연히 같은 값이 나왔을 경우
   
2. key, hash 둘 모두 다른데 hash % map_capatity 결과가 같을 때

해결 방법

• open addressing(linear probing)
  • hash값의 인덱스가 이미 차 있다면 다음 배열에 값을 저장
  • 삭제 시 밀린 hash값을 돌려 놓던가, 더미 값을 채워 놓아야 함
  • capacity의 75%이상이 채워졌다면 2배의 크기로 증가
• separate chaining
  • bucket하나하나를 LinkedList로 관리
    • 다른key, 동일한 hash일시 다음 노드에 저장