[자료구조] Hash Table (해시 테이블)

자료구조 2014. 12. 17. 15:33

출처 : http://luyin.tistory.com/191

 

Hash Table (해시 테이블)

기본개념 : 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것. 궁극의 탐색 알고리즘이다. 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.

 


Table[3819] = 123817;

데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다.

 


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

(통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다.)


용어정리 : 

1. Collision(충돌) : 서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 주소를 반환하는 것. 어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못합니다. 한마디로 말해서, 해시 함수의 충돌은 피할 수 없습니다.

2. Cluster(클러스터) : 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제

Hash function (해시 함수)

해시 함수의 알고리즘 종류

1. Division Method(나눗셈 법) 

2. Digit Folding(자릿수 접기)


1. Division Method(나눗셈 법) 

나눗셈법은 입력 값을 테이블의 크기로 나누고, 그 '나머지'를 테이블의 주소로 사용한다.

주소 = 입력 값 % 테이블의 크기

특징 : (1) 어떤 값이든 테이블의 크기로 나누면 그 나머지는 절대 테이블의 크기를 넘지 않는다.

   (2) 테이블의 크기를 n이라 할때, 0~n-1 사이의 주소를 반환함을 보장.

   (3) 테이블의 크기 n을 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다.


2. Digit Folding(자릿수 접기)

숫자의 각 자릿수를 더해 해시 값을 만드는 것.

특징 : (1) 문자열을 키로 사용하는 해시 테이블에 특히 잘 어울리는 알고리즘

 문자열의 각 요소를 ASCII  코드 번호(0~127)로 바꾸고 이 값을 각각 더하여 접으면 문자열을 해시 테이블 내의 주소로 변환 가능


ex) 

다음과 같이 7자리의 숫자가 있다고 해봅시다.

8 1 2 9 3 3 5

이 수의 각 자릿수를 더하면 새로운 값, 31이 나옵니다.

31 = 8 + 1 + 2 + 9 + 3 + 3 + 5

이번에는 두 자리씩 더해 봅시다.

148 = 81 + 29 + 33 + 5


Collision Resolution (충돌 해결하기)

해시 테이블의 충돌을 해결하는 방법

1. Open Hashing(개방 해싱) : 주소 밖에 새로운 공간을 할당하여 문제 해결

(1) Chaining(체이닝) : 개방 해싱인 동시에 폐쇠 해싱

2. Closed Hashing(폐쇄 해싱) : 처음에 주어진 해시 테이블의 공간 안에서 문제 해결

(1) Chaining(체이닝) 개방 해싱인 동시에 폐쇠 해싱

(2) Open Addressing(개방 주소법)

(가) Linear Probing(선형 탐사)

(나) Quadratic Probing(제곱 탐사)

(다) Double Hashing(이중 해싱)

(라) Rehashing(재해싱)


1. Chaining(체이닝)

충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법. 개방 해싱 알고리즘이다.

특징 :  (1) 새 데이터를 링크드 리스트의 가장 앞(즉, 헤드의 앞)에 삽입한다.

(그러면 데이터 삽입시, 링크드 리스트 테일을 찾는 '순차 탐색' 을 수행하지 않아도 된다.)

    (2) 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 가짐.

    (3) 해시 테이블 + 이진 탐색 트리의 결합은 최고!

체이닝 해시 테이블 형태


체이닝 기반 해시 테이블의 삽입


2. Chaining(개방 주소법)

개방 주소법은 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 충돌된 데이터를 입력하는 방식

(1) Linear Probing(선형 탐사)

해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.

특징 : Cluster(클러스터) 현상이 매우 잘 발생한다.



(2) Quadratic Probing(제곱 탐사)

선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.

특징 : 서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생


(3) Double Hashing(이중 해싱)

클러스터 방지를 위해, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용



(4) Rehashing(재해싱)

해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것


'자료구조' 카테고리의 다른 글

[자료구조] 이진트리(BinaryTree) - 트리 순회법(전위/중위/후위 순회법)  (0) 2014.12.09
[자료구조] 큐 Queue  (0) 2014.12.03
블로그 이미지

