1. 해싱표, 해쉬표, 해시 테이블 (Hash Table)
ㅇ 키(Key)를, 해시함수를 통해 해시주소로 변환하여, 데이터 저장/검색하는, 배열 기반 자료구조
- 키를 입력 받아 고정 크기의 배열 인덱스를 생성하고,
- 그 위치에 해당 데이터를 저장함으로써, 빠른 탐색을 가능하게 함
2. 해시 테이블의 특징
ㅇ `키 - 값` 쌍 저장 구조
- 데이터는 키(Key)와 값(Value) 쌍의 형태로 저장됨
- 키를 이용해 해당 값에 직접 접근 가능
ㅇ 비 선형 자료구조 임
- 데이터가 순차적으로 저장되지 않고,
- 해시 함수를 통해, 특정 버킷(bucket) 또는 슬롯(slot)에, 산발적으로 배치됨
ㅇ 인덱싱 방식의 직접 접근 구조
- 배열처럼 순차적인 인덱스를 사용하는 것이 아니라,
. 해시 함수를 통해 특정한 메모리 주소를 직접 계산하여 접근함
- 따라서, 같은 해시 값이 할당된 경우(충돌 발생 시),
. 체이닝(연결 리스트 사용) 또는 개방 주소법 등을 사용하여 해결함
ㅇ 고정 크기 매핑 구조
- 해시 테이블의 크기는 사전에 정해진 고정 크기를 가짐
- 무한한 키 공간을 유한한 해시 값으로 매핑하므로,
- 제한된 작은 캐시 메모리로도 대규모 데이터를 관리 가능
ㅇ 높은 탐색 효율 : 평균적으로 시간복잡도 O(1) 상수 시간에 검색 및 삽입 가능
- 충돌이 많거나 해시 함수 품질이 낮으면, 성능 저하 가능
- 데이터의 저장,검색은 빠르나, 그외의 용도에는 제약 많음
ㅇ 정렬 비지원
- 저장 시 순서 보장 않되므로, 정렬 필요시 별도 연산 수행 요구됨
- 반면, 이진 검색 트리 등은 자동 정렬 구조를 가짐
3. 해시의 구현
ㅇ 구현 기반
- 기본적으로, 배열을 이용하여 구현
ㅇ 주요 활용
- 사전, 연관배열 등의 추상 자료형(ADT)을 효율적으로 구현하는 데 적합