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

✅ 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 사용효율이 높을 것