Implement hashtable by C.
해시테이블은 데이터의 양이 많을 경우 생기는 데이터 검색에 대한 연산과정을 줄일 수 있는 자료구조이다. key가 주어졌을 때 value를 찾기 위한 방법으로 해시 함수를 사용한다. input 으로 key가 들어오면 해쉬 함수를 통한 해쉬 인덱스가 나오고 해당 인덱스를 통해 빠르게 데이터를 찾아 들어가는 구조이다. 그림을 보자.
가장 이상적인 해시테이블은 한 버켓에 딱 한개의 노드가 있는 경우이다. 그럴 경우에 데이터 검색의 경우 인덱스만 계산하면 바로 값을 찾을 수 있으므로 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);
}
}
// 키를 주면 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));
}
// 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로 바로 접근하여 포인터를 바꿔주는 방식으로 수정되었다.
