해시법 (체인법, 오픈 주소법)

• 해시법

해시법이란 data를 저장할 인덱스를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행할 수 있는 자료구조이다. 해시법에는 data를 저장할때 key값과 함께 저장하는데 이 key값과 해시 함수(간단한 연산)를 통해 얻은 해시값을 index로 사용한다.

예를 들면 다음과 같다.

 

 해시 함수 : key % 13

key	35	80	75	63	21	1
해시값 (index)	9	2	10	11	8	1

  이렇게 key값을 해시함수에 넣어 얻은 해시값을 index로 해서 key값과 data값을 저장하면 된다.

  

 위와 같이 해시값을 index로 하여 key값과 data를 저장하는 자료구조를 해시 테이블이라고 하고 그 안에 요소들을 버킷(bucket)이라고 한다. 해시 테이블에서 원하는 data를 찾으려면 원하는 data와 한 쌍인 key값을 해시함수에 넣어 index만 찾으면 바로 찾아지므로 시간복잡도가 O(1)이 된다. 

 이렇게 빠른 탐색속도를 갖고있어서 편한 해시법에도 해결해야할 문제가 있다. 만약 해시 함수가 위와 같이 key % 13일때 key값으로 75, 62가 들어오면 충돌이 일어난다.

 

 75 % 13 = 10

 62 % 13 = 10

 

이렇게 되면 index = 10의 자리는 1개인데 들어가야 할 data는 2개가 된다. 따라서 우리는 체인법과 오픈 주소법으로 이 문제를 해결해야 한다.

 

• 체인법

 체인법은 위와 같이 1개의 index에 여러 key, data가 들어가야 할 일을 생각해서 각 index를 연결리스트로 구현하는 방법이다. 모든 index는 연결리스트의 head의 역할을 해서 연결리스트의 맨 첫 노드를 가리킨다고 생각하면 된다. 이제 위의 예시처럼 key값이 75인 노드를 index에 추가하고 그 다음에 key값이 62인 노드를 추가하면 index = 10은 key값이 75인 노드를 가리키고 key값이 75인 노드는 key값이 62인 노드를 가리키게 된다.

 그러면 탐색을 할 경우에 key값의 해시값에 따라 index = 10을 찾게 되고 연결리스트를 순회하면서 실제 key값을 비교해 원하는 data를 찾으면 된다.

 

 그러면 체인법을 한번 코드로 구현해보자.

 

class ChainHash{

    int size;
    Node[] table;

    ChainHash(int capacity)
    {
        table = new Node[capacity];
        this.size = capacity;
    }

    int hashValue(int key){
        return key % size;
    }

    class Node{
        int key;
        String data;
        Node next;
        Node(int key, String data, Node next)
        {
            this.key = key;
            this.data = data;
            this.next = next;
        }
    }
}

 key를 int형 data를 String형으로하는 Node를 저장하는 해시테이블을 구현하는 ChainHash class이다. Node의 생성자는 연결리스트를 구현했을때와 비슷하고 그 연결리스트를 저장할 해시테이블은 ChainHash생성자를 통해 만든다. 그리고 해시 함수는 hasValue로 구현하였고 key값을 해시테이블의 크기로 나머지연산을 해서 해시값을 구한다. 이제 추가로 필요한 함수들을 하나씩 구현해 보자.

 

 1) add

 add함수는 key값과 value값을 입력하면 자동으로 노드를 만들어서 해시테이블의 알맞은 자리에 넣어주는 함수이다. 어렵지 않으므로 코드를 보고 이해해보자.

