해시 테이블 (Hash Table)

▷ 기본개념

1. 데이터를 담을 테이블을 미리 크게 확보해 놓는다.

2. 입력받은 데이터를 해시하여 테이블 내의 주소를 계산한다.

3. 나온 주소에 데이터를 담는다.

※ 

- 해시 테이블은 궁극의 탐색 알고리즘이다.

- 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.

▷ 특징

해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.

▷ 용어정리

1. 충돌 (Collision)

- 서로 다른 입력 값에 대해 동일한 해시 값.

- 해시 테이블 내의 동일한 주소를 반환 하는것.

※ 

- 알고리즘을 정교하게 설계한다고 해도 모든 입력값에 대해 고유한 값을 만들지 못한다.

=> 해시 함수의 충돌은 피할 수 없다는 것이다.

2. 클러스터(Cluster)

- 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제.

▷ 해쉬 테이블의 검색 성능.

- 해쉬 테이블의 검색성능은 해쉬 함수의 성능과 해쉬 테이블의 크기에 좌우된다.

- 충돌이 많이 발생하면 성능은 O(n)에 가까워지므로 충돌을 최대한 억제시키는 것이 해쉬의 핵심 포인트다.

▷ 해시(Hash)

- 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다.

- 해시는 검색 방법이라기보다는 빠른 검색을 위해 자료를 관리하는 기법이라고 보면 된다.

실 생활에서도 해시 기법은 흔히 사용된다.

수첩에 주소록을 작성할 때 '가나다'순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로

주소를 적는 방법이 바로 해싱이다.

1. 해시 테이블(Hash Table) : 자료가 저장되는 전체 저장소.

2. 버킷(Bucket) : 주소록의 예에서 보면 ㄱ, ㄴ, ㄷ, ㄹ의 각 페이지가 버킷이다.

3. 슬롯(Slot) : 페이지를 버킷(Bucket)이라고 한다면 페이지에 주소를 기록하는 칸을 슬롯이라고 보면 된다.

4. 해시 함수 : 새로운 자료가 입력될 때 어떤 버킷에 넣을지를 결정하는 연산.

Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include <iostream> using namespace std;     #define KEY         10 #define CHAINING  3   int HashTable[KEY][CHAINING];     int Hash(int Key); void AddKey(int Key); bool FindKey(int Key); void main() {     memset( HashTable, 0, sizeof(HashTable));       // 데이터 입력     int Key = 0;     for(int i = 0; i < 5; i++)     {         printf("[%d]번째 입력: ",i + 1);         scanf("%d", &Key);         AddKey(Key);     }       printf("\n");       // 데이터 탐색.     printf("찾을 데이터를 입력:");     scanf("%d", &Key);     FindKey(Key);       printf("\n");       // 테이블 내에 데이터 출력.     for(int i = 0; i < KEY; i++)     {         for(int j = 0; j < CHAINING; j++)             printf("[%d]번째 : %d",i + 1, HashTable[i][j]);         printf("\n");     } }   // 해싱. int Hash(int Key) {     return Key % 100; }   // 데이터 추가. void AddKey(int Key) {     int Bucket = Hash(Key);     for(int i = 0; i < KEY; i++)     {         if(HashTable[Bucket][i] == 0)         {             HashTable[Bucket][i] = Key;             break;         }     } }   // 데이터 검색. bool FindKey(int Key) {     int Bucket = Hash(Key);     for(int i = 0; i < KEY; i++)     {         if(HashTable[Bucket][i] == Key)         {             printf("데이터를 무사히 불러왔습니다.\n");             printf("찾아온 데이터 : %d \n", HashTable[Bucket][i]);             return true;         }     }       printf("데이터가 존재하지 않습니다. \n");     return false; }

결과