연관배열 구조로 되어있으며 해싱을 사용하여 키(key)에 결과 값(value)을 저장하는 자료구조

연관배열 구조 (associative array)

키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

연관배열 구조는 다음의 명령을 지원한다.

• 키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장하는 명령
• 키(key)가 주어졌을 때, 연관되는 값(value)을 얻는 명령
• 키(key)와 새로운 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령
• 키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하는 명령

위의 명령은 해시테이블에서도 동일하게 적용이 된다.

Hashing

해싱이란 임의의 길이의 값을 **해시함수(Hash Function)**를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.

Direct Address Table

먼저 가장 간단한 형태의 해시테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 이는 키 값이 100이라고 했을 때 배열의 인덱스 100에 원하는 데이터를 저장하는 것이다. 이러한 자료구조는 탐색,삽입,삭제 연산을 모두 O(1) 에 할 수 있지만 다음과 같은 한계점이 있다.

• 최대 키 값에 대해 알고 있어야 한다.
• 최대 키 값이 작을 때 실용적으로 사용할 수 있다.
• 키 값들이 골고루 분포되어있지 않다면 메모리 낭비가 심할 수밖에 없다.

Hash Table

해시 테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭(Bucket, Slot)되어 저장소에 저장이 된다.

인덱스로 저장되는 key값은 불규칙하기 때문에 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다.