알고리즘 - 13 해시 테이블

해시

- 원재료를 다른 재료와 함께 다지고 섞어서 새로운 형태의 요리로 만드는 것

 

자료구조의 해시

- 데이터를 입력 받으면 완전히 다른 모습의 데이터

 

 

 

해시 테이블 개개요

- 아래의 배열에서 623453을 찾기 위해서 어떻게 해야할까?

- 지금 상태에서는 순차 탐색 밖에 대안이 없음

-> 원하는 값이 k번째에 있는 경우 k번 비교 연산을 수행해야함

 

 

해시 테이블 개요

1. 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료 구조

- 저장된 자료와 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자신의 자리를 찾음

2. 직접 주소 테이블 direct address tables

- 원본 데이터의 키를 직접 주소 테이블의 주소에 바로 기재하는 방법

  -> 크기가 |U|인 테이블 T를 생성하고 키 k를 slot k에 저장하는 방식

- 키가 중복되어서는 안됨

 

3. 평균 상수 시간에 삽입, 삭제, 검색

- 매우 빠른 응답을 요구하는 응용에 유용함

 -> ex : 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록시스템

- 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않음

 

 

 

해시 테이블의 예시

- 입력 : 25, 13, 16, 15, 7

- 해시 함수 h(x) = x mod 13

-> 탐색 성능은 향상되었으나 저장 공간은 희생 됨

0	13
1
2	15
3	16
4
5
6
7	7
8
9
10
11
12	25

 

 

해시 함수

- 키 값을 입력으로 받아 해시 테이블 상 주소를 리턴

- 해시 함수가 가져야 하는 성질 : 입력 원소가 해시 테이블 전체에 고루 저장되어야 함. 계산이 간단해야함

 

해시 함수 종류

1. 제산법 division method

2. 곱하기 방법 multiplication method

3. 제곱법 mid square

4. 숫자 분석법 digit analysis

5. 이동법 shifting

6. 기수변환법 radix conversion

7. 접지법 floding

8. 난수 생성법 pseudo random

9. 대수적 코딩 algebraic coding

10. 자릿수 재배열