C/C++でサンプルハッシュテーブルを実装する方法
はじめに
C/C++におけるハッシュテーブルは、キーを値にマッピングするデータ構造です。ハッシュテーブルは、ハッシュ関数を使用してキーのインデックスを計算します。ハッシュテーブルのインデックスに基づいて、適切な場所に値を格納することができます。
ハッシュテーブルを使用する利点は、非常に高速なアクセス時間です。通常、時間の複雑性（償却時間の複雑性）は一定のO(1)アクセス時間です。
異なる二つのキーが同じインデックスになる場合、これらの衝突を考慮するために他のデータ構造（バケツ）を使用する必要があります。非常に優れたハッシュ関数を選択すると、衝突の可能性は無視できる程度になります。
C++のSTL（標準テンプレートライブラリ）には、std::unordered_map()というデータ構造があります。
この記事では、ゼロからハッシュテーブルを構築する方法について紹介します。
- A hash function to map keys to values.
- A hash table data structure that supports insert, search, and delete operations.
- A data structure to account for a collision of keys.
ハッシュ関数の選択
最初のステップは、衝突の可能性が低いかなり良いハッシュ関数を選択することです。ただし、このチュートリアルの目的のために、ハッシュの衝突をよりわかりやすくするために、低品質なハッシュ関数を使用します。この限定された例では、文字列（またはCの文字配列）のみを使用します。
ハッシュテーブル.cpp
#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値を持つため、衝突が起こります。
このコードは、ハッシュテーブルの容量の範囲内で数値を返さなければなりません。そうでない場合、未割り当てのメモリ領域にアクセスしてエラーが発生する可能性があります。
ハッシュテーブルデータ構造を定義する
ハッシュテーブルは、{キー: 値}のペアで構成されるアイテムの配列です。
まず、アイテムの構造を定義してください。 (Mazu, aitemu no kōzō o teigi shite kudasai.)
HashTable.cppを日本語で言い換えてください。
// Defines the HashTable item.
typedef struct Ht_item
{
char* key;
char* value;
} Ht_item;
現在、ハッシュテーブルにはHt_itemを指すポインターの配列があり、それはダブルポインターです。
HashTable.cppを日本語で述べると、
// Defines the HashTable.
typedef struct HashTable
{
// Contains an array of pointers to items.
Ht_item** items;
int size;
int count;
} HashTable;
ハッシュテーブルは、要素の数をカウントし、ハッシュテーブルのサイズをサイズを使って返す必要があります。
ハッシュテーブルとハッシュテーブルのアイテムを作成する。 (Hashutēburu to hashutēburu no aitemu o sakusei suru)
次に、メモリを割り当てるための関数と、アイテムを作成するための関数を作成してください。
キーと値のためにメモリを割り当てて、アイテムへのポインタを返すことでアイテムを作成します。
HashTable.cppの内容を日本語で言い換えると、おそらく以下のようになります：
「HashTable.cppは、ハッシュテーブルを実装するためのC++のファイルです。」
「HashTable.cppは、ハッシュテーブルを実装するためのC++のファイルです。」
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.cpp
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()でヒープ上に割り当てたメモリを解放してください。
テーブルのアイテムと全体を解放する機能を作成してください。
ハッシュテーブル.cpp
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() を追加してください。
ハッシュテーブル.cpp
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");
}
これで、カスタムハッシュテーブルの基本的な機能の説明は終わりです。次に、挿入、検索、削除の関数を記述します。
ハッシュテーブルに挿入する (Hasshu te-buru ni sounyuu suru)
関数ht_insert()を作成して、挿入を行う。
関数はHashTableポインタ、キー、値を引数に受け取ります。
void ht_insert(HashTable* table, char* key, char* value)
{
...
}
今、ht_insert()関数には特定の手順が含まれています。
- Create the item based on the { key: value } pair.
- Compute the index based on the hash function.
- Check if the index is already occupied or not, by comparing the key.If it is not occupied, you can directly insert it into index.
Otherwise, it is a collision, and you will need to handle it.
このチュートリアルでは、初期モデルが作成された後の衝突処理について説明します。
最初に、アイテムを作成してください。
create_item(key, value)
その後、指標を計算してください。
int index = hash_function(key);
最初にキーを挿入するとき、アイテムは NULL でなければなりません。
HashTable.cppを日本語で言い換えると
// 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++;
}
同じアイテムがハッシュテーブルに挿入されているため、{キー: 値}のペアが既に存在する場合を考えましょう。この場合、コードはアイテムの値を新しい値に更新する必要があります。
ハッシュテーブル.cpp
if (current_item == NULL)
{
...
}
else {
// Scenario 1: Update the value.
if (strcmp(current_item->key, key) == 0)
{
strcpy(table->items[index] -> value, value);
return;
}
}
衝突処理が必要なシナリオを考えてみましょう。それに対処するため、プレースホルダが追加されました。
ハッシュテーブル.cpp
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ポインターとキーをパラメーターとして受け取ります。
char* ht_search(HashTable* table, char* key)
{
...
}
ハッシュテーブル内でキーを使ってアイテムを探します。もしハッシュテーブル内でアイテムが見つからなかった場合、NULLが返されます。
HashTable.cppを日本語で自然に言い換えると、以下のようになります：
ハッシュテーブルのcppファイル
ハッシュテーブルのcppファイル
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;
}
キーに一致するアイテムを表示するために、print_search()を追加してください。
HashTable.cppの意味
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)となります。この方法の利点は、ハッシュテーブルの容量が低い場合に適しているということです。
オーバーフローバケットリストを実装してください。
ハッシュテーブル.cpp
// 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);
}
}
これらのオーバーフローバケットリストをハッシュテーブルに追加してください。各アイテムにはチェインがあり、全体のテーブルはLinkedListポインターの配列です。
ハッシュテーブル.cpp
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;
};
オーバーフローバケットが定義されたので、作成と削除のための関数を追加してください。また、create_table()とfree_table()の関数でもそれらを考慮する必要があります。
HashTable.cppを日本語で言い換えると、以下のようになります。
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()を更新してください。
ハッシュテーブルの実装ファイル HashTable.cpp
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;
}
}
そして、呼びかけ：
HashTable.cppを日本語で言い換えると、以下のようになります：「ハッシュテーブルの.cppファイル」
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;
}
}
}
今、検索方法をオーバーフローバケットを使用するように更新してください。
ハッシュテーブル.cpp
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()で衝突が処理されます！
ハッシュテーブルから削除する (Hashi tēburu kara sakujo suru)
では最後に、削除機能について見てみましょう。
void ht_delete(HashTable* table, char* key)
{
...
}
また、その方法は挿入と似ています。
-
- ハッシュインデックスを計算し、アイテムを取得します。
-
- もしNULLであれば、何もしません。
-
- それ以外の場合、キーを比較した後、そのインデックスに対して衝突チェーンが存在しない場合は、テーブルからアイテムを削除します。
- 衝突チェーンが存在する場合は、その要素を削除し、リンクを適切にシフトします。
ハッシュテーブル.cpp
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;
}
このコードは次の出力を生成します。
Output
Key: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++のチュートリアルを使ってさらに学習を続けましょう。