kuku_dass

,

[자료구조] 이진트리(BinaryTree) - 트리 순회법(전위/중위/후위 순회법)

자료구조 2014. 12. 9. 15:55

출처 : http://warmz.tistory.com/619

<순회 방법 코멘트>

Root가 기준!. 무조건 L -> R 순서로 진행된다.

1. Root를 기준으로, Root를 가장 먼저 확인 후, L->R을 하기 때문에, 전위.(Root가 가장 먼저)

2. L -> Root -> R  : Root가 중간에 있으니 중위

3. L -> R -> Root : Root가 마지막이라 후위

 


이진트리(BinaryTree)
 - 일반적인 트리는 한 노드가 N개의 자식을 가질 수 있지만 이진트리의 경우 한 노드가 최대 2개의 자식만 가질 수 있다. 
 - 다양한 분야에 활용되는 자료구조이다. 수식을 트리 형태로 표현하여 계산하게 하는 수식 이진 트리(Expression Binary Tree),
   아주 빠른 데이터 검색을 가능케 하는 이진 탐색 트리(Binary Search Tree) 등등.
 - 이진트리의 종류 : 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree),
                            높이 균형 트리(Height Balanced Tree), 완전 높이 균형 트리(Completely Height Balanced Tree)

 



포화 이진 트리(Full Binary Tree)
 - 모든 레벨의 노드가 꽉 차있는 이진 트리.
 - 단말 노드를 제외한 모든 노드의 차수가 2인 형태를 말한다.

 



완전 이진 트리(Complete Binary Tree)
 - 단말 노드들이 트리의 왼쪽부터 차곡차곡 채워진 형태. 
 - 무조건 왼쪽부터 채워져 있어야 한다.(왼쪽 하위 트리 중 하나라도 비워져있다면 해당 안됨)





트리 순회법
 - 트리 순회 방법에는 3가지가 있다.
 - 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 


전위 순회법(Preorder Traversal)
 1. 루트 노드부터 시작해서 아래로 내려 오면서
 2. 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면
 3. 오른쪽 하위 트리를 방문하는 방식 

 

 



중위 순회법(Inorder Traversal)
 - 트리는 하위 트리의 집합이라고 할 수 있고 하위 트리 역시 또 다른 하위 트리의 집합이라고 할  수 있다.
 - 따라서 아래와 같은 방법으로 탐색할 수 있다.
 1. 왼쪽 하위 트리부터 시작해서
 2. 루트를 거쳐
 3. 오른쪽 하위 트리를 방문하는 방법

 

 - 응용 사례 : 수식 트리(Expression Tree), 중위 표기식
 - (1 * 2) + (7 - 8)을 수식 트리로 표현하면 다음 그림과 같이 나타낼 수 있다.

 



후위 순회법(Postorder Traversal)
 - 전위 순회의 반대
 1. 왼쪽 하위 트리부터 시작해서
 2. 오른쪽 형제 노드를 방문 후
 3. 루트 노드를 방문하는 방법.

 

 - 응용 사례 : 후위 표기식. 후위 순회법을 통해 출력되는 노드를 살펴보면 후위 표기식으로 나타난다.
 - 1 2 * 7 8 - +

 

 

 



C로 구현한 이진트리/트리 순회법
BinaryTree.h

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef BINARY_TREE_H
 
#define BINARY_TREE_H
 
#include <stdio.h>
#include <stdlib.h>
 
typedef char ElementType;
 
typedef struct tagNode
{
    struct tagNode* left;
    struct tagNode* right;
    ElementType data;
} Node;
 
Node* CreateNode(ElementType newData);
void DestroyNode(Node* node);
void DestroyTree(Node* root);
void PreOrderPrintTree(Node* node);
void InOrderPrintTree(Node* node);
void PostOrderPrintTree(Node* node);
 
#endif
 

BinaryTree.c

?
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
82
83
84
#include "BinaryTree.h"
 
