Hash Table 자료구조 (C++)

" class Cell "

- key, value 값을 저장하는 단위로 쓰이는 객체이다.

 

1. 변수

- int key  :  key 값을 저장한다.

- int value  :  value 값을 저장한다.

- int flag  :  value값의 유뮤와 별개로 값이 있었는지 여부를 나타내는 값이 필요하다. 이를 저장한다.

  -> ISITEM(0), NOITEM(1), AVAILABLE(2) 로 저장한다.

 

2. 함수

- Cell()  :  생성자 함수로, 초기화 작업을 한다.

 

3. class Cell ADT

class cell {
public:
    int key;
    int value;
    int flag;
    cell() {
        this->key = -1;
        this->value = -1;
        this->flag = NOITEM;
    }
};

 

 

" class HashTable "

- Linear HashTable과 Double HashTable 방식으로 나뉘게 된다.

- Linear HashTable의 경우 hashfunction이 한개가 필요하며, insert, find에서 index를 한칸씩 다음위치로 이동시키며 확인한다.

- Double HashTable의 경우 hashfunction이 두개가 필요하며, insert, find에서 index를 hashfunction2의 상수배만큼 이동시키며 확인한다.

 

1. 변수

- Cell* CellArray  :  앞서 구현한 Cell를 담는  배열로 사용된다.

- int hash_size  : HashTable의 전체 크기를 저장한다. 

- int cur_size  :  현재 저장된 개수를 저장한다.

 

2. 함수

- int hashfunction(int key)  :  key값을 [0 , hash_size-1] 범위내 숫자로 수정하여 반환해준다.

- void insert(int key, int value)  :  hashfunction(key)값을 통해 index 시작점을 구한 후, 한칸씩 CellArray[idx]의 flag 값과 비교하며 ISITEM이 아닌경우(비어있는 경우) 각 key, value, flag 값을 수정한다.

- void find(int key)  :  hashfunction(key)값을 통해 index 시작점을 구한 후, 한칸씩 CellArray[idx]의 key 값과 비교하며 값이 같은경우 종료한다. 만약 CellArray[idx]의 flg값이 NOITEM인 경우 없는경우이므로 종료한다.

 

3. class HashTable ADT

class HashTable {
private:
    cell* cellArray;
    int hash_size;
    int cur_size;
public:
    HashTable(int size) { }
    int hashfunction(int key) { }
    void insert(int key, int value) { }
    void find(int key) { }
 };

 

4. 예시코드

- 참고 코드 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/8.%20Hash%20Table/Code_cpp/W12_P1_HashTable.cpp

- 참고 문제 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/8.%20Hash%20Table/Exercize_pdf/prob-W12_P1.pdf

//
//  W12_4_HashTable.cpp
//  INHA CLASS
//
//  Created by Kang Minsang on 2020/12/16.
//  Copyright © 2020 Kang Minsang. All rights reserved.
//

#include <iostream>
using namespace std;
#define ISITEM 0
#define NOITEM 1
#define AVAILABLE 2

class cell {
public:
    int key;
    int value;
    int flag;
    cell() {
        this->key = -1;
        this->value = -1;
        this->flag = NOITEM;
    }
};

class HashTable {
private:
    cell* cellArray;
    int hash_size;
    int cur_size;
public:
    HashTable(int size) {
        this->hash_size = size;
        this->cellArray = new cell[hash_size];
        this->cur_size = 0;
    }
    
    int hashfunction(int key) {
        return key%hash_size;
    }
    
    void insert(int key, int value) {
        int initial_idx = hashfunction(key);
        int cur_idx = hashfunction(key);
        int proving = 1;
        bool initial = true;
        while(cellArray[cur_idx].flag == ISITEM) {
            if(cur_idx == initial_idx && !initial) {
                return;
            }
            else {
                proving++;
                initial = false;
                cur_idx = (cur_idx+1)%hash_size;
            }
        }
        cellArray[cur_idx].key = key;
        cellArray[cur_idx].value = value;
        cellArray[cur_idx].flag = ISITEM;
    }
    
    void find(int key) {
        int initial_idx = hashfunction(key);
        int cur_idx = hashfunction(key);
        int proving = 1;
        bool initial = true;
        while(cellArray[cur_idx].flag != NOITEM) {
            if(cellArray[cur_idx].key == key) {
                cout<<"True "<<proving<<"\n";
                return;
            }
            else if(cur_idx == initial_idx && !initial) {
                cout<<"False "<<proving<<"\n";
                return;
            }
            else {
                proving++;
                initial = false;
                cur_idx = (cur_idx+1)%hash_size;
            }
        }
        cout<<"False "<<proving<<"\n";
        return;
    }
    
};

int main()
{
    int T;
    cin>>T;
    while(T--) {
        int P,Q;
        cin>>P>>Q;
        HashTable table = HashTable(P);
        int key;
        while(Q--) {
            cin>>key;
            table.insert(key, key);
        }
        int R;
        cin>>R;
        while(R--) {
            cin>>key;
            table.find(key);
        }
    }
}

 

5. 기타

- Linear HashTable의 insert, find의 다음번 index 구하는 코드

cur_idx = (cur_idx+1)%hash_size;

- Double HashTable의 insert, find의 다음번 index 구하는 코드

cur_idx = (hashrunction1(key) + (proving-1)*(hashfunction2(key)))%hash_size;

- erase 함수  :  find함수와 동일구조에 key값이 같을경우 반환 대신 초기화를 진행해준다

    void erase(int key) {
        int probing = 1;
        int initial_idx = hashfunction(key)%arrSize;
        int curIdx = hashfunction(key)%arrSize;
        bool firstOpr = true;

        if(isEmpty()) {
            cout<<"Empty\n";
        }
        else {
            //반복조건 : 값이 있거나 값이 있었던 경우 : 삭제가 가능한 경우, NOITEM의 경우 이동이 필요없기 때문
            while(hashArr[curIdx].flag != NOITEM) {
                //삭제대상을 찾은경우 : 삭제한다
                if(hashArr[curIdx].key == key) {
                    hashArr[curIdx].flag = AVAILABLE;
                    hashArr[curIdx].key = -1;
                    hashArr[curIdx].value = -1;
                    curSize--;
                    break;
                }
                //한바퀴 되돌아온경우 : 종료한다
                else if(curIdx == initial_idx && !firstOpr) {
                    cout<<"loop\n";
                    break;
                }
                //다음칸으로 위치이동한다
                else {
                    probing++;
                    firstOpr = false;
                    curIdx = (hashfunction(key)+probing-1)%arrSize;
                }
            }
        }
    }