C/C++에서 샘플 해시 테이블을 구현하는 방법
소개
C/C++의 해시 테이블은 키를 값에 매핑하는 데이터 구조입니다. 해시 테이블은 해시 함수를 사용하여 키에 대한 인덱스를 계산합니다. 해시 테이블 인덱스를 기반으로 적절한 위치에 값을 저장할 수 있습니다.
해시 테이블 사용의 이점은 매우 빠른 액세스 시간입니다. 일반적으로 시간 복잡도(할부 상환 시간 복잡도)는 일정한 O(1) 액세스 시간입니다.
두 개의 서로 다른 키가 동일한 색인을 얻는 경우 이러한 충돌을 설명하기 위해 다른 데이터 구조(버킷)를 사용해야 합니다. 아주 좋은 해시 함수를 선택하면 충돌 가능성을 무시할 수 있습니다.
C++ STL(표준 템플릿 라이브러리)에는 std::unordered_map() 데이터 구조가 있습니다.
이 기사에서는 다음으로 구성된 해시 테이블을 처음부터 구성합니다.
- 키를 값에 매핑하는 해시 함수
삽입,검색및삭제작업을 지원하는 해시 테이블 데이터 구조- 키 충돌을 설명하기 위한 데이터 구조.
해시 함수 선택
첫 번째 단계는 충돌 가능성이 낮은 합리적으로 좋은 해시 함수를 선택하는 것입니다. 그러나 이 자습서의 목적을 위해 해시 충돌을 더 잘 설명하기 위해 잘못된 해시 함수가 적용됩니다. 이 제한된 예제는 문자열(또는 C의 문자 배열)만 사용합니다.
#define CAPACITY 50000 // Size of the HashTable.
unsigned long hash_function(char* str)
{
unsigned long i = 0;
for (int j = 0; str[j]; j++)
i += str[j];
return i % CAPACITY;
}
이 코드를 실행하고 잠재적 충돌에 대해 다른 문자열을 테스트합니다. 예를 들어 문자열 Hel과 Cau는 동일한 ASCII 값을 가지므로 충돌합니다.
이 코드는 해시 테이블 용량 범위 내에서 숫자를 반환해야 합니다. 그렇지 않으면 바인딩되지 않은 메모리 위치에 액세스하여 오류가 발생할 수 있습니다.
해시 테이블 데이터 구조 정의
해시 테이블은 { key: value } 쌍인 항목의 배열입니다.
먼저 항목 구조를 정의합니다.
// Defines the HashTable item.
typedef struct Ht_item
{
char* key;
char* value;
} Ht_item;
이제 해시 테이블에는 Ht_item을 가리키는 포인터 배열이 있으므로 이중 포인터입니다.
// Defines the HashTable.
typedef struct HashTable
{
// Contains an array of pointers to items.
Ht_item** items;
int size;
int count;
} HashTable;
해시 테이블은 count를 사용하여 해시 테이블의 요소 수를 반환하고 size를 사용하여 해시 테이블의 크기를 반환해야 합니다.
해시 테이블 및 해시 테이블 항목 만들기
다음으로 메모리 할당 및 항목 생성을 위한 함수를 만듭니다.
키와 값에 대한 메모리를 할당하여 항목을 만들고 항목에 대한 포인터를 반환합니다.
Ht_item* create_item(char* key, char* value)
{
// Creates a pointer to a new HashTable item.
Ht_item* item = (Ht_item*) malloc(sizeof(Ht_item));
item->key = (char*) malloc(strlen(key) + 1);
item->value = (char*) malloc(strlen(value) + 1);
strcpy(item->key, key);
strcpy(item->value, value);
return item;
}
메모리를 할당하고 size, count 및 items를 설정하여 테이블을 만듭니다.
HashTable* create_table(int size)
{
// Creates a new HashTable.
HashTable* table = (HashTable*) malloc(sizeof(HashTable));
table->size = size;
table->count = 0;
table->items = (Ht_item**) calloc(table->size, sizeof(Ht_item*));
for (int i = 0; i < table->size; i++)
table->items[i] = NULL;
return table;
}
앞의 예제는 래퍼 구조 HashTable에 대한 메모리를 할당하고 모든 항목을 NULL로 설정합니다.
메모리 확보는 C/C++ 모범 사례입니다. malloc() 및 calloc()을 사용하여 힙에 할당한 메모리를 확보하십시오.
테이블 항목과 전체 테이블을 해제하는 함수를 작성합니다.
void free_item(Ht_item* item)
{
// Frees an item.
free(item->key);
free(item->value);
free(item);
}
void free_table(HashTable* table)
{
// Frees the table.
for (int i = 0; i < table->size; i++)
{
Ht_item* item = table->items[i];
if (item != NULL)
free_item(item);
}
free(table->items);
free(table);
}
print_table()을 추가하여 각 항목에 대한 index, key 및 value를 표시합니다.
void print_table(HashTable* table)
{
printf("\nHash Table\n-------------------\n");
for (int i = 0; i < table->size; i++)
{
if (table->items[i])
{
printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i] -> key, table->items[i]->value);
}
}
printf("-------------------\n\n");
}
이것으로 사용자 지정 해시 테이블의 기본 기능을 마칩니다. 이제 삽입, 검색 및 삭제 기능을 작성합니다.
해시 테이블에 삽입
삽입을 수행하는 ht_insert() 함수를 만듭니다.
이 함수는 HashTable 포인터, 키 및 값을 매개변수로 사용합니다.
void ht_insert(HashTable* table, char* key, char* value)
{
...
}
이제 ht_insert() 함수와 관련된 특정 단계가 있습니다.
{ key: value }쌍을 기반으로 항목을 생성합니다.- 해시 함수를 기반으로 인덱스를 계산합니다.
키를 비교하여 인덱스가 이미 사용 중인지 확인합니다.\n- 사용하지 않는 경우
인덱스에 직접 삽입할 수 있습니다. - 그렇지 않으면 충돌이며 처리해야 합니다.
이 튜토리얼에서는 초기 모델이 생성된 후 충돌 처리를 다룹니다.
먼저 항목을 만듭니다.
create_item(key, value)그런 다음 인덱스를 계산합니다.
int index = hash_function(key);키를 처음 삽입할 때 항목은
NULL이어야 합니다.// Creates the item. Ht_item* item = create_item(key, value); // Computes the index. int index = hash_function(key); Ht_item* current_item = table->items[index]; if (current_item == NULL) { // Key does not exist. if (table->count == table->size) { // HashTable is full. printf("Insert Error: Hash Table is full\n"); free_item(item); return; } // Insert directly. table->items[index] = item; table->count++; }동일한 항목이 해시 테이블에 삽입되었기 때문에
{ key: value }쌍이 이미 존재하는 시나리오를 고려하십시오. 이 문제를 해결하려면 코드에서 항목 값을 새 값으로 업데이트해야 합니다.if (current_item == NULL) { ... } else { // Scenario 1: Update the value. if (strcmp(current_item->key, key) == 0) { strcpy(table->items[index] -> value, value); return; } }충돌을 처리해야 하는 시나리오를 고려하십시오. 이 문제를 해결하기 위해 자리 표시자가 추가되었습니다.
void handle_collision(HashTable* table, Ht_item* item) { } void ht_insert(HashTable* table, char* key, char* value) { ... if (current_item == NULL) { ... } else { // Scenario 1: Update the value. if (strcmp(current_item->key, key) == 0) { ... } else { // Scenario 2: Handle the collision. handle_collision(table, item); return; } } }이제
ht_insert()함수가 완성되었습니다.해시 테이블에서 항목 검색
키가 존재하는지 확인하고 존재하는 경우 해당 값을 반환하는 함수
ht_search()를 만듭니다.이 함수는
HashTable포인터와key를 매개변수로 사용합니다.char* ht_search(HashTable* table, char* key) { ... }HashTable에서키가 있는 항목을 검색합니다.HashTable에서 항목을 찾을 수 없으면NULL이 반환됩니다.char* ht_search(HashTable* table, char* key) { // Searches for the key in the HashTable. // Returns NULL if it doesn't exist. int index = hash_function(key); Ht_item* item = table->items[index]; // Provide only non-NULL values. if (item != NULL) { if (strcmp(item->key, key) == 0) return item->value; } return NULL; }key와 일치하는 항목을 표시하려면print_search()를 추가하세요.void print_search(HashTable* table, char* key) { char* val; if ((val = ht_search(table, key)) == NULL) { printf("Key:%s does not exist\n", key); return; } else { printf("Key:%s, Value:%s\n", key, val); } }이제
ht_search()기능이 완성되었습니다.충돌 처리
충돌을 해결하는 방법에는 여러 가지가 있습니다. 이 튜토리얼은 동일한 해시 인덱스를 가진 모든 항목에 대해 독립적인 체인을 생성하는 것을 목표로 하는 Separate Chaining이라는 방법에 의존합니다. 이 튜토리얼의 구현은 연결된 목록을 사용하여 이러한 체인을 생성합니다.
충돌이 발생할 때마다 동일한 인덱스에서 충돌하는 추가 항목이 오버플로 버킷 목록에 추가됩니다. 따라서 해시 테이블에서 기존 레코드를 삭제할 필요가 없습니다.
삽입, 검색 및 삭제에
O(n)시간 복잡도를 갖는 연결 목록으로 인해 충돌 시 최악의 액세스 시간은O(n)도 마찬가지입니다. 이 방법의 장점은 해시 테이블의 용량이 적은 경우 좋은 선택이라는 것입니다.오버플로 버킷 목록을 구현합니다.
// Defines the LinkedList. typedef struct LinkedList { Ht_item* item; struct LinkedList* next; } LinkedList;; LinkedList* allocate_list() { // Allocates memory for a LinkedList pointer. LinkedList* list = (LinkedList*) malloc(sizeof(LinkedList)); return list; } LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item) { // Inserts the item onto the LinkedList. if (!list) { LinkedList* head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; } else if (list->next == NULL) { LinkedList* node = allocate_list(); node->item = item; node->next = NULL; list->next = node; return list; } LinkedList* temp = list; while (temp->next->next) { temp = temp->next; } LinkedList* node = allocate_list(); node->item = item; node->next = NULL; temp->next = node; return list; } Ht_item* linkedlist_remove(LinkedList* list) { // Removes the head from the LinkedList. // Returns the item of the popped element. if (!list) return NULL; if (!list->next) return NULL; LinkedList* node = list->next; LinkedList* temp = list; temp->next = NULL; list = node; Ht_item* it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; } void free_linkedlist(LinkedList* list) { LinkedList* temp = list; while (list) { temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); } }이제 이러한 오버플로 버킷 목록을
HashTable에 추가합니다. 모든 항목에는 체인이 있으므로 전체 테이블은LinkedList포인터의 배열입니다.typedef struct HashTable HashTable; // Defines the HashTable. struct HashTable { // Contains an array of pointers to items. Ht_item** items; LinkedList** overflow_buckets; int size; int count; };이제
overflow_buckets가 정의되었으므로 생성 및 삭제 기능을 추가합니다. 또한create_table()및free_table()함수에서 이를 설명해야 합니다.LinkedList** create_overflow_buckets(HashTable* table) { // Create the overflow buckets; an array of LinkedLists. LinkedList** buckets = (LinkedList**) calloc(table->size, sizeof(LinkedList*)); for (int i = 0; i < table->size; i++) buckets[i] = NULL; return buckets; } void free_overflow_buckets(HashTable* table) { // Free all the overflow bucket lists. LinkedList** buckets = table->overflow_buckets; for (int i = 0; i < table->size; i++) free_linkedlist(buckets[i]); free(buckets); } HashTable* create_table(int size) { // Creates a new HashTable. HashTable* table = (HashTable*) malloc(sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item**) calloc(table->size, sizeof(Ht_item*)); for (int i = 0; i < table->size; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; } void free_table(HashTable* table) { // Frees the table. for (int i = 0; i < table->size; i++) { Ht_item* item = table->items[i]; if (item != NULL) free_item(item); } // Free the overflow bucket lists and its items. free_overflow_buckets(table); free(table->items); free(table); }항목에 대한 오버플로 버킷 목록이 없으면 목록을 만들고 항목을 추가합니다.
삽입을 위해
handle_collision()업데이트:void handle_collision(HashTable* table, unsigned long index, Ht_item* item) { LinkedList* head = table->overflow_buckets[index]; if (head == NULL) { // Creates the list. head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; } else { // Insert to the list. table->overflow_buckets[index] = linkedlist_insert(head, item); return; } }그리고 전화:
void ht_insert(HashTable* table, char* key, char* value) { ... if (current_item == NULL) { ... } else { // Scenario 1: Update the value. if (strcmp(current_item->key, key) == 0) { ... } else { // Scenario 2: Handle the collision. handle_collision(table, index, item); return; } } }이제 오버플로 버킷을 사용하도록 검색 방법을 업데이트합니다.
char* ht_search(HashTable* table, char* key) { // Searches for the key in the HashTable. // Returns NULL if it doesn't exist. int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; // Provide only non-NULL values. if (item != NULL) { if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; } return NULL; }마지막으로 충돌은 이제
insert()및search()에서 처리됩니다!해시 테이블에서 삭제
이제 마지막으로 삭제 기능을 살펴보겠습니다.
void ht_delete(HashTable* table, char* key) { ... }다시 말하지만 방법은 삽입과 유사합니다.
- 해시 인덱스를 계산하고 항목을 가져옵니다.
NULL이면 아무것도 하지 마십시오.- 그렇지 않으면 키를 비교한 후 해당 인덱스에 대한 충돌 체인이 없으면 테이블에서 항목을 제거합니다.
- 충돌 체인이 존재하는 경우 해당 요소를 제거하고 그에 따라 링크를 이동합니다.
void ht_delete(HashTable* table, char* key) { // Deletes an item from the table. int index = hash_function(key); Ht_item* item = table->items[index]; LinkedList* head = table->overflow_buckets[index]; if (item == NULL) { // Does not exist. return; } else { if (head == NULL && strcmp(item->key, key) == 0) { // Collision chain does not exist. // Remove the item. // Set table index to NULL. table->items[index] = NULL; free_item(item); table->count--; return; } else if (head != NULL) { // Collision chain exists. if (strcmp(item->key, key) == 0) { // Remove this item. // Set the head of the list as the new item. free_item(item); LinkedList* node = head; head = head->next; node->next = NULL; table->items[index] = create_item(node->item->key, node->item->value); free_linkedlist(node); table->overflow_buckets[index] = head; return; } LinkedList* curr = head; LinkedList* prev = NULL; while (curr) { if (strcmp(curr->item->key, key) == 0) { if (prev == NULL) { // First element of the chain. // Remove the chain. free_linkedlist(head); table->overflow_buckets[index] = NULL; return; } else { // This is somewhere in the chain. prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; } } curr = curr->next; prev = curr; } } } }#include <stdio.h> #include <stdlib.h> #include <string.h> #define CAPACITY 50000 // Size of the HashTable. unsigned long hash_function(char *str) { unsigned long i = 0; for (int j = 0; str[j]; j++) i += str[j]; return i % CAPACITY; } // Defines the HashTable item. typedef struct Ht_item { char *key; char *value; } Ht_item; // Defines the LinkedList. typedef struct LinkedList { Ht_item *item; LinkedList *next; } LinkedList; // Defines the HashTable. typedef struct HashTable { // Contains an array of pointers to items. Ht_item **items; LinkedList **overflow_buckets; int size; int count; } HashTable; LinkedList *allocate_list() { // Allocates memory for a LinkedList pointer. LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList)); return list; } LinkedList *linkedlist_insert(LinkedList *list, Ht_item *item) { // Inserts the item onto the LinkedList. if (!list) { LinkedList *head = allocate_list(); head->item = item; head->next = NULL; list = head; return list; } else if (list->next == NULL) { LinkedList *node = allocate_list(); node->item = item; node->next = NULL; list->next = node; return list; } LinkedList *temp = list; while (temp->next->next) { temp = temp->next; } LinkedList *node = allocate_list(); node->item = item; node->next = NULL; temp->next = node; return list; } Ht_item *linkedlist_remove(LinkedList *list) { // Removes the head from the LinkedList. // Returns the item of the popped element. if (!list) return NULL; if (!list->next) return NULL; LinkedList *node = list->next; LinkedList *temp = list; temp->next = NULL; list = node; Ht_item *it = NULL; memcpy(temp->item, it, sizeof(Ht_item)); free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); return it; } void free_linkedlist(LinkedList *list) { LinkedList *temp = list; while (list) { temp = list; list = list->next; free(temp->item->key); free(temp->item->value); free(temp->item); free(temp); } } LinkedList **create_overflow_buckets(HashTable *table) { // Create the overflow buckets; an array of LinkedLists. LinkedList **buckets = (LinkedList **)calloc(table->size, sizeof(LinkedList *)); for (int i = 0; i < table->size; i++) buckets[i] = NULL; return buckets; } void free_overflow_buckets(HashTable *table) { // Free all the overflow bucket lists. LinkedList **buckets = table->overflow_buckets; for (int i = 0; i < table->size; i++) free_linkedlist(buckets[i]); free(buckets); } Ht_item *create_item(char *key, char *value) { // Creates a pointer to a new HashTable item. Ht_item *item = (Ht_item *)malloc(sizeof(Ht_item)); item->key = (char *)malloc(strlen(key) + 1); item->value = (char *)malloc(strlen(value) + 1); strcpy(item->key, key); strcpy(item->value, value); return item; } HashTable *create_table(int size) { // Creates a new HashTable. HashTable *table = (HashTable *)malloc(sizeof(HashTable)); table->size = size; table->count = 0; table->items = (Ht_item **)calloc(table->size, sizeof(Ht_item *)); for (int i = 0; i < table->size; i++) table->items[i] = NULL; table->overflow_buckets = create_overflow_buckets(table); return table; } void free_item(Ht_item *item) { // Frees an item. free(item->key); free(item->value); free(item); } void free_table(HashTable *table) { // Frees the table. for (int i = 0; i < table->size; i++) { Ht_item *item = table->items[i]; if (item != NULL) free_item(item); } // Free the overflow bucket lists and its items. free_overflow_buckets(table); free(table->items); free(table); } void handle_collision(HashTable *table, unsigned long index, Ht_item *item) { LinkedList *head = table->overflow_buckets[index]; if (head == NULL) { // Creates the list. head = allocate_list(); head->item = item; table->overflow_buckets[index] = head; return; } else { // Insert to the list. table->overflow_buckets[index] = linkedlist_insert(head, item); return; } } void ht_insert(HashTable *table, char *key, char *value) { // Creates the item. Ht_item *item = create_item(key, value); // Computes the index. int index = hash_function(key); Ht_item *current_item = table->items[index]; if (current_item == NULL) { // Key does not exist. if (table->count == table->size) { // HashTable is full. printf("Insert Error: Hash Table is full\n"); free_item(item); return; } // Insert directly. table->items[index] = item; table->count++; } else { // Scenario 1: Update the value. if (strcmp(current_item->key, key) == 0) { strcpy(table->items[index]->value, value); return; } else { // Scenario 2: Handle the collision. handle_collision(table, index, item); return; } } } char *ht_search(HashTable *table, char *key) { // Searches for the key in the HashTable. // Returns NULL if it doesn't exist. int index = hash_function(key); Ht_item *item = table->items[index]; LinkedList *head = table->overflow_buckets[index]; // Provide only non-NULL values. if (item != NULL) { if (strcmp(item->key, key) == 0) return item->value; if (head == NULL) return NULL; item = head->item; head = head->next; } return NULL; } void ht_delete(HashTable *table, char *key) { // Deletes an item from the table. int index = hash_function(key); Ht_item *item = table->items[index]; LinkedList *head = table->overflow_buckets[index]; if (item == NULL) { // Does not exist. return; } else { if (head == NULL && strcmp(item->key, key) == 0) { // Collision chain does not exist. // Remove the item. // Set table index to NULL. table->items[index] = NULL; free_item(item); table->count--; return; } else if (head != NULL) { // Collision chain exists. if (strcmp(item->key, key) == 0) { // Remove this item. // Set the head of the list as the new item. free_item(item); LinkedList *node = head; head = head->next; node->next = NULL; table->items[index] = create_item(node->item->key, node->item->value); free_linkedlist(node); table->overflow_buckets[index] = head; return; } LinkedList *curr = head; LinkedList *prev = NULL; while (curr) { if (strcmp(curr->item->key, key) == 0) { if (prev == NULL) { // First element of the chain. // Remove the chain. free_linkedlist(head); table->overflow_buckets[index] = NULL; return; } else { // This is somewhere in the chain. prev->next = curr->next; curr->next = NULL; free_linkedlist(curr); table->overflow_buckets[index] = head; return; } } curr = curr->next; prev = curr; } } } } void print_search(HashTable *table, char *key) { char *val; if ((val = ht_search(table, key)) == NULL) { printf("Key:%s does not exist\n", key); return; } else { printf("Key:%s, Value:%s\n", key, val); } } void print_table(HashTable *table) { printf("\nHash Table\n-------------------\n"); for (int i = 0; i < table -> size; i++) { if (table -> items[i]) { printf("Index:%d, Key:%s, Value:%s\n", i, table -> items[i] -> key, table -> items[i] -> value); } } printf("-------------------\n\n"); } int main() { HashTable *ht = create_table(CAPACITY); ht_insert(ht, (char *)"1", (char *)"First address"); ht_insert(ht, (char *)"2", (char *)"Second address"); ht_insert(ht, (char *)"Hel", (char *)"Third address"); ht_insert(ht, (char *)"Cau", (char *)"Fourth address"); print_search(ht, (char *)"1"); print_search(ht, (char *)"2"); print_search(ht, (char *)"3"); print_search(ht, (char *)"Hel"); print_search(ht, (char *)"Cau"); // Collision! print_table(ht); ht_delete(ht, (char *)"1"); ht_delete(ht, (char *)"Cau"); print_table(ht); free_table(ht); return 0; }이 코드는 다음 출력을 생성합니다.
OutputKey:1, Value:First address Key:2, Value:Second address Key:3 does not exist Key:Hel, Value:Third address Key:Cau does not exist Hash Table ------------------- Index:49, Key:1, Value:First address Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address ------------------- Hash Table ------------------- Index:50, Key:2, Value:Second address Index:281, Key:Hel, Value:Third address -------------------ht_insert(),ht_search()및ht_delete는 예상대로 작동합니다.결론
이 기사에서는 C/C++에서 처음부터 해시 테이블을 구현했습니다.
다른 충돌 처리 알고리즘과 다른 해시 함수를 실험해 보십시오. 더 많은 C++ 자습서로 학습을 계속하십시오.
- 사용하지 않는 경우