포인터, alias 개념과 직접 구현 해시

새내기 때 나를 괴롭히던 포인터

&&*
보는 이에 따라 별보는 사람 혹은 참조와 포인터로 보일 수 있다.

🌟포인터와 Alias

📌포인터

선언과 초기화

포인터는 자료형 뒤에 *를 붙여서 선언한다.

p라는 포인터는 int형 변수의 주소를 담을 수 있다.
변수의 주소는 변수명 앞에 &를 붙여서 가져온다.

int* p; // 포인터 선언
int a = 5;
p = &a; // a의 주소를 담기
printf("%d", p); // a의 주소가 출력됨
printf("%d", *p); // 5 (a의 값이 출력됨)

값을 가져오는 방법

asterisk(*)을 포인터 변수 앞에 붙이면 포인터에 담긴 주소를 가지는 변수의 값을 가져올 수 있다.

*p를 print하게 되면 5가 출력된다.

📌별명(Alias)

alias는 어떤 변수의 주소를 똑같이 가지는 새로운 변수이다.
별칭 혹은 별명이라고 부른다. 껍데기만 다르고, 주소와 값은 같은 것이라 볼 수 있다.

대입 연산자로 변수에 값을 대입할 때는 변수의 값만이 복사된다.(주소는 무시된다.)

alias에는 어떤 변수의 값 뿐만 아니라 주소 또한 복사되어 alias 값을 변경하게 되면 원래 변수의 값도 같이 변경된다.

자료형 뒤에 &를 붙여서 선언한다.

int a = 5;
int& p = a; // alias 선언과 대입
printf("%d\n", p); // 5
p++;
printf("%d\n", a); // 6

📌포인터 배열

포인터는 주소를 저장하는 역할을 한다. 포인터 배열은 주소를 저장할 수 있는 공간이 여러개 이어져 있는 배열을 의미한다.

사혼의 구슬조각처럼 원하는 변수가 여기저기 흩어져있다면, 포인터 배열을 통해서 한데 묶어놓을 수 있다.

포인터 배열 내부에는 여기저기 흩어져있는 변수의 주소들이 담긴다.

링크드 리스트를 직접 구현하게 된다면, 노드들이 여기저기 흩어져있을테고, 흩어져있는 노드들의 연결을 포인터배열을 통해서 하게 된다.

---

 

해시?

🌟해시

📌해시테이블

해시 테이블은 (key, value) 쌍을 저장하는 자료구조로, 해시함수를 이용해 변환한 값을 key로 사용해 value를 저장한다.
충돌(collision) 해결 방식에 따라 개별체이닝(Seperate Chaining) 방식 또는 오픈어드레싱(Open Addressing) 방식을 사용한다.

📌해시함수

데이터를 고정값으로 변환해주는 함수로, 고정값은 해시테이블의 key로 사용된다.
해시함수는 해시테이블의 모든 연산(insert, find, erase)에서 쓰인다.
hash 함수를 거쳐 나온 key를 통해 해시테이블에서 value가 담기거나 담길 공간을 찾는다.
해시함수는 일반적으로 데이터에 소수 모듈러 연산을 한다.

📌충돌

서로 다른 value가 같은 key를 가지는 충돌이 필연적으로 발생한다. 모든 key의 해시값이 같은 최악의 경우에는 O(N)의 시간복잡도로 해시테이블에 담긴 모든 노드를 순차적으로 탐색해야한다.

📌충돌 해결

1. 소수 사용하기
   해시테이블의 크기는 소수를 사용한다. 해시함수 연산에서도 소수를 사용한다. 인수가 많은 수를 해시테이블의 크기로 사용하거나, 해시함수 연산에서 사용한다면, 같은 key에 많은 값들이 몰려 충돌할 것이다. 또한 해시테이블 내에 값이 고루 분포되지 못한다. 그렇기 때문에 전통적으로 인수가 1과 자기 자신뿐인 소수를 사용한다.
2. 참고 : https://medium.com/swlh/why-should-the-length-of-your-hash-table-be-a-prime-number-760ec65a75d1
3. 해시테이블 구현방식 - 개별체이닝(Seperate Chaining)
   충돌이 발생할 경우, 같은 key를 가지는 노드들을 연결(체이닝)해서 저장한다.
4. 해시테이블 구현방식 - 오픈어드레싱(Open Addressing)
   충돌이 발생할 경우, 비어있는 해시를 찾아서 노드를 저장한다. 세부적인 방식으로 선형탐색, 제곱탐색, 이중해시가 있다.

