해시맵(Hash Map) , 테이블 공부 정리

오늘은 지난번에 공부했던 Array에 이어서 해시맵에 대한 공부를 정리하려고 합니다.


목차


1. 해시맵(Hash Map) 이란?

  • 키(key), 값(Value) 대응시켜 저장하는 데이터 구조입니다. ( 키를 통해 해당 데이터에 빠르게 접근이 가능합니다.)
  • 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 입니다.

2. 해시 맵 구조

  • Key는 해시 맵 접근을 위한 입력 값입니다.
  • 해시 함수는 키를 해시 값으로 매핑하는 연산입니다.
  • 해시 값은 해시맵의 인덱스입니다.
  • 해시 맵은 키 값을 연관시켜 저장하는 데이터 구조 입니다.
    해시맵

    각 하나의 테이블에 키값이 들어가야 하지만 위에 같이 테이블 공간에 서로 다른 값을 저장하려는 경우 충돌이 발생합니다.

    3.해시 충돌 해결 방법

    1. 개발 주소법으로 충돌 시, 테이블에 비어 있는 공간의 hash를 찾아 데이터를 저장 합니다.
    2. 비어 있는 공간 탐색 방법에 따라서 분류 (선형 탐사법, 제곱 탐사법, 이중 해싱)

    1. 선형 탐사법

    • 빈 공간을 순차적으로 탐사하는 방법입니다.
    • 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사합니다.
    • 일차 군집화 문제 발생 -> 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생 합니다.

    2. 제곱 탐사법

    • 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법입니다.
      • 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사합니다.
    • 일차 군집화 문제 일부 보완합니다.
    • 이차 군집화 문제 발생 가능성 있습니다.

    4. 시간 복잡도

    • 평균 O(1)의 시간 복잡도를 갖습니다.
    • 해시 충돌이 일어날 경우 시간 복잡도는 O(N)에 수렴합니다.

    지난번에 공부한 Array는 링크 참고해주세요.

    Leave a Comment