int add(int key, String data){
    int value = hashValue(key);
    Node p = table[value];
    while (p != null){
        if (p.key == key)
            return 1;
        p = p.next;
    }
    Node n = new Node(key, data, table[value]);
    table[value] = n;
    return 0;
}

 add는 우선 매개변수로 추가할 노드의 key, data를 받는다. 그리고 key값으로 해시값을 먼저 찾는다. 해시법에서 중요한 점은 중복되는 key값을 갖지 않는 것이므로 해당 해시값을 index로 하는 연결리스트를 while문으로 전부 방문하면서 동일 key값이 존재하면 1을 return해준다.

 만약 중복 key값이 없으면 본격적으로 노드를 추가해준다. 일단 n이라는 새로운 노드를 만드는데 next를 현재 해시값을 index로하는 연결리스트의 head로 지정해서 연결리스트의 맨 앞으로 추가해준다. 그리고 연결리스트의 head역할을 하는 table[value]의 값을 n으로 만들어주면 해시테이블에 노드가 추가된다. 그리고 노드를 정상적으로 추가해줬다는 의미로 0을 return해준다.

 

2) remove

 remove함수는 해시테이블에서 매개변수로 주어지는 key값을 갖는 노드를 삭제하는 함수이다. 노드를 삭제한 후 그 노드의 앞의 노드와 뒤의 노드를 이어주는 것이 포인트이다.

int remove(int key){
    int value = hashValue(key);
    Node p = table[value];
    Node pp = null;
    while (p != null)
    {
        if (p.key == key)
        {
            if (pp == null)
                table[value] = p.next;
            else 
                pp.next = p.next;
            return 0;
        }
        pp = p;
        p = p.next;
    }
    return 1;
}

 해시값 value를 주어진 매개변수 key로 찾고 노드 p와 노드 pp를 만든다. 노드 p는 현재 탐색중인 노드이고 노드 pp는 p의 이전 노드라 보면 된다.

 while문으로 p가 null이 나오기 전까지 연결리스트를 탐색하는데 만약 매개변수로 들어온 key값과 동일한 값이 없으면 탐색 실패로 삭제를 할 수 없기 때문에 while문을 빠져나가 1을 return한다. 하지만 탐색중에 key값과 동일한 key를 갖는 노드를 찾으면 2가지 경우에 따라 처리를 한다.

 

 1. p가 연결리스트의 head노드라 pp가 null인경우

 2. 그 외에 pp가 null이 아닌 경우

 

1번의 경우 연결해줄 앞의 노드가 없으므로 head노드를 p의 다음노드로 바꿔주기만 하면 된다. 그리고 2번의 경우에는 pp의 next를 p가 아닌 p.next로 연결해주면 노드p가 삭제된다.

 

3) search

 마지막으로 key값을 넣으면 해당 key와 쌍을 이루는 data를 return해주는 탐색함수 search이다. key값을 이용해 value를 얻고 table[value]를 돌면서 입력으로 받은 key와 일치하는 key를 갖는 노드를 발견하면 해당 노드의 data를 반환해주면 된다. 탐색에 실패하면 null을 반환해준다.

String search(int key){
    int value = hashValue(key);
    Node p = table[value];
    while (p != null)
    {
        if (p.key == key)
            return p.data;
        p = p.next;
    }
    return null;
}

 

• 오픈 주소법

오픈 주소법은 충돌이 발생했을때 재해시를 통해 다른 버킷을 사용하여 충돌을 해결하는 방법이다. 재해시를 하는 방법에는 선형 탐사, 제곱 탐사 등 여러가지가 있다. (만약 재해시를 통해 찾은 bucket도 비어있지 않으면 계속 재해시를 하면 빈 공간을 찾는다)

 

 - 선형 탐사 : key값을 통해 찾은 bucket에 자리가 없으면 현재 index에 +1을 한 bucket을 확인하는 방법

 - 제곱 탐사 : key값을 통해 찾은 bucket에 자리가 없으면 현재 index의 제곱에 해당하는 index의 bucket을 확인하는 방법

 

 오픈 주소법은 체인법과 비교하면 추가 메모리를 사용하지 않아 공간복잡도를 줄일 수 있지만 충돌이 발생하면 추가적인 검색이 필요하므로 검색속도가 체인법에 비해 느릴 수 있다. 따라서 충돌의 빈도가 낮은 경우에 체인법보다 효율적이다. 

 

 이번엔 오픈 주소법을 코드로 구현해보자. (재해시는 현재 해시값 + 1로 설정)

class OpenHash{

    int size;
    Bucket[] table;