/* 노드 생성 */
Node* CreateNode(ElementType newData)
{
    // 노드를 위한 메모리 할당
    Node* newNode = (Node*) malloc(sizeof(Node));
 
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->data = newData;
 
    return newNode;
}
 
/* 노드 파괴 */
void DestroyNode(Node* node)
{
    free(node);
}
 
/* 트리 파괴(후위 순회 활용) */
void DestroyTree(Node* root)
{
    if(root == NULL)
        return;
 
    // 왼쪽 하위 트리 소멸
    DestroyTree(root->left);
 
    // 오른쪽 하위 트리 소멸
    DestroyTree(root->right);
 
    // 루트 노드 소멸
    DestroyNode(root);
}
 
/* 전위 순회 */
void PreOrderPrintTree(Node* node)
{
    if(node == NULL)
        return;
 
    // 부모 노드 출력
    printf(" %c", node->data);
 
    // 왼쪽 하위 트리 출력
    PreOrderPrintTree(node->left);
 
    // 오른쪽 하위 트리 출력
    PreOrderPrintTree(node->right);
}
 
/* 중위 순회 */
void InOrderPrintTree(Node* node)
{
    if(node == NULL)
        return;
 
    // 왼쪽 하위 트리 출력
    InOrderPrintTree(node->left);
 
    // 부모 노드 출력
    printf(" %c", node->data);
 
    // 오른쪽 하위 트리 출력
    InOrderPrintTree(node->right);
}
 
/* 후위 순회 */
void PostOrderPrintTree(Node* node)
{
    if(node == NULL)
        return;
 
    // 왼쪽 하위 트리 출력
    PostOrderPrintTree(node->left);
 
    // 오른쪽 하위 트리 출력
    PostOrderPrintTree(node->right);
 
    // 부모 노드 출력
    printf(" %c", node->data);
}
 

Test_BinaryTree.c

?
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
#include "BinaryTree.h"
 
void main()
{
    // 노드 생성
    Node* A = CreateNode('A');
    Node* B = CreateNode('B');
    Node* C = CreateNode('C');
    Node* D = CreateNode('D');
    Node* E = CreateNode('E');
    Node* F = CreateNode('F');
    Node* G = CreateNode('G');
 
    // 트리에 노드 추가
    A->left = B;
    B->left = C;
    B->right = D;
 
    A->right = E;
    E->left = F;
    E->right = G;
 
    // 트리 출력
    printf("PreOrder...\n");
    PreOrderPrintTree(A);
    printf("\n\n");
 
    printf("InOrder...\n");
    InOrderPrintTree(A);
    printf("\n\n");
 
    printf("PostOrder...\n");
    PostOrderPrintTree(A);
    printf("\n");
 
    // 소멸
    DestroyTree(A);
}

 



JAVA로 구현한 이진트리/트리 순회법
Node.java

?
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
public class Node {
    private char data;
    private Node left;
    private Node right;
 
    public Node(char data) {
        this.setData(data);
    }
 
    public void setData(char data) {
        this.data = data;
    }
 
    public char getData() {
        return data;
    }
 
    public void setLeft(Node left) {
        this.left = left;
    }
 
    public Node getLeft() {
        return left;
    }
 
    public void setRight(Node right) {
        this.right = right;
    }
 
    public Node getRight() {
        return right;
    }
}
 

BinaryTree.java

?
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
public class BinaryTree {
    // 전위 순회
    public static void preorderPrintTree(Node node) {
        if(node == null)
            return;
         
        // 부모 노드 출력
        System.out.print(" " + node.getData());
         
        // 왼쪽 하위 트리 출력
        preorderPrintTree(node.getLeft());
         
        // 오른쪽 하위 트리 출력
        preorderPrintTree(node.getRight());
    }
     
    // 중위 순회
    public static void inorderPrintTree(Node node) {
        if(node == null)
            return;
         
        // 왼쪽 하위 트리 출력
        inorderPrintTree(node.getLeft());
         
        // 부모 노드 출력
        System.out.print(" " + node.getData());
         
        // 오른쪽 하위 트리 출력
        inorderPrintTree(node.getRight());
    }
     
