Hash c++ 개념 정리

Hash

 

Hash는 기본적으로 임의의 길이의 문자열을 받아 고유한 key값을 생성한다.

그리고 그 key값에 value를 저장한다.

이렇게 저장을 할 때 같은 key값이 나올 수도 있다. 

그래서 그러한 경우에는 Chaning 방법을 써서 해결하면 된다.

Chaning이란 연결리스트를 통해 바로 뒤로 이어서 저장을 한다.

 

해싱함수

#define MAX_TABLE 10000 // 내가 필요한 만큼의 테이블 크기로 잡아주면 된다.

int hashing(string input){
		// 정수로 바꿔 주는 함수이다.

        int div = 401; // 이렇게 정수로 바꿀때 특정한 소수들을 이용하면 최대한 key값이 겹치지 않게 만들 수 있다.

        int i = 0;
        int len = input.length();

        while(i != len){
                div = ((div << 5) + (int)input[i]) % MAX_TABLE;
                i++;
        }

        return div % MAX_TABLE;

}

 

 

삽입

struct Node{
        string num;
        Node *next;
};

Node head[MAX_TABLE];
Node node[MAX_TABLE];
int node_cnt;

void insert_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        Node *target = &node[node_cnt++];
        target->num = input;

        if(temp->next == 0){
                temp->next = target;
        }
        else{
                while(temp->next != 0){
                        temp = temp->next;
                }
                temp->next = target;
        }

        return;

}

 

찾기

int search_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        while(temp->next != 0){

                if(temp->next->num == input){
                        return 2;
                }
                temp = temp->next;

        }

        return 0;

}