개념

맵(map)

• key-value 쌍(pair)들을 저장하는 ADT
• 같은 key를 가지는 쌍(pair)은 최대 1개만 존재 (반면 value는 중복 가능)
• associative array 또는 dictionary 라고도 함

언제 쓸까?

• 전화번호에 대응되는 이름
• 투표 대상별 투표 횟수 카운팅

구현

해시 테이블(hash table)

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

해시 함수(Hash function)
-임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환
-해시 테이블에서 임의의 데이터를 정수로 변환
-key를 해시 함수에 넣어서 출력된 값을 hash 라고 부름

배열의 크기(=capacity)
배열의 각각의 공간(=bucket =slot)

해시 충돌(hash collision)

• key가 다르고, hash가 같은 경우
  • 크기가 큰 데이터 > 해시 함수 > 크기가 작은 데이터
  • 따라서 충돌을 피할 수 없음
  • 해시 함수의 출력값을 최대한 균등하게 나오도록 해주는 게 중요함
• key와 hash 모두 다르고, hash % map_capa 결과가 같은 경우

해시 충돌 해결 방법

1. open addressing (linear probing)

2. separate chaining

• bucket 하나하나를 linked list로 관리함

해시 테이블 리사이징(resizing)

• 데이터가 많이 차게 되면 크기를 늘려줘야 한다