Implement hashtable by C.
ํด์ํ ์ด๋ธ์ ๋ฐ์ดํฐ์ ์์ด ๋ง์ ๊ฒฝ์ฐ ์๊ธฐ๋ ๋ฐ์ดํฐ ๊ฒ์์ ๋ํ ์ฐ์ฐ๊ณผ์ ์ ์ค์ผ ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. key๊ฐ ์ฃผ์ด์ก์ ๋ value๋ฅผ ์ฐพ๊ธฐ ์ํ ๋ฐฉ๋ฒ์ผ๋ก ํด์ ํจ์๋ฅผ ์ฌ์ฉํ๋ค. input ์ผ๋ก key๊ฐ ๋ค์ด์ค๋ฉด ํด์ฌ ํจ์๋ฅผ ํตํ ํด์ฌ ์ธ๋ฑ์ค๊ฐ ๋์ค๊ณ ํด๋น ์ธ๋ฑ์ค๋ฅผ ํตํด ๋น ๋ฅด๊ฒ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ๋ค์ด๊ฐ๋ ๊ตฌ์กฐ์ด๋ค. ๊ทธ๋ฆผ์ ๋ณด์. ํค์ ํด์ํจ์๋ฅผ ํตํด ์ป์ ํด์ ์ธ๋ฑ์ค๋ก Bucket์ ์ธ๋ฑ์ค๋ฅผ ์ฐพ๋๋ค. ๊ทธ ๋ค์ ํค์ ๋ฐ์ดํฐ๊ฐ ์ ์ฅ๋ ๋ ธ๋๋ฅผ ๋ฒ์ผ ๋ค์ ๋ถ์ด๋ ํ์์ด๋ค. ๋จ์ ๋งํฌ๋ ๋ฆฌ์คํธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ์ ๋ ๊ฐ์ ์ฐพ๊ธฐ์ํด ๋ชจ๋ ๋ ธ๋๋ฅผ ์ํํด์ผํ๋ ๋ฐ๋ฉด ํด์ฌ ํ ์ด๋ธ์ ํค๋ฅผ ํตํด ๋ฐ๋ก ํด์ ์ธ๋ฑ์ค๋ก ์ ๊ทผํ ์ ์์ผ๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๊ฐ ์ค์ด๋ฆ์ ์ ์ ์๋ค. ๋ค๋ง, ์ ๊ทธ๋ฆผ์์ ์ ์ถํ ์ ์๋ฏ์ด ํ ์ธ๋ฑ์ค๋ก ๋ ธ๋๊ฐ ๋ชจ๋ ๋ชฐ๋ฆฌ๋ ๊ฒฝ์ฐ๊ฐ ์๊ธธ ์๋ ์๋ค. ๊ทธ๋ ๊ฒ ๋ ๊ฒฝ์ฐ ๋งํฌ๋ ๋ฆฌ์คํธ์ ๋ค๋ฅธ ์ ์ด ์์ผ๋ฏ๋ก ํด์ฌํ ์ด๋ธ์ ๊ฒ์์ ์๊ฐ๋ณต์ก๋๋ ์ต์ ์ ๊ฒฝ์ฐ O(n)์ด ๋ ์ ์๋ค.(n์ node์ ๊ฐ์) ๊ทธ๋์ ์ธ๋ฑ์ค๋ฅผ ๋ง๋๋ ํด์ ํจ์๊ฐ ๋ฌด์๋ณด๋ค ์ค์ํ ์๋ฃ๊ตฌ์กฐ๋ผ๊ณ ํ ์ ์๋ค.
๊ฐ์ฅ ์ด์์ ์ธ ํด์ํ ์ด๋ธ์ ํ ๋ฒ์ผ์ ๋ฑ ํ๊ฐ์ ๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ์ด๋ค. ๊ทธ๋ด ๊ฒฝ์ฐ์ ๋ฐ์ดํฐ ๊ฒ์์ ๊ฒฝ์ฐ ์ธ๋ฑ์ค๋ง ๊ณ์ฐํ๋ฉด ๋ฐ๋ก ๊ฐ์ ์ฐพ์ ์ ์์ผ๋ฏ๋ก O(1)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๋ณด์ฅํ ์ ์๋ค. ํ์ง๋ง ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ, ์ฆ, ํ ๋ฒ์ผ์ ์ฌ๋ฌ๊ฐ์ ๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ๋ฅผ ์ถฉ๋์ด๋ผ๊ณ ํ๋ค.
์ถฉ๋์ ํด๊ฒฐํ๋๋ฐ์๋ ํฌ๊ฒ ๋๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋ค. ์ฒด์ด๋๊ณผ ๊ฐ๋ฐฉ์ฃผ์๋ฐฉ๋ฒ์ด ์๋ค. ์ฒด์ด๋์ ํด๋น ์ธ๋ฑ์ค๋ฅผ ๋งํฌ๋ ๋ฆฌ์คํธ๋ก ๋ฌถ์ด์ ๊ณ์ ๋ค์ ๋ง๋ถ์ด๋ ์์ผ๋ก ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๊ณ ์์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ ํํ๊ฐ ๋๋ค. ๋๋ฒ์งธ ๊ฐ๋ฐฉ์ฃผ์๋ฐฉ๋ฒ์ ์ธ๋ฑ์ค์ ์ด๋ฏธ ๋ค๋ฅธ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๋ค๋ฅธ ์ธ๋ฑ์ค๋ฅผ ํ์ํด์ ๋น ์ธ๋ฑ์ค์ ์ฝ์ ํ๋ ๋ฐฉ์์ด๋ค.(๋ ์จ๊ฒจ์ง ๋ด์ฉ์ด ๋ง๋ค. ๋์ค์ ์์๋ณด์)
์ฌ๋งํ low๋จ์ด ์๋ ์ธ์ด๋ค์ ํด์ ํจ์๋ฅผ ๊ธฐ๋ณธ์ ์ผ๋ก ์ ๊ณตํ๋๋ฐ ์ฌ๊ธฐ์๋ ํ์ด์ฌ์์ ๋ฌธ์์ด์ ํด์ฌํ๋ ํจ์๋ง ์์๋ก ๋ณด์.
static long string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;
if (a->ob_shash != -1)
return a->ob_shash;
len = Py_SIZE(a);
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= Py_SIZE(a);
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}
๋งค์ฐ ๋ณต์กํ ๊ณผ์ ์ ํตํด ์ธ๋ฑ์ค์ ์ค๋ณต์ ์์ ๋ ค๊ณ ํจ์ ์ ์ ์๋ค. ๋ฐ๋ผ์ ํ์ด์ฌ์์ ํด์ํ ์ด๋ธ์ ์ฌ์ฉํ set, dict๋ฅผ ์ฌ์ฉํ ๋ ์ฌ๋งํ ๋ฐ์ดํฐ ํฌ๊ธฐ๋ผ๋ฉด ์๊ฐ๋ณต์ก๋ ๊ฑฑ์ ์ ํฌ๊ฒ ํ์ง ์๊ณ ์ฌ์ฉํ ์ ์๋ค.
์ถ๊ฐ๋ก ์ฒด์ด๋ํ ๋ ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ singly linked list๋ก ๋ง๋ค๊ฑฐ๋ ํน์ doubly linked list๋ก ๋ง๋ค์ ์๋๋ฐ ๋์ ๋ชจ๋ ๋ง๋ค์ด๋ณด๊ณ ๊ทธ ์ฐจ์ด์ ์ ์์๋ณด๋ ค๊ณ ํ๋ค.
medium / @bartobri stackoverflow / Where can I find source or algorithm of Python's hash() function? youtube / (์๋ฃ๊ตฌ์กฐ) ํด์ํ ์ด๋ธ(๋ฆฌ์คํธ, ์ฒด์ด๋) C์ธ์ด๋ก ์ฝ๋ฉํด์ - by Gunny
// ์ฒด์ด๋์ singly linked list ๋ก ํ ํด์ ํ
์ด๋ธ ๊ตฌํ
#include <stdio.h>
#include <stdlib.h> // ๋ฉ๋ชจ๋ฆฌ ํ ๋น์ ์ํจ
struct bucket* hashTable = NULL;
int BUCKET_SIZE = 10; // ๋ฒ์ผ์ ์ด ๊ธธ์ด
ํด์ํ ์ด๋ธ์ ๋ฒ์ผ์ ํตํด ์ ๊ทผํ๊ธฐ ๋๋ฌธ์ hashTable์ด๋ผ๋ ์ด๋ฆ์ผ๋ก bucket ๋ฐฐ์ด ์ฃผ์๊ฐ์ ์ ์ธํด๋๋ค. ๋ฒ์ผ์ ์ด ๊ธธ์ด๋ 10์ด ๋๋ค.
// ๋
ธ๋ ๊ตฌ์กฐ์ฒด ์ ์ธ
struct node {
int key; // ํด์ ํจ์์ ์ฌ์ฉ๋ ํค
int value; // key ๊ฐ ๊ฐ์ง๊ณ ์๋ ๋ฐ์ดํฐ
struct node* next; // ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ
};
// ๋ฒ์ผ ๊ตฌ์กฐ์ฒด ์ ์ธ
struct bucket{
struct node* head; // ๋ฒ์ผ ๊ฐ์ฅ ์์ ์๋ ๋
ธ๋์ ํฌ์ธํฐ
int count; // ๋ฒ์ผ์ ๋ค์ด์๋ ๋
ธ๋์ ๊ฐ์
};
๋ ธ๋์ ๋ฒ์ผ์ ๊ตฌ์กฐ์ฒด๋ฅผ ์ ์ธํ๋ค. ๋ ธ๋ - ๋ ธ๋์๋ key, value๊ฐ ์๊ณ ์ฒด์ด๋์ด ๋์์ ๋ ๋ค์ ๋ ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ next ํฌ์ธํฐ๋ฅผ ๋ฉค๋ฒ๋ก ๊ฐ๋๋ค. ๋ฒ์ผ - ๋ฒ์ผ์๋ ๋ฒ์ผ์ ์๋ ์ฒซ๋ฒ์งธ ๋ ธ๋์ ํฌ์ธํฐ์ ํด๋น ๋ฒ์ผ์ ์๋ ๋ ธ๋์ ๊ฐ์์ธ count๋ฅผ ๋ฉค๋ฒ๋ก ๊ฐ๋๋ค.
์ด์ ๋ถํฐ ํด์ํ ์ด๋ธ์์ ํ์ํ ํจ์๋ฅผ ๊ตฌํํด๋ณด๋ ค๊ณ ํ๋ค. ํ์ํ ํจ์๋ ๋ค์๊ณผ ๊ฐ๋ค.
createNode -> ์๋ก์ด ๋ ธ๋๋ฅผ ๋ง๋ค์ด์ฃผ๋ ํจ์ hashFunction -> ํค๋ฅผ ํด์ฌ ์ธ๋ฑ์ค๋ก ๋ณํํด์ฃผ๋ ํด์ฌ ํจ์ add -> ํค๋ฅผ ํด์ฌ ํ ์ด๋ธ์ ์ถ๊ฐํ๋ ํจ์ remove_key -> ํค๋ฅผ ํด์ฌ ํ ์ด๋ธ์์ ์ญ์ ํ๋ ํจ์ search -> ํค์ ๋ฐ์ดํฐ๊ฐ์ ์ฐพ์์ฃผ๋ ํจ์ display -> ํด์ฌํ ์ด๋ธ ์์ฒด๋ฅผ ์ถ๋ ฅํด์ ๋ณด์ฌ์ฃผ๋ ํจ์
// ํด์ฌํ
์ด๋ธ ์ฝ์
๋ ๋ ์๋ก ๋
ธ๋๋ฅผ ์์ฑํด์ฃผ๋ ํจ์(์ด๊ธฐํ)
struct node* createNode(int key, int value){
struct node* newNode;
// ๋ฉ๋ชจ๋ฆฌ ํ ๋น
newNode = (struct node *)malloc(sizeof(struct node));
// ์ฌ์ฉ์๊ฐ ์ ํด์ค ๊ฐ์ ๋์
newNode->key = key;
newNode->value = value;
newNode->next = NULL; // ์์ฑํ ๋๋ next๋ฅผ NULL๋ก ์ด๊ธฐํ
return newNode;
}
์ฌ์ฉ์๊ฐ ๋๊ฒจ์ค key, value๋ก ํด์ฌํ ์ด๋ธ์ ์ถ๊ฐํ๊ธฐ ์ ์ ๋ ธ๋ ๊ตฌ์กฐ์ฒด๋ฅผ ๋ง๋ค์ด ์ฃผ๋ ํจ์์ด๋ค.
// ํด์ฌํจ์ ๋ง๋ค๊ธฐ. ์ฌ๊ธฐ์๋ ๋จ์ํ key๋ฅผ ๋ฒ์ผ ๊ธธ์ด๋ก ๋๋ ๋๋จธ์ง๋ก ํจ์๋ฅผ ๋ง๋ฆ.
int hashFunction(int key){
return key%BUCKET_SIZE;
}
์ถฉ๋์ ํผํ ํด์ฌํจ์๋ฅผ ๋ง๋๋๊ฒ ์ค์ํ์ง๋ง ๋ณธ ๊ธ์์๋ ์ค๋ช ์ ์ํด ๊ฐ๋จํ key๊ฐ์ bucket ๊ธธ์ด์ธ 10์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ธ๋ฑ์ค๋ก ๋ฐํํ๋ ํด์ ํจ์๋ฅผ ๋ง๋ค์ด๋ณด์๋ค.
// ์๋ก ํค ์ถ๊ฐํ๋ ํจ์
void add(int key, int value){
// ์ด๋ ๋ฒ์ผ์ ์ถ๊ฐํ ์ง ์ธ๋ฑ์ค๋ฅผ ๊ณ์ฐ
int hashIndex = hashFunction(key);
// ์๋ก ๋
ธ๋ ์์ฑ
struct node* newNode = createNode(key, value);
// ๊ณ์ฐํ ์ธ๋ฑ์ค์ ๋ฒ์ผ์ ์๋ฌด ๋
ธ๋๋ ์์ ๊ฒฝ์ฐ
if (hashTable[hashIndex].count == 0){
hashTable[hashIndex].count = 1;
hashTable[hashIndex].head = newNode; // head๋ฅผ ๊ต์ฒด
}
// ๋ฒ์ผ์ ๋ค๋ฅธ ๋
ธ๋๊ฐ ์์ ๊ฒฝ์ฐ ํ์นธ์ฉ ๋ฐ๊ณ ๋ด๊ฐ ํค๋๊ฐ ๋๋ค(์ค์ ๋ก๋ ํฌ์ธํฐ๋ง ๋ฐ๊ฟ์ค)
else{
newNode->next = hashTable[hashIndex].head;
hashTable[hashIndex].head = newNode;
hashTable[hashIndex].count++;
}
}
ํค๊ฐ ์ถ๊ฐ๋ ๋ ์ฒด์ด๋์ ์ด๋ ๋ถ๋ถ์ ์ฝ์ ๋์ด๋ ์๊ด์์ง๋ง ๋ณธ ๊ธ์์๋ ์ถ๊ฐ๋ ํค๊ฐ ํญ์ ๋ฒ์ผ์ head๊ฐ ๋๋๋ก ํ์๋ค.
// ํค๋ฅผ ์ญ์ ํด์ฃผ๋ ํจ์
void remove_key(int key){
int hashIndex = hashFunction(key);
// ์ญ์ ๊ฐ ๋์๋์ง ํ์ธํ๋ flag ์ ์ธ
int flag = 0;
// ํค๋ฅผ ์ฐพ์์ค iterator ์ ์ธ
struct node* node;
struct node* before; // ๋
ธ๋๊ฐ ์ง๋๊ฐ ๋ฐ๋ก ์ ๋
ธ๋
// ๋ฒ์ผ์ head๋ถํฐ ์์
node = hashTable[hashIndex].head;
// ๋ฒ์ผ์ ์ํํ๋ฉด์ key๋ฅผ ์ฐพ๋๋ค.
while (node != NULL) // NULL ์ด ๋์ฌ๋๊น์ง ์ํ
{
if (node->key == key){
// ํฌ์ธํฐ ๋ฐ๊ฟ์ฃผ๊ธฐ ๋
ธ๋๊ฐ 1 . ํค๋์ธ ๊ฒฝ์ฐ 2 . ํค๋๊ฐ ์๋๊ฒฝ์ฐ
if (node == hashTable[hashIndex].head){
hashTable[hashIndex].head = node->next; // ๋ค์ ๋
ธ๋๊ฐ ์ด์ ํค๋
}
else{
before->next = node->next; // ์ ๋
ธ๋๊ฐ ์ด์ ๋ด ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํด
}
// ๋๋จธ์ง ์์
์ํ
hashTable[hashIndex].count--;
free(node);
flag = 1;
}
before = node; // ๋
ธ๋ ๋ฐ๊ฟ์ฃผ๊ธฐ ์ ์ ์ ์ฅ
node = node->next;
}
// flag์ ๊ฐ์ ๋ฐ๋ผ ์ถ๋ ฅ ๋ค๋ฅด๊ฒ ํด์ค
if (flag == 1){ // ์ญ์ ๊ฐ ๋์๋ค๋ฉด
printf("\n [ %d ] ์ด/๊ฐ ์ญ์ ๋์์ต๋๋ค. \n", key);
}
else{ // ํค๊ฐ ์์ด์ ์ญ์ ๊ฐ ์๋ ๊ฒฝ์ฐ
printf("\n [ %d ] ์ด/๊ฐ ์กด์ฌํ์ง ์์ ์ญ์ ํ์ง ๋ชปํ์ต๋๋ค.\n", key);
}
}
remove ํจ์๊ฐ doubly linked list๋ก ์ฒด์ด๋์ ๊ตฌํํ ๋ฐฉ์๊ณผ ๊ฐ์ฅ ํฐ ์ฐจ์ด๊ฐ ์๋ ๋ถ๋ถ์ด๋ค.
๊ทธ๋ฆผ๊ณผ ๊ฐ์ด A, B, C ๋ ธ๋๊ฐ ์ฒด์ด๋๋์ด์์ ๋ B๋ฅผ ์ญ์ ํ๋ค๊ณ ๊ฐ์ ํด๋ณด์. ๊ทธ๋ ๊ฒ ๋๋ฉด A์ next ํฌ์ธํฐ๋ฅผ C๋ก ๋ฐ๊ฟ์ฃผ๋ ๊ณผ์ ์ด ํ์ํ๋ฐ ์ด๋ B์์๋ A๋ก doubly linked list์ ๋ฌ๋ฆฌ ๋ฐ๋ก ์ ๊ทผํ ์๊ฐ ์์ผ๋ฏ๋ก ํ๋ฒ ๋ search๋ฅผ ํด์ค์ผํ๋ ๋ถ์์ฌ๊ฐ ์๊ธฐ๋ฏ๋ก ์ฐ์ฐ๊ณผ์ ์ด ๋ ๋ค๊ฒ ๋๋ค.
ํ์ง๋ง ๋ณธ ๊ธ remove_key์์๋ ๋ค์ ๋ ธ๋๋ก ๋ฐ๋ณต์๊ฐ ์ด๋ํ๊ธฐ ์ ์ ๋ฏธ๋ฆฌ before์ ํฌ์ธํฐ๋ฅผ ์ ์ฅํด๋ ์ผ๋ก์ ํด๋น ์ถ๊ฐ ๊ฒ์ ์ฐ์ฐ๊ณผ์ ์ ํผํ๋ค.
// ํค๋ฅผ ์ฃผ๋ฉด value๋ฅผ ์๋ ค์ฃผ๋ ํจ์
void search(int key){
int hashIndex = hashFunction(key);
struct node* node = hashTable[hashIndex].head;
int flag = 0;
while (node != NULL)
{
if (node->key == key){
flag = 1;
break;
}
node = node->next;
}
if (flag == 1){ // ํค๋ฅผ ์ฐพ์๋ค๋ฉด
printf("\n ํค๋ [ %d ], ๊ฐ์ [ %d ] ์
๋๋ค. \n", node->key, node->value);
}
else{
printf("\n ์กด์ฌํ์ง ์์ ํค๋ ์ฐพ์ ์ ์์ต๋๋ค. \n");
}
}
ํด๋น value๋ฅผ ๋ฐํํ์ง์๊ณ ์ถ๋ ฅํ๋ ์์ผ๋ก ๊ฐ๋จํ๊ฒ ๊ตฌํํด๋ณด์๋ค.
// ํด์ํ
์ด๋ธ ์ ์ฒด๋ฅผ ์ถ๋ ฅํด์ฃผ๋ ํจ์
void display(){
// ๋ฐ๋ณต์ ์ ์ธ
struct node* iterator;
printf("\n========= display start ========= \n");
for (int i = 0; i<BUCKET_SIZE; i++){
iterator = hashTable[i].head;
printf("Bucket[%d] : ", i);
while (iterator != NULL)
{
printf("(key : %d, val : %d) -> ", iterator->key, iterator->value);
iterator = iterator->next;
}
printf("\n");
}
printf("\n========= display complete ========= \n");
}
ํด์ํ ์ด๋ธ ๋ฒํท ์ ์ฒด๋ฅผ ์ํํ๋ฉด์ ์ถ๋ ฅํด์ฃผ๋ ํจ์์ด๋ค.
int main(){
// ํด์ํ
์ด๋ธ ๋ฉ๋ชจ๋ฆฌ ํ ๋น
hashTable = (struct bucket *)malloc(BUCKET_SIZE * sizeof(struct bucket));
}
-o [name] ์์ฑ์ ๋ถ์ฌ์ single์ด๋ผ๋ ์ด๋ฆ์ผ๋ก ์คํํ์ผ์ ๋ง๋ค์๋ค.
// 15 ๊น์ง ๊ฐ ์ถ๊ฐ
for (int i=0; i < 16; i++){
add(i, 10*i);
}
// ๋ช๊ฐ ๋ ์ถ๊ฐ
add(21, 210);
add(31, 310);
add(41, 410);
display();
remove_key(31);
remove_key(11);
remove_key(51);
display();
search(11);
search(1);
์์์ ๊ตฌํํ ๋ด์ฉ๊ณผ ๊ฑฐ์ ๋์ผํ๋ ์ฐจ์ด๊ฐ ์๋ ๊ณณ๋ง ๊ธ๋ก ์ฎ๊ธฐ๋๋ก ํ๊ฒ ๋ค.
// ๋
ธ๋ ๊ตฌ์กฐ์ฒด ์ ์ธ
struct node {
int key; // ํด์ ํจ์์ ์ฌ์ฉ๋ ํค
int value; // key ๊ฐ ๊ฐ์ง๊ณ ์๋ ๋ฐ์ดํฐ
struct node* next; // ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ
struct node* previous; // ์ด์ ๋
ธ๋๋ฅผ ๊ฐ๋ฅดํค๋ ํฌ์ธํฐ
};
์๋กญ๊ฒ previous๋ผ๋ ํฌ์ธํฐ๊ฐ ์๊ฒผ๋ค. ๋น์ฐํ createNode์์ previous ํฌ์ธํฐ๋ NULL๋ก ์ด๊ธฐํ ํด์ค๋ค. ์ด ํจ์ ๋ถ๋ถ์ ์๋ตํ๋ค.
// ๋ฒ์ผ์ ๋ค๋ฅธ ๋
ธ๋๊ฐ ์์ ๊ฒฝ์ฐ ํ์นธ์ฉ ๋ฐ๊ณ ๋ด๊ฐ ํค๋๊ฐ ๋๋ค(์ค์ ๋ก๋ ํฌ์ธํฐ๋ง ๋ฐ๊ฟ์ค)
else{
hashTable[hashIndex].head->previous = newNode; // ์ถ๊ฐ
newNode->next = hashTable[hashIndex].head;
hashTable[hashIndex].head = newNode;
hashTable[hashIndex].count++;
}
add ํจ์์์ else๋ถ๋ถ์ ํ์ค์ด ์ถ๊ฐ๋์๋ค. ํ์นธ ๋ค๋ก ๋ฐ๋ ค๋๊ธฐ ๋๋ฌธ์ ์๋กญ๊ฒ ๋ค์ด์จ node๊ฐ ์๋ ์๋ head์ previous๊ฐ ๋๋ค.
// ํค๋ฅผ ์ญ์ ํด์ฃผ๋ ํจ์
void remove_key(int key){
int hashIndex = hashFunction(key);
// ์ญ์ ๊ฐ ๋์๋์ง ํ์ธํ๋ flag ์ ์ธ
int flag = 0;
// ํค๋ฅผ ์ฐพ์์ค iterator ์ ์ธ
struct node* node;
// struct node* before; // ํ์ ์์!
// ๋ฒ์ผ์ head๋ถํฐ ์์
node = hashTable[hashIndex].head;
// ๋ฒ์ผ์ ์ํํ๋ฉด์ key๋ฅผ ์ฐพ๋๋ค.
while (node != NULL) // NULL ์ด ๋์ฌ๋๊น์ง ์ํ
{
if (node->key == key){
// ํฌ์ธํฐ ๋ฐ๊ฟ์ฃผ๊ธฐ ๋
ธ๋๊ฐ 1 . ํค๋์ธ ๊ฒฝ์ฐ 2 . ํค๋๊ฐ ์๋๊ฒฝ์ฐ
if (node == hashTable[hashIndex].head){
node->next->previous = NULL; // ์ถ๊ฐ ์ด์ ๋ค์๊ป ํค๋๊ฐ ๋์์ผ๋ฏ๋ก previous๊ฐ ์์
hashTable[hashIndex].head = node->next; // ๋ค์ ๋
ธ๋๊ฐ ์ด์ ํค๋
}
else{
node->previous->next = node->next; // ๋ด ์ ๋
ธ๋์ ์์ด ์ด์ ๋ด ์ ๋
ธ๋
node->next->previous = node->previous; // ๋ด ์ ๋
ธ๋์ ์ ์ด ์ด์ ๋ด ์ ๋
ธ๋
}
// ๋๋จธ์ง ์์
์ํ
hashTable[hashIndex].count--;
free(node);
flag = 1;
}
node = node->next;
}
// flag์ ๊ฐ์ ๋ฐ๋ผ ์ถ๋ ฅ ๋ค๋ฅด๊ฒ ํด์ค
if (flag == 1){ // ์ญ์ ๊ฐ ๋์๋ค๋ฉด
printf("\n [ %d ] ์ด/๊ฐ ์ญ์ ๋์์ต๋๋ค. \n", key);
}
else{ // ํค๊ฐ ์์ด์ ์ญ์ ๊ฐ ์๋ ๊ฒฝ์ฐ
printf("\n [ %d ] ์ด/๊ฐ ์กด์ฌํ์ง ์์ ์ญ์ ํ์ง ๋ชปํ์ต๋๋ค.\n", key);
}
}
์ผ๋จ ์ง๋์จ ๋ ธ๋๋ฅผ ์ ์ฅํ๋ before๋ ํ์๊ฐ ์๊ฒ๋์๋ค. ๊ทธ๋ฆฌ๊ณ ํฌ์ธํฐ๋ฅผ ๋ฐ๊ฟ์ค ๋ previous๋ก ๋ฐ๋ก ์ ๊ทผํ์ฌ ํฌ์ธํฐ๋ฅผ ๋ฐ๊ฟ์ฃผ๋ ๋ฐฉ์์ผ๋ก ์์ ๋์๋ค.
์ถ๋ ฅ๋ ๋์ผํจ์ ์ ์ ์๋ค. doubly linked list์๋ -> ํ์ดํ๊ฐ ์๋ <-> ํ์ดํ๋ฅผ ์ถ๋ ฅํด ์ฐจ๋ณ์ ์ ๋์๋ค :)