[c언어] 해시 테이블

26 Dec 2023

c언어

해시 테이블은 키-값 쌍을 저장하는 데 사용되는 데이터 구조입니다. 각 키는 해시 함수에 의해 해시 값으로 매핑되고, 해당 해시 값을 사용하여 데이터를 저장하거나 검색합니다. 이것은 데이터를 상수 시간 내에 검색할 수 있다는 의미입니다.

해시 테이블은 검색, 삽입 및 삭제 작업을 매우 효율적으로 수행할 수 있으며, 이러한 특성으로 인해 많은 프로그래밍 언어와 응용 프로그램에서 널리 사용됩니다.

해시 테이블의 작동 방식

해시 테이블은 일반적으로 배열을 사용하여 구현됩니다. 해시 함수는 각 키를 배열의 인덱스로 변환하여 값을 저장하거나 검색할 수 있도록 도와줍니다.

해시 충돌은 해시 함수가 다른 키를 동일한 해시 값으로 매핑할 때 발생합니다. 이러한 충돌을 해결하기 위해 일반적으로 체이닝(Chaining) 이나 개방 주소법 같은 기술을 사용합니다. 체이닝은 각 버킷에 연결 리스트를 사용하여 충돌을 해결하고, 개방 주소법은 충돌이 발생한 경우 다른 빈 버킷을 찾아내어 값을 저장합니다.

C언어에서 해시 테이블 구현

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 1000

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

typedef struct HashTable {
    Node *table[TABLE_SIZE];
} HashTable;

int hashFunction(char *key) {
    int hash = 0;
    for (int i = 0; i < strlen(key); i++) {
        hash += key[i];
    }
    return hash % TABLE_SIZE;
}

Node* createNode(char *key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void insert(HashTable* ht, char *key, int value) {
    int index = hashFunction(key);
    Node *newNode = createNode(key, value);
    if (ht->table[index] == NULL) {
        ht->table[index] = newNode;
    } else {
        Node *current = ht->table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

int main() {
    HashTable* hashtable = (HashTable*)malloc(sizeof(HashTable));
    insert(hashtable, "apple", 5);
    insert(hashtable, "banana", 7);
    insert(hashtable, "cherry", 10);
    // 해시 테이블을 이용한 다양한 작업 수행
    return 0;
}

위 코드는 해시 테이블의 기본 구현 예시로, 간단한 문자열 키-값 쌍을 저장하고 검색하는 방법을 보여줍니다.

결론

해시 테이블은 빠른 검색, 삽입 및 삭제 작업을 지원하며, 많은 프로그래밍 시나리오에서 실용적인 데이터 구조로 사용됩니다. C언어를 비롯한 많은 프로그래밍 언어에서 해시 테이블을 자체적으로 제공하거나 라이브러리를 통해 활용할 수 있습니다.

해시 테이블의 작동 방식

C언어에서 해시 테이블 구현

결론

참고 자료