해시 테이블에 대해서 알아보자

해시 테이블에 대해서 알아보자

해시 테이블 (Hash tables / Hash map)이란?

📍 해시 테이블의 개념

해시테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조다.

📍 해시 테이블의 특징

• 해시테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.
  덕분에 데이터 양에 관계없이 빠른 성능을 기대할 수 있다는 장점이 있다.

• 해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.

• 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것이 해싱(Hashing)이라 하며, 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다.

성능이 좋은 해시 함수들의 특징

• 해시함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

📍 해시 함수에서 알아야 할것

• 로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수k로 나눈 것이다.
• 로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야할 지를 결정한다.

📍 충돌이 발생했을 때 피하는 방법

1.개별 체이닝

• 해시테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 연결리스트로 연결하는 방식이다.
• 이 방식은 잘 구현한다면 대부분의 탐색은 O(1)이지만, 최악의 경우, 즉 모든 해시 출동이 발생했다고 가정할 경우에는 O(n)이 된다.

2.오픈 어드레싱

• 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식, 충돌이 일어나면, 테이블 공간 내 탐사를 통해 빈 공간을 찾아 해결한다.
• 이 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
• 일정 이상 채워지면, 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 과정이 일어난다.