    OpenHash(int capacity)
    {
        table = new Bucket[capacity];
        this.size = capacity;
        for (int i = 0; i < capacity; i++)
            table[i] = new Bucket();
    }

    int hashValue(int key){
        return key % size;
    }

    int rehashValue(int hash){
        return (hash + 1) % size;
    }
    enum Status {OCCUPIED, EMPTY}

    static class Bucket{
        int key;
        String data;
        Status stat;
        Bucket() {
            stat = Status.EMPTY;
        }

        void set(int key, String data, Status stat){
            this.key = key;
            this.data = data;
            this.stat = stat;
        }

        void setStat(Status stat) {
            this.stat = stat;
        }
    }
}

 체인법처럼 table을 구현했지만 다른점은 Node가 아닌 Bucket의 배열이라는 점이다. Bucket은 다음과 같은 특징을 같고 있다.

 

 1. 내부적으로 key, data, stat값을 갖는다

 2. stat는 enum으로 만들어진 Status의 값을 받는다

 3. OpenHash, Bucket생성자에 의해 모든 Bucket의 stat는 EMPTY로 초기화된다.

 4. set과 setStat로 Bucket의 값을 수정할 수 있다

 

 그리고 hashValue라는 함수로 해시값을 얻었던 것처럼 방문한 Bucket이 OCCUPIED상태인 경우 rehashValue로 재해시를 통해 다음 해시값을 얻을 수 있다.

 이제 추가적인 함수들을 살펴보자.

 

1) search

 search는 입력받은 key값으로 얻은 해시값 value를 index로 하는 Bucket을 방문하여 Bucket의 key값이 입력된 key값과 같으면 해당 Bucket의 data를 반환하고 다르면 재해시를 통해 다음 Bucket을 방문하는 것을 반복하여 원하는 data를 찾는 함수이다. 이렇게 원하는 data를 찾을 수 있으면 다행이지만 재해시를 size만큼 했는데도 탐색을 성공하지 못한경우 방문할 수 있는 Bucket을 다 방문했지만 원하는 Bucket을 찾지 못한 경우이므로 탐색에 실패했다 할 수 있다. 이를 코드로 구현하면 다음과 같다.

String search(int key){
    int value = hashValue(key);
    Bucket p = table[value];
    for (int i = 0; i < size; i++)
    {
        if (p.key == key && p.stat == Status.OCCUPIED)
            return p.data;
        p = table[rehashValue(value)];
    }
    return null;
}

2) add

 add는 해시값에 맞는 EMPTY상태의 Bucket을 찾은 후 그 안에 key와 data를 넣는 함수이다. 만약 이미 해당 key값이 들어있으면 1을 return하고 재해시를 반복해도 EMPTY상태의 Bucket을 찾지 못하면(해시 테이블이 가득 찼다면) 2를 return하고 성공적으로 EMPTY상태의 Bucket을 찾았다면 key와 data를 저장하고 0을 return한다. 코드는 다음과 같다.

int add(int key, String data){
    if (search(key) != null)
        return 1;
    int value = hashValue(key);
    Bucket p = table[value];
    for (int i = 0; i < size; i++){
        if (p.stat == Status.EMPTY){
            p.set(key, data, Status.OCCUPIED);
            return 0;
        }
        p = table[rehashValue(value)];
    }
    return 2;
}

 

3) remove

 마지막은 remove함수로 입력받은 key값과 일치하는 Bucket을 찾은후 stat를 EMPTY상태로 바꿔주면 된다. 성공적으로 삭제에 성공하면 0을 반환하고 만약 해당 key값을 갖는 Bucket이 없다면 1을 반환한다.

 굉장히 간단하므로 코드를 보면 이해가 될 것이다.

int remove(int key){
    int value = hashValue(key);
    Bucket p = table[value];
    for(int i = 0; i < size; i++)
    {
        if (p.key == key && p.stat == Status.OCCUPIED)
        {
            p.setStat(Status.EMPTY);
            return 0;
        }
        p = table[rehashValue(value)];
    }
    return 1;
}