HASH

삼성전자 수시 역량테스트 B형을 준비하기 위해서 필요한 reference code를 직접 구현하면서 정리를 해보는 중

어짜피 queue나 stack은 딱히 구현할 연습은 없어보임....원래 stl을 안썻으니....

하지만 map이나 sort는 해본적이 없고, 우선순위 queue같은 것도 미리 구현을 해보면 좋을 것 같다는 생각이 들었다.

그 중에 이 글은 map을 대체로 사용할 수 있는 hash를 구현해 보았다.

여기서 가장 중요하게 기억해야 할 것은 5381이라는 골든 넘버!

hash를 구현하다 보면 다른 key값이지만, 이미 할당된 index를 참조하는 경우가 있다.

이런 index 충돌이 일어나게 되는 것이 최소화시키는 것이 5381이라고 한다.

자세한 것은 아래의 코드를 보면서 참조하면 될 것 같다.

물론 이 코드는 SWEA의 reference code를 보고 공부하여, class 형식으로 만들어 둔것이고, 말그대로 짜면서 내 입맛에 맞게 구현한 것이라

부족한 부분도 있지만, 공부를 위한 참고용이라면 충분할 것이라고 생각된다.

#include <iostream>
#define MAXSIZE 1234
#define KEY_SIZE 255
#define VALUE_SIZE 1234
 
using namespace std;
 
typedef struct {
    char key[KEY_SIZE];
    int key_len;
    char value[VALUE_SIZE];
    int value_len;
    bool init;
 
}node;
 
class HASH {
private:
    node map[MAXSIZE];
    int map_size;
public:
    HASH() {
        map_size = 0;
    }
 
    char* operator[](const char *key) {
        return Getvalue(key);
    }
 
    int Getidx(const char *key) {
        int hash = 5381;
        int c;
        while (c = *key++) {
            hash = ((hash << 5) + hash + c) % MAXSIZE;
        }
        int idx = hash % MAXSIZE;
        return idx;
    }
    
    void insert(const char *key, const char *value) {
        int key_len = 0;
        int idx = Getidx(key);
        char c;
        
        if (map[idx].key_len != 0) {
            if (!compare(map[idx].key, key)) {
                cout << "Can not Insert...\n";
                return;
            }
        }
 
        while (c = *key++) {
            map[idx].key[map[idx].key_len++] = c;
        }
        
        while (c = *value++) {
            map[idx].value[map[idx].value_len++] = c;
        }
 
        map[idx].init = true;
        map_size++;
    }
 
    char* Getvalue(const char *key) {
        int idx = Getidx(key);
        if (!compare(map[idx].key, key)) return NULL;
        else return map[idx].value;
    }
 
    int size() {
        return map_size;
    }
 
    bool compare(const char *a, const char *b) {
        char a_;
        char b_;
        while (a_ = *a++, b_ = *b++) {
            if (a_ != b_) return false;
        }
        return true;
    }
};
 
HASH map;
 
int main(void) {
 
    cout << "exit : press key 1 \n";
    cout << "insert : press key 2 \n";
    cout << "find : press key 3 \n";
 
    while (1) {
        int mode;
        cin >> mode;
        if (mode == 1) {
            char key[KEY_SIZE];
            char value[VALUE_SIZE];
            cin >> key >> value;
            map.insert(key, value);
        }
        else if (mode == 2) {
            char key[KEY_SIZE];
            cin >> key;
            const char *result = map[key];
            if (result == NULL) {
                cout << "Can not found...\n";
            }
            else cout << result << "\n";
        }
        else break;
    }
    return 0;
}