Hash 사용법

#1. 프로시험에 유용한 - 동적할당 대신 사용할수 있는 배열

#2. 프로시험에 유용한 - Hash 사용법

#3. 프로시험에 유용한 - 트리 사용법 (자연수 ID 를 가지는 트리)

#4. 프로시험에 유용한 - 트리 사용법

#5. 프로시험에 유용한 - Graph 사용법

#6. 프로시험에 유용한 - 더블 링크드 리스트

==============================================

---

지난 번 "동적할당 대신 사용할수 있는 배열" 에 이어지는 것입니다.

역시 한번 살펴보시고 맘에 드시는 분들 참고하시면 됩니다.

hash에서 가장 중요한 Hash key 를 만들어 주는 함수는 시험중에 참고할 수 있는 S/W Problem Solving Reference 에 이미 있습니다.

복사해온 함수의 내용을 보면 복잡하지만 string 을 주면 적당한 key를 만들어 주고 있습니다.

unsigned long myhash(const char *str)
{
    unsigned long hash = 5381;
     int c;
    while (c = *str++)
    {
 
 
        hash = (((hash << 5) + hash) + c) % MAX_TABLE;
 
 
    }
 
 
    return hash % MAX_TABLE;
 
 
}
 

사용할 hash table 은 지난번의 single linked list 를 배열로 만든 것입니다.

당연히 다 아시는 개념이겠지만, single linked list 가 여러개 있다고 생각하시면 됩니다.

    struct NODE {
 
 
        char data[7];
 
 
        NODE * prev;  //싱글 리스트를 위해 추가.
 
 
    } a[20000];    //지난번과 동일하게 데이터 저장을 위한 힙입니다.
 
 
 
 
    NODE *hTable[MAX_TABLE];  //Hash Table 입니다.
 

저장할 데이터를 참고로 적당한 key를 뽑아서 hTable[ key ] 인 single linked list에 저장하는 방식입니다.

    int key;
    char in[7] = "aaaaaa';
 
 
    key = (int)myhash(in);
 
 
    p = myalloc();
    strncpy(p->data, in, 7);
    p->prev = hTable[key];
    hTable[key] = p;
 

single linked list 와 비교해서 바뀐 내용은 저장을 pList 가 아닌 hTable[key] 에 한다는 점과

이전에는 저장되는 데이터가 int 였으나, 지금은 6자리의 문자열이라는 점 입니다.

마지막으로

Hash table 에서 검색하는 경우는

 - 검색 문자열에서 Hash key 생성

 - Hash table [key] 에서 검색

하시면 됩니다.

    char search[7] = "vrvipy";
 
 
    int k = (int)myhash(search);
 
 
    for (NODE * pp = hTable[k]; pp != NULL; pp = pp->prev)
    {
        if (!strncmp(search, pp->data, 6))
            cout << "FOUND : " << pp->data << endl << endl;
    }
 

Test case 마다 초기화 하실때는 arr_idx 와 Hash table 을 모두 초기화하셔야 합니다

 arr_idx = 0;    for(int i = 0; i < MAX_TABLE; i++)        hTable[i] = nullptr;

********************
추가로 삭제에 관한 사항입니다.

Sinlgle linked list, Hash 는 삭제를 고려하여 만들어진 것이 아니라 삭제코드는 좀 어렵습니다,

참고만 하시기 바라며,

삭제가 반드시 필요한 경우에는 dummy tail 을 넣어서 삭제하는 방법을 쓰시는 것이 더 편합니다.

