1. 해싱표, 해쉬표, 해시 테이블 (Hash Table)
ㅇ 탐색 키 및 해쉬 주소가 배열로 구현된 테이블 (자료구조)
- 해싱에 이용되는, 일정 크기의 자료구조 (기억공간)
- 고정된 크기의 자료구조로써, 사전에 그 크기가 미리 정해짐
2. 해시의 특징
ㅇ 키를 값에 매핑할 수 있는 자료구조임
- `키(Key), 값(Value)` 쌍으로 저장되고, 탐색되어 짐
. 즉, 키와 값이 하나의 쌍을 이루며, 데이터가 저장되고 검색되어짐
ㅇ 비 선형 자료구조 임
- 내부적으로 해시 함수를 사용하여 데이터를 특정 위치(버킷)에 매핑함
- 따라서, 데이터를 순차 저장 않고, 해시 함수에 의해 산발 배치하므로, 비 선형 자료구조임
ㅇ 인덱싱 방식 임
- 배열처럼 순차적인 인덱스를 사용하는 것이 아니라,
. 해시 함수를 통해 특정한 메모리 주소를 직접 계산하여 접근함
- 따라서, 같은 해시 값이 할당된 경우(충돌 발생 시),
. 체이닝(연결 리스트 사용) 또는 개방 주소법을 사용하여 해결함
ㅇ 시간복잡도 : O(1) 상수시간 알고리즘
- 비록, 데이터의 저장,검색은 빠르나, 그외의 용도에는 제약 많음
ㅇ 고정된 크기의 자료구조로써, 사전에 그 크기가 미리 정해짐
- 무한에 가까운 데이터(키)들을 유한한 개수의 해시 값으로 매핑
. 이를통해 작은 크기의 캐시 메모리로도 관리 가능
3. 해시의 구현
ㅇ 주로, 배열을 활용하여 구현됨
ㅇ 통상, 사전과 같은 자료구조를 구현할 때, 좋은 선택이 됨
- 연관배열 추상자료형(ADT)을 구현할 수 있는 자료구조