📌시간 · 공간 복잡도

해시테이블 시간복잡도

Operation	Average	Worst case
Search	Θ(1)	O(n)
Insert	Θ(1)	O(n)
Delete	Θ(1)	O(n)

해시테이블 공간복잡도

	Average	Worst case
Space	Θ(n)	O(n)

📌직접 구현한 해시

BOJ 7785 회사에 있는 사람 문제를 직접 구현한 해시로 풀이한 코드이다.
개별 체이닝 방식으로 구현했다.

#include <stdio.h>
#pragma warning(disable:4996)
#define PN 1009 // 해시함수 연산을 위한 적당히 큰 소수
#define NODE_MAX 1000001
#define HASH_MAX 10007

struct NODE {
    bool isEnter;
    char name[6];
    NODE* prev;
};

NODE node[NODE_MAX]; // 단순 노드 저장
int idx = 0;
NODE* hashTable[HASH_MAX]; // 포인터배열에서의 노드 위치
NODE* allNode[NODE_MAX]; // 모든 노드 주소를 저장
NODE* resNode[NODE_MAX]; // 결과 노드 주소만 저장
NODE* bufNode[NODE_MAX]; // 정렬용
int resCnt = 0, allCnt = 0;

unsigned int my_hash(const char* str) {
    unsigned int hash = 0;
    while (*str) hash = (hash * PN + *str++) % HASH_MAX;
    // 문자열 해시 방식. 
    // 현재까지의 해시값에 적당히 큰 소수를 곱하고 현재 문자를 더한 후, 해시테이블 크기로 모듈러 연산
    return hash % HASH_MAX;
}
int my_strcmp(const char* a, const char* b) { // 문자열 비교
    while (*a && *a == *b) a++, b++;
    return *a - *b; // 같으면 0, 다르면 0이 아닌 값 리턴
}
void my_strcpy(char* a, const char* b) { // 문자열 복사
    while (*b) *a++ = *b++;
    *a = 0; // char* 형 문자열은 마지막에 \0 추가 필요 
}
NODE* myalloc() { // 새로운 노드 저장 시 공간 할당
    return &node[idx++];
}
// 해시테이블 **개별 체이닝** 방식 구현
NODE* find(const char* str) { // 탐색
    unsigned int key = my_hash(str);
    for (NODE* pp = hashTable[key]; pp; pp = pp->prev) {
        if (my_strcmp(pp->name, str) == 0) return pp;
    }
    return NULL;
}
void insert(const char* str) { // 삽입
    NODE* myNode = find(str);
    if (myNode == NULL) {
        unsigned int key = my_hash(str);
        myNode = myalloc();
        my_strcpy(myNode->name, str);
        allNode[allCnt++] = myNode;
        myNode->prev = hashTable[key];
        hashTable[key] = myNode;
        // 해시테이블에서 삽입 노드의 키값으로 찾은 공간에(머리) 삽입노드의 주소를 넣음
        // 원래 머리에 있던 노드 주소를 삽입 노드의 prev로 넣음
    }
    myNode->isEnter = 1;
}
void erase(const char* str) { // 삭제
    NODE* myNode = find(str);
    if (myNode == NULL) return;
    myNode->isEnter = 0;
}
void merge(int l, int r) { // 병합
    int m = (l + r) / 2;
    int a = l, b = m, c = l;
    while (a < m && b < r && c < r) {
        if (my_strcmp(resNode[a]->name, resNode[b]->name) >= 0) bufNode[c++] = resNode[a++];
        else bufNode[c++] = resNode[b++];
    }
    while (a < m) bufNode[c++] = resNode[a++];
    while (b < r) bufNode[c++] = resNode[b++];
    for (int i = l; i < r; i++) resNode[i] = bufNode[i];
}
void mergeSort(int l, int r) { // 병합정렬
    if (r - l == 1) return; // 종료조건
    int m = (l + r) / 2;
    mergeSort(l, m);
    mergeSort(m, r);
    merge(l, r);
}
int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char s1[6], s2[6];
        scanf("%s %s", s1, s2);
        if (my_strcmp("enter", s2) == 0) insert(s1);
        else if (my_strcmp("leave", s2) == 0) erase(s1);
    }
    for (int i = 0; i < allCnt; i++) if (allNode[i]->isEnter) resNode[resCnt++] = allNode[i];
    mergeSort(0, resCnt);
    for (int i = 0; i < resCnt; i++) printf("%s\n", resNode[i]->name);
    return 0;
}