오늘은 지난번에 공부했던 Array에 이어서 해시맵에 대한 공부를 정리하려고 합니다.
목차
1. 해시맵(Hash Map) 이란?
- 키(key), 값(Value) 대응시켜 저장하는 데이터 구조입니다. ( 키를 통해 해당 데이터에 빠르게 접근이 가능합니다.)
- 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 입니다.
2. 해시 맵 구조
- Key는 해시 맵 접근을 위한 입력 값입니다.
- 해시 함수는 키를 해시 값으로 매핑하는 연산입니다.
- 해시 값은 해시맵의 인덱스입니다.
- 해시 맵은 키 값을 연관시켜 저장하는 데이터 구조 입니다.
각 하나의 테이블에 키값이 들어가야 하지만 위에 같이 테이블 공간에 서로 다른 값을 저장하려는 경우 충돌이 발생합니다.
3.해시 충돌 해결 방법
- 개발 주소법으로 충돌 시, 테이블에 비어 있는 공간의 hash를 찾아 데이터를 저장 합니다.
- 비어 있는 공간 탐색 방법에 따라서 분류 (선형 탐사법, 제곱 탐사법, 이중 해싱)
1. 선형 탐사법
- 빈 공간을 순차적으로 탐사하는 방법입니다.
- 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사합니다.
- 일차 군집화 문제 발생 -> 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생 합니다.
2. 제곱 탐사법
- 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법입니다.
- 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사합니다.
- 일차 군집화 문제 일부 보완합니다.
- 이차 군집화 문제 발생 가능성 있습니다.
4. 시간 복잡도
- 평균 O(1)의 시간 복잡도를 갖습니다.
- 해시 충돌이 일어날 경우 시간 복잡도는 O(N)에 수렴합니다.
지난번에 공부한 Array는 링크 참고해주세요.