해시 테이블 (Hash Table)
▷ 기본개념
1. 데이터를 담을 테이블을 미리 크게 확보해 놓는다.
2. 입력받은 데이터를 해시하여 테이블 내의 주소를 계산한다.
3. 나온 주소에 데이터를 담는다.
※
- 해시 테이블은 궁극의 탐색 알고리즘이다.
- 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.
▷ 특징
해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.
▷ 용어정리
1. 충돌 (Collision)
- 서로 다른 입력 값에 대해 동일한 해시 값.
- 해시 테이블 내의 동일한 주소를 반환 하는것.
※
- 알고리즘을 정교하게 설계한다고 해도 모든 입력값에 대해 고유한 값을 만들지 못한다.
=> 해시 함수의 충돌은 피할 수 없다는 것이다.
2. 클러스터(Cluster)
- 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제.
▷ 해쉬 테이블의 검색 성능.
- 해쉬 테이블의 검색성능은 해쉬 함수의 성능과 해쉬 테이블의 크기에 좌우된다.
- 충돌이 많이 발생하면 성능은 O(n)에 가까워지므로 충돌을 최대한 억제시키는 것이 해쉬의 핵심 포인트다.
▷ 해시(Hash)
- 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다.
- 해시는 검색 방법이라기보다는 빠른 검색을 위해 자료를 관리하는 기법이라고 보면 된다.
실 생활에서도 해시 기법은 흔히 사용된다.
수첩에 주소록을 작성할 때 '가나다'순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로
주소를 적는 방법이 바로 해싱이다.
1. 해시 테이블(Hash Table) : 자료가 저장되는 전체 저장소.
2. 버킷(Bucket) : 주소록의 예에서 보면 ㄱ, ㄴ, ㄷ, ㄹ의 각 페이지가 버킷이다.
3. 슬롯(Slot) : 페이지를 버킷(Bucket)이라고 한다면 페이지에 주소를 기록하는 칸을 슬롯이라고 보면 된다.
4. 해시 함수 : 새로운 자료가 입력될 때 어떤 버킷에 넣을지를 결정하는 연산.
Code
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; } |
결과
'자료구조' 카테고리의 다른 글
| 덱(Deque) (0) | 2017.05.31 |
|---|---|
| 단방향 연결리스트 반대로 뒤집기. (0) | 2017.04.11 |
| 큐(Queue) (0) | 2017.01.07 |
| 스택(Stack) (0) | 2017.01.07 |
| 단방향 연결 리스트(Linked List) (0) | 2017.01.06 |
▷ 큐(Quene)
- 큐(Queue)의 데이터 제거는 대기 줄의 가장 앞에서 수행되며,
데이터의 삽입은 대기 줄의 가장 뒤에서 수행되는 제한된 리스트 구조를 말한다.
- 가장 먼저 삽입된 데이터가(First In) 가장 먼저 제거되는(First Out) 선입선출(FIFO)형태의 자료구조를 가지고 있다.
- 제일 처음에 입력된 데이터를 front라고 하고,
- 가장 나중에 입력된 데이터를 rear라고 한다.
- 데이터의 삽입은 rear에서 이루어지고,
- 삭제는 front에서 이루어진다.
제공되는 큐를 이용하여 만들기.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <iostream> using namespace std; #include <queue> void main() { queue <int> q; // 데이터 입력. for(int i = 0; i < 10; i++) q.push(i); // 데이터 출력. for(int i = 0; i < 10; i++) { printf("%d \n", q.front()); q.pop(); } } |
직접구현.
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 | #include <iostream> using namespace std; #define MAX 9 typedef struct QUEUE{ int Data; struct QUEUE* pNext; }QUEUE; QUEUE* pHead = NULL; QUEUE* pTail = NULL; void push( int Data ); int front(); void pop(); void main() { for(int i = 0; i < MAX; i++) push(i); for(int j = 0; j < MAX; j++) { printf("%d\n", front()); pop(); } } void push( int Data ) { QUEUE* NewNode = new QUEUE; NewNode->Data = Data; NewNode->pNext = NULL; if(pHead == NULL) pHead = NewNode; else pTail->pNext = NewNode; pTail = NewNode; } void pop() { if( pHead == NULL ) { printf("데이터가 존재하지 않습니다. \n"); return; } QUEUE* pRemove = pHead; pHead = pHead->pNext; delete pRemove; } int front() { if( pHead == NULL ) { printf("데이터가 존재하지 않습니다. \n"); return -1; } return pHead->Data; } |
양방향
결과
'자료구조' 카테고리의 다른 글
| 단방향 연결리스트 반대로 뒤집기. (0) | 2017.04.11 |
|---|---|
| 해시 테이블 (Hash Table) (0) | 2017.01.08 |
| 스택(Stack) (0) | 2017.01.07 |
| 단방향 연결 리스트(Linked List) (0) | 2017.01.06 |
| 연결 리스트(Linked List) (0) | 2017.01.06 |
▷ 스택(Stack)
- 스택은 데이터 입/출력이 한쪽으로만 접근할 수 있는 자료구조이다.
- 가장 나중에 들어간 데이터가 제일 먼저나오게 되는 구조이다.
- 선형구조 라고도 한다.
데이터의 입력이 A=> B=> C=> D 순서인 구조에서 자료를 꺼내거나 삭제하려면 다음과 같은 동작이 필요하다.
제공되는 스택을 쓸 경우.
push : 데이터를 추가한다.
top : 최상위 데이터를 반환한다.
pop : 최상위 데이터를 삭제한다.
isEmpty : 현재 스택이 Null인지 아닌지 확인 후 true/false을 반환한다.
직접 구현할 경우 보통 사용법.
push : 데이터를 추가한다.
Peek : 최상위 데이터를 반환한다.
pop : 최상위 데이터를 반환 후 데이터를 삭제 or 데이터를 삭제한다. ( 구현자 입맛대로. )
isEmpty : 현재 스택이 Null인지 아닌지 확인 후 true/false을 반환한다.
라이브러리 사용 스택.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> using namespace std; #include <stack> // 스택을 사용하기 위한 include void main() { stack <int> s; // 스택을 int형으로 사용하겠음. // 1부터 10까지 데이터를 추가. for(int i = 0; i < 10; i++) s.push(i + 1); for(int i = 0; i < 10; i++) { printf("%d\n", s.top()); s.pop(); } } | cs |
직접 구현한 스택.
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 | #include <iostream> using namespace std; #define MAX 9 typedef struct STACK{ int Data; struct STACK* pUnder; }STACK; STACK* pHead = NULL; void push(int Data); int peek(); void pop(); void main() { for(int i = 0; i < MAX; i++) push(i); for(int i = 0; i < MAX; i++) { printf("%d\n", peek()); pop(); } } void push(int Data) { STACK* NewNode = new STACK; NewNode->Data = Data; NewNode->pUnder = NULL; if(pHead != NULL) NewNode->pUnder = pHead; pHead = NewNode; } int peek() { if(pHead == NULL) { printf("데이터가 존재하지 않습니다. \n"); return -1; } return pHead->Data; } void pop() { if(pHead == NULL) { printf("데이터가 존재하지 않습니다. \n"); return; } STACK* pRemove = pHead; pHead = pHead->pUnder; delete pRemove; } |
결과
'자료구조' 카테고리의 다른 글
| 해시 테이블 (Hash Table) (0) | 2017.01.08 |
|---|---|
| 큐(Queue) (0) | 2017.01.07 |
| 단방향 연결 리스트(Linked List) (0) | 2017.01.06 |
| 연결 리스트(Linked List) (0) | 2017.01.06 |
| 퀵 정렬 (Quick sort) (0) | 2017.01.04 |
