[Algorithm & DS] Hash/Hash Table/Hash Map

leehyuna·2022년 6월 13일
0

Algorithm & DS

목록 보기
1/6

✅ Hash Table / Hash Map

  • Hash Table 또는 Hash Map은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.

  • Hash Tabel 의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1) 이라는 것이다.

  • 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다.
    (Key를 통해 데이터를 바로 받아올 수 있어 속도가 획기적으로 빨라진다.)

  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후 사용한다.
    (공간과 탐색 시간을 맞바꾸는 기법)

  • Python의 Dictionary 타입이 hash table의 대표적 예시이다.


✅ Hash

  • Hash 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.
  • Hash Table을 인덱싱하기 위해 Hash 함수를 사용하는 것을 Hashing 이라 한다.
  • Hashing은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나이고, 따라서 최적의 검색이 필요한 분야에 사용된다.
  • 성능 좋은 Hash 함수들의 특징
    1. hash 함수 값 충돌의 최소화
    2. 쉽고 빠른 연산
    3. Hash Table 전체에 Hash 값이 균일하게 분포
    4. 사용할 키의 모든 정보를 이용하여 Hashing
    5. Hash Table 사용효율이 높을 것

profile

0개의 댓글