자료구조 정리자료 - 해시 테이블 (Hash table)

소개글

"자료구조 정리자료 - 해시 테이블 (Hash table)"에 대한 내용입니다.

목차

1. 연관배열구조

2. 연산

3. 해시 테이블의 구조

4. 해시 테이블 구성

5. 해시 테이블을 이용한 기본 연산 설명
1) 삽입연산
2) 삭제연산
3) 검색연산

6. 해시 충돌

7. 해시 충돌 해결방법
1) 개방형 주소법 (open addressing)
2) 체이닝 (chaining)

본문내용

해시 테이블은 연관배열 구조(associative array)를 이용한 것으로, 키(key)에 결과 값(value)을 연관시켜 데이터를 저장하는 자료구조이다. 빠른 데이터 검색을 특징으로 한다. 키값에 해시함수를 적용하여 고유한 인덱스(index)를 생성하고 이 인덱스를 이용해 값을 저장소에 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라 부른다.
연관배열 구조
연관배열 구조란 키(key) 1개와 값(value) 1개를 1:1로 연관지어 저장하는 자료 구조이다. 따라서 키(key)를 이용하여 값(value)을 찾아내는 자료 구조이다.
연산
연관배열 구조로 수행할 수 있는 연산은 다음과 같은 것이 있다.
 키와 값이 주어졌을 때, 연관배열에 키와 값의 쌍을 저장하는 연산 (삽입)
 키가 주어졌을 때, 연관되는 값을 얻는 연산 (검색)
 키와 값이 주어졌을 때, 키에 연관되어 있던 원래의 값을 새로운 값으로 교체하는 연산 (교체)
 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 연산 (삭제)
해시 테이블을 이용하여 이러한 연산을 어떻게 수행하는지 살펴볼 것이다.
해시 테이블의 구조 (Hash Table Data Structure)
아래의 해시 테이블을 예로 들어보자. (key, value) 쌍이 (“John Smith”, “521-8976”)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 먼저 hash_function(“John Smith”) % 16 연산을 통해 index를 계산한다. 그리고 array[index] 에 “521-1234”를 저장한다. 이렇게 저장하면, key 값을 이용해 데이터를 조회할 때 해시 함수를 1번 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회가 가능한다. 따라서 해시테이블을 이용한 저장/삭제/조회에 대한 평균 시간복잡도는 O(1)이다. 여기서 O(1)의 의미는 어떤 다른 조건에도 상관없이 (예를 들면 키의 길이에 상관없이) 항상 constant한 시간 내에 저장/삭제/조회가 가능한다는 의미다.

참고 자료

없음