반응형
해시테이블: 해시테이블 또는 해시맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조다.
해시테이블의 핵심은 해시함수다.
해시함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.
해시테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 표현한다.
해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용. 즉, 최적 검색이 필요한 분야에 사용한다.
# 좋은 해시함수의 특징
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시테이블 사용 효율이 높음
충돌 처리에는 두가지 방법이 존재한다. 개별체이닝 방식과 오픈 어드레싱 방식
개별체이닝 방식: 충돌 발생 시 연결리스트로 연결.
오픈 어드레싱 방식: 충돌 발생시 탐사를 통해 빈공간을 찾아 해결. 따라서 오픈어드레싱 방식은 모든 원소가 자신의 해시값과 일치하는 주소에 저장되지는 않는다.
차이점: 개별체이닝 방식은 사실상 무한정 저장이 가능하지만 오픈 어드레싱은 전체 슬롯의 개수 이상은 저장할 수 없다.
댓글