    // 후위 순회
    public static void postorderPrintTree(Node node) {
        if(node == null)
            return;
         
        // 왼쪽 하위 트리 출력
        postorderPrintTree(node.getLeft());
         
        // 오른쪽 하위 트리 출력
        postorderPrintTree(node.getRight());
         
        // 부모 노드 출력
        System.out.print(" " + node.getData());
    }
}
 

Test_BinaryTree.java

?
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
public class Test_BinaryTree {
    public static void main(String[] args) {
        // 노드 생성
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
         
        // 트리에 노드 추가
        A.setLeft(B);
        B.setLeft(C);
        B.setRight(D);
         
        A.setRight(E);
        E.setLeft(F);
        E.setRight(G);
         
         
        // 출력
        System.out.println("Preorder...");
        BinaryTree.preorderPrintTree(A);
        System.out.println("\n");
 
        System.out.println("Inorder...");
        BinaryTree.inorderPrintTree(A);
        System.out.println("\n");
         
        System.out.println("Postorder...");
        BinaryTree.postorderPrintTree(A);
    }
}
 

결과)
 Preorder...

 A B C D E F G

Inorder...
 C B D A F E G

Postorder...
 C D B F G E A

'자료구조' 카테고리의 다른 글

[자료구조] Hash Table (해시 테이블)  (0) 2014.12.17
[자료구조] 큐 Queue  (0) 2014.12.03
블로그 이미지

kuku_dass

,

[자료구조] 큐 Queue

자료구조 2014. 12. 3. 14:09

Queue : FIFO (First In First Out)

개념 : "앞으로 들어가 뒤로 나온다."

Front(head)                   -       rear(tail)

 enqueue( put, insert)     -      dequeue(get)

 

front or head 에서 데이터의 삽입이 이루어 진다.

rear or tail 에서 데이터가 나오게 된다.

 

보통, 급하게 짜야할 경우, 배열을 이용하게 될텐데, 배열은

구조상

1 

 2

 3

 4

 5

 6

 7

rear ( get )                                                                                                                 front(put)

0번 인덱스부터 쭉 데이터를 넣는 구조이다.

개념상 왼쪽부터 오른쪽으로 데이터가 저장되는 구조이므로, 데이터가 들어가는 오른쪽이 front,

데이터가 빠져나가게되는 쪽이 왼쪽이기 때문에, 왼쪽 부분이 rear 라고 생각하면 된다.

(위 그림에서는 front가 뒷쪽으로 가있는 모양새이고, rear가 앞에 있는 모양으로 보인다.)

헷갈리면 세로로 세워서 생각하자.

 

스택처럼 데이터를 밑에서부터 담아 간다.

 front(head) - put

 7

 6

 5

 4

 3

 2

 1

 rear(tail) - get

 

데이터를 뺄 때는, 들어온 순으로 나가야 하기에, 밑에서 부터 데이터를 뺀다.

 

 배열로 구현 시에는

#define SIZE 100

int data[SIZE];

int rear = -1;(rear는 get될 대상을 가리키고 있어야 한다. 그러므로 기본 값은 -1, enqueue 될 때 마다, +1 )

int front = 0; (앞으로 들어갈 곳을 가리켜야 하니까, 0. enqueue 시에 + 1)

queue_init, queue_destroy, queue_enqueue, queue_dequeue , queue_peak(get될 대상이 되는 데이터를 return)

정도로 구현하면 되며, queue 안에 있을 데이터 자료구조형은 배열이든 리스트이든 입맛에 맞게 구현한다.

'자료구조' 카테고리의 다른 글

[자료구조] Hash Table (해시 테이블)  (0) 2014.12.17
[자료구조] 이진트리(BinaryTree) - 트리 순회법(전위/중위/후위 순회법)  (0) 2014.12.09
블로그 이미지

kuku_dass

,

공지사항

태그목록

글 보관함

달력

«   2024/05   »
일 월 화 수 목 금 토
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

티스토리툴바