(#6. 더블 링크드 리스트의 삭제를 참고하시기 바랍니다)

아래는 전통적인 삭제 코드입니다.

삭제는  해시키를 계산한 후,
hTable[key] 에서 삭제할 데이터를 검색, 검색된 노드의 이전 노드의 prev에   검색된 노드의  prev를 넣어주면 됩니다.

Single linked list 는 이전 노드를 찾아 갈 수 없으므로,
이전 노드의 prev 를 저장해야 하는 어려움이 있습니다.

 char search[7] = "vrvipy";
 int k = (int)myhash(search);
 NODE **del = &hTable[k];  //이전 노드의 위치를 저장할 포인터 변수
 
 
 for (NODE * iter = hTable[k]; iter != nullptr; iter = iter->prev)  //hTable[k]에서 모두 검색
 {
   if (!strncmp(search, iter->data, 6)) {   //삭제할 데이터를 찾으면
 
 
   cout << "FOUND & DEL : " << iter->data << endl << endl;
   *del = iter->prev;   //검색된 노드의 prev를   이전 노드 prev에 저장
  }
  del = &iter->prev;  //저장할 이전 노드 prev 위치를 변경
 }
 

감사합니다.

*  key를 만드는 데이터가 String 이 아니더라도 약간의 변경으로 적용이 가능하며,

*  이름, 부서, 전화번호 등등 여러 데이터를 모두 NODE 구조체에 넣고 이중 하나로 Hash key 로 사용하는 방법도 많이 사용됩니다.

main.cpp

#include <iostream> using namespace std; #define MAX_TABLE 10 int arr_idx = 0; struct NODE { char data[7]; NODE * prev; //싱글 리스트를 위해 추가. } a[20000]; NODE *myalloc(void) { return &a[arr_idx++]; } NODE *hTable[MAX_TABLE]; unsigned long myhash(const char *str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash << 5) + hash) + c) % MAX_TABLE; } return hash % MAX_TABLE; } int main(void) { freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); //for (int i = 0; i < 100; i++) //{ // for (int j = 0; j < 6; j++) // cout << (char)(rand() % 26 + 'a'); // cout << endl; //} arr_idx = 0; //사용할 배열 초기화 for (int i = 0; i < MAX_TABLE; i++) hTable[i] = nullptr; NODE *p; int key; char in[7]; int test_case; cin >> test_case; //Hash table 추가 for (int T = 0; T < test_case; T++) { cin >> in; //문자열을 입력 받습니다. key = (int)myhash(in); //문자열을 바탕으로 key 를 생성합니다. cout << "Add to Hash table " << key << " : " << in << endl; p = myalloc(); //저장할 공간을 alloc 합니다. strncpy(p->data, in, 7); //입력받은 문자열을 복사합니다. p->prev = hTable[key]; //Hash table 에 저장합니다. hTable[key] = p; //추가된 모든 노드 확인 for (int _tKey = 0; _tKey < MAX_TABLE; _tKey++) { cout << "Hash table( " << _tKey << " ) :"; for (NODE * pp = hTable[_tKey]; pp != NULL; pp = pp->prev) { cout << " " << pp->data; } cout << endl; } cout << endl << endl; } //Hash table 검색 char search[7] = "vrvipy"; cout << "Searching : " << search << endl; int k = (int)myhash(search); // hash key 생성 cout << "Hash table key : " << k << endl; //hash table [k] 에서 검색 for (NODE * pp = hTable[k]; pp != NULL; pp = pp->prev) { if (!strncmp(search, pp->data, 6)) cout << "FOUND : " << pp->data << endl << endl; } NODE **del = &hTable[k]; //이전 노드의 위치를 저장할 포인터 변수 for (NODE * iter = hTable[k]; iter != nullptr; iter = iter->prev) //hTable[k]에서 모두 검색 { if (!strncmp(search, iter->data, 6)) { //삭제할 데이터를 찾으면 cout << "FOUND & DEL : " << iter->data << endl << endl; *del = iter->prev; //현재 노드에 연결된 prev 노드를 이전 노드에 저장 } del = &iter->prev; //이전 노드를 변경 } //삭제 확인 cout << "Check delete"; for (NODE *iter = hTable[k]; iter != nullptr; iter = iter->prev) { if (!strncmp(search, iter->data, 6)) cout << "FOUND : " << iter->data << endl << endl; } }

input.txt

100 phqghu meayln lfdxfi rcvscx ggbwkf nqduxw fnfozv srtkjp repggx rpnrvy stmwcy syycqp evikef fmznim kkasvw srenzk ycxfxt lsgyps fadpoo efxzbc oejuvp vaboyg poeylf pbnplj vrvipy amyehw qnqrqp mxujjl oovaow uxwhms ncbxco ksfzkv atxdkn lyjyhf ixjswn kkufnu xxzrzb mnmgqo oketly hnkoau gzqrcd diutei ojwayy zpvscm psajlf vgubfa aovlzy lntrkd cpwsrt esjwhd izcobz cnfwlq ijtvdw vxhrcb ldvgyl wgbusb mborxt lhcsmp xohgmg nkeufd xotogb gxpeya nfetcu kepzsh kljugg gekjdq zjenpe vqgxie pjsrdz jazujl lchhbf qmkimw zobiwy bxduun fsksrs rtekmq dcyzje euhmsr qcozij ipfion eeddps zrnavy mmtatb dzqsoe muvnpp psuacb azuxmh ecthle grpunk dmbppw eqtgjo parmow zdqyox ytjbbh awdydc prjbxp hoohpk wqyuhr qzhnbn fuvqnq

#include <stdio.h> //#include <string.h> //#include <memory.h> #define MAX_KEY 12 #define MAX_DATA 12 #define MAX_TABLE 4096 typedef struct { char key[MAX_KEY + 1]; char data[MAX_DATA + 1]; }Hash; Hash tb[MAX_TABLE]; int mystrcmp(char *arr1, const char *arr2) { int i = 0; while (arr1[i] != '\0' || arr2[i] != '\0') { if (arr1[i] > arr2[i]) return arr1[i] - arr2[i]; else if (arr1[i] < arr2[i]) { return arr1[i] - arr2[i]; } i++; } return 0; } int mystrcpy(char* dest, const char* src) { int i = -1; while (src[++i] != 0) { *(dest + i) = *(src + i); } *(dest + i) = '\0'; return 0; } unsigned long hash(const char *str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash << 5) + hash) + c) % MAX_TABLE; } return hash % MAX_TABLE; } int find(const char *key, char *data) { unsigned long h = hash(key); int cnt = MAX_TABLE; while (tb[h].key[0] != 0 && cnt--) { if (mystrcmp(tb[h].key, key) == 0) { mystrcpy(data, tb[h].data); return 1; } h = (h + 1) % MAX_TABLE; } return 0; } int add(const char *key, char *data) { unsigned long h = hash(key); while (tb[h].key[0] != 0) { if (mystrcmp(tb[h].key, key) == 0) { return 0; } h = (h + 1) % MAX_TABLE; } mystrcpy(tb[h].key, key); mystrcpy(tb[h].data, data); return 1; } void* mymemset(void *dest, int fillChar, unsigned int count) { for (size_t i = 0; i < count; i++) { *((char*)dest + i) = fillChar; } return dest; } int main(int argc, char* argv[]) { freopen("input.txt", "r", stdin); int T, N, Q; scanf("%d", &T); for (int test_case = 1; test_case <= T; test_case++) { mymemset(tb, 0, sizeof(tb)); // 모두 0으로 셋팅 = 초기화 scanf("%d", &N); char k[MAX_KEY + 1]; char d[MAX_DATA + 1]; for (int i = 0; i < N; i++) { scanf("%s %s\n", &k, &d); add(k, d); } printf("#%d\n", test_case); scanf("%d", &Q); for (int i = 0; i < Q; i++) { char k[MAX_KEY + 1]; char d[MAX_DATA + 1]; scanf("%s\n", &k); if (find(k, d)) { printf("%s\n", d); } else { printf("not find\n"); } } } return 0; }

1. mymest, mystrcpy, mystrcmp 구현 함수 알기 2. stdio.h 에서 돌아가는 것 확인하기