C を用いたハッシュテーブルによる Set データ構造の実装

この記事では、ハッシュテーブルを用いて Set データ構造を C で実装する方法を示し、複雑性、トレードオフ、および改善の可能性について議論します。プログラミングの基礎知識（論理など）、C 構文、変数の割り当て、C におけるメモリ管理（ポインタ、malloc、free）、ハッシャーの基本的な理解が必要です。ユニークな要素を格納するデータ構造です。集合理論におけるアイデアと同一です：重複した値は許可されません。Set を実装するにはハッシュテーブルが適しています：挿入、検索、削除 -> O(1) 平均場合。衝突が発生する可能性があるため、それらを処理する戦略が必要になります。この実装では、バケットごとに連結リストを使用して衝突を処理しています。ハッシュされるインデックスが同じ複数の要素は同じリストに保存されます。変数定義: m = バケットの数、k = 1 つのバケット内の要素数、n = 総要素数。最悪の場合：挿入 O(k)、検索 O(k)、削除 O(k)、iterate O(m + n)、isEmpty O(1)。平均の場合：挿入 O(1)、検索 O(1)、削除 O(1)、iterate O(m + n) -> O(n)（m が定数の場合）、isEmpty O(1)。ロードファクターの処理は行っておりません。再ハッシュ化によってロードファクターを処理していません。ここでは Set 自体に焦点を当てています。これは n が大きくなる限りパフォーマンスを低下させる可能性があります。改善策：動的サイズ変更（拡大/縮小）。ハッシュテーブルとバランスト・バイナリ・サーチ・ツリー（BST）の比較：ハッシュテーブルは一般的に非順序の Set に適しており、一定時間の平均パフォーマンスを提供し、順序を維持しないためです。バランスト・BST は、平均パフォーマンスよりも最悪ケースの保証やソート順が重要である場合にのみ適しているためです。Set は非順序のデータ構造であるため、ハッシュテーブルの使用が好まれます。時間複雑性の比較（挿入、検索、削除）：ハッシュテーブル：平均場合 O(1)、最悪場合 O(n)。バランスト・BST：平均場合 O(log n)、最悪場合 O(log n)。ロードファクターの処理とダブルハッシャーを用いたオープンアドレッシングによるハッシュテーブル成長をチェックするには：https://github.com/godinhojoao/dsa-studies/blob/main/dsa-in-c/hashtable.c。C における Set の開発手法：このコードでは、固定サイズのハッシュテーブルが使用され、衝突はチェーン（連結リスト）で処理されます。FNV-1a がハッシュ関数として使用されています。 コード例: ```c #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define SET_LIMIT_SIZE 1000 typedef struct SetNode { struct SetNode* next; int value; } SetNode; typedef struct Set { SetNode** nodes; int currLength; } Set; // 32-bit FNV-1a unsigned int fnv1a_int(int value) { unsigned int hash = 2166136261u; unsigned char* p = (unsigned char*)&value; for(int i = 0; i < (int)sizeof(int); i++) { hash ^= (unsigned int)p[i]; hash *= 16777619u; } return hash; } int itemIndex(int value, int arrLimit) { unsigned int hash = fnv1a_int(value); return hash % arrLimit; } Set* initializeSet() { Set* set = malloc(sizeof(Set)); set->currLength = 0; set->nodes = malloc(sizeof(SetNode*) * SET_LIMIT_SIZE); for(int i = 0; i < SET_LIMIT_SIZE; i++) { set->nodes[i] = NULL; } return set; } SetNode* createNode(int value) { SetNode* newNode = malloc(sizeof(SetNode)); newNode->next = NULL; newNode->value = value; return newNode; } void insert(Set* set, int value) { int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currentNode = set->nodes[index]; SetNode* prevNode = NULL; while(currentNode != NULL) { if(currentNode->value == value) { printf("set do not allow repeated values: %d\n", value); return; } prevNode = currentNode; currentNode = currentNode->next; } SetNode* newNode = createNode(value); set->currLength += 1; if(prevNode == NULL) { set->nodes[index] = newNode; } else { prevNode->next = newNode; } } int isEmpty(Set* set) { return set->currLength == 0; } SetNode* find(Set* set, int value) { if(isEmpty(set)) return NULL; int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currNode = set->nodes[index]; while(currNode != NULL && currNode->value != value) { currNode = currNode->next; } return currNode; } int removeItem(Set* set, int value) { if(isEmpty(set)) return -1; int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currentNodeToDelete = set->nodes[index]; SetNode* prevNode = NULL; while(currentNodeToDelete != NULL && currentNodeToDelete->value != value) { prevNode = currentNodeToDelete; currentNodeToDelete = currentNodeToDelete->next; } if(currentNodeToDelete == NULL) { return -1; // Not found } if(prevNode == NULL) { set->nodes[index] = currentNodeToDelete->next; } else { prevNode->next = currentNodeToDelete->next; } free(currentNodeToDelete); set->currLength--; return 0; } ```

In this article I will show how to implement a Set data structure in C using a hashtable, and discuss complexity, trade-offs, and possible improvements. Basic knowledge of programming (logic, etc); C syntax, allocating variables; Memory management in C: pointers, malloc, free; Basic understanding of hashing; A data structure that stores unique elements. Same idea as in set theory in mathematics: no repeated values are allowed. A hashtable is a good choice for implementing a Set: insert, find, remove -> O(1) average Collisions can happen, so we need a strategy to handle them. In this implementation, collisions are handled using a linked list per bucket. Multiple elements that hash to the same index are stored in the same list. Let: m = number of buckets k = elements in one bucket n = total elements Worst case: insert O(k) find O(k) remove O(k) iterate O(m + n) isEmpty O(1) Average case: insert O(1) find O(1) remove O(1) iterate O(m + n) -> O(n) if m is constant isEmpty O(1) Load factor not handled: I haven't handled load factor by rehashing since the focus is the Set itself. This can degrade performance as n grows. Improvement: dynamic resizing (grow/shrink). Hashtable vs Balanced Binary Search Tree (BST): A hashtable is generally better for unordered sets, because it provides constant-time average performance and does not maintain order. A balanced BST is preferable only when worst-case guarantees or sorted order are more important than average performance. A set is an unordered data structure, so using a hashtable is preferable. Time complexity comparison (insert, find, remove): Hashtable: Average case: O(1) Worst case: O(n) Balanced BST: Average case: O(log n) Worst case: O(log n) To check load factor handling and hashtable growth using open addressing with double hashing: https://github.com/godinhojoao/dsa-studies/blob/main/dsa-in-c/hashtable.c How to Develop a Set in C In this code: A hashtable with fixed size is used Collisions are handled with linked lists (chaining) FNV-1a is used as the hash function #include #include #include #define SET_LIMIT_SIZE 1000 typedef struct SetNode { struct SetNode* next; int value; } SetNode; typedef struct Set { SetNode** nodes; int currLength; } Set; // 32-bit FNV-1a unsigned int fnv1a_int(int value) { unsigned int hash = 2166136261u; unsigned char* p = (unsigned char*)&value; for(int i = 0; i < (int)sizeof(int); i++) { hash ^= (unsigned int)p[i]; hash *= 16777619u; } return hash; } int itemIndex(int value, int arrLimit) { unsigned int hash = fnv1a_int(value); return hash % arrLimit; } Set* initializeSet() { Set* set = malloc(sizeof(Set)); set->currLength = 0; set->nodes = malloc(sizeof(SetNode*) * SET_LIMIT_SIZE); for(int i = 0; i < SET_LIMIT_SIZE; i++) { set->nodes[i] = NULL; } return set; } SetNode* createNode(int value) { SetNode* newNode = malloc(sizeof(SetNode)); newNode->next = NULL; newNode->value = value; return newNode; } void insert(Set* set, int value) { int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currentNode = set->nodes[index]; SetNode* prevNode = NULL; while(currentNode != NULL) { if(currentNode->value == value) { printf("set do not allow repeated values: %d\n", value); return; } prevNode = currentNode; currentNode = currentNode->next; } SetNode* newNode = createNode(value); set->currLength += 1; if(prevNode == NULL) { set->nodes[index] = newNode; } else { prevNode->next = newNode; } } int isEmpty(Set* set) { return set->currLength == 0; } SetNode* find(Set* set, int value) { if(isEmpty(set)) return NULL; int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currNode = set->nodes[index]; while(currNode != NULL && currNode->value != value) { currNode = currNode->next; } return currNode; } int removeItem(Set* set, int value) { if(isEmpty(set)) return -1; int index = itemIndex(value, SET_LIMIT_SIZE); SetNode* currentNodeToDelete = set->nodes[index]; SetNode* prevNode = NULL; while(currentNodeToDelete != NULL && currentNodeToDelete->value != value) { prevNode = currentNodeToDelete; currentNodeToDelete = currentNodeToDelete->next; } if(currentNodeToDelete == NULL) return -1; if(prevNode != NULL) { prevNode->next = currentNodeToDelete->next; } else { set->nodes[index] = currentNodeToDelete->next; } free(currentNodeToDelete); set->currLength -= 1; return 1; } int main() { Set* set = initializeSet(); printf("== insert 10, 20, 30, 10 ==\n"); insert(set, 10); insert(set, 20); insert(set, 30); insert(set, 10); // duplicate test printf("== find ==\n"); printf("find 10: %s\n", find(set, 10) ? "found" : "not found"); printf("find 99: %s\n", find(set, 99) ? "found" : "not found"); printf("== remove ==\n"); printf("remove 99: %d\n", removeItem(set, 99)); printf("remove 20: %d\n", removeItem(set, 20)); printf("remove 10: %d\n", removeItem(set, 10)); printf("remove 10 again: %d\n", removeItem(set, 10)); printf("== final finds ==\n"); printf("find 10: %s\n", find(set, 10) ? "found" : "not found"); printf("find 20: %s\n", find(set, 20) ? "found" : "not found"); printf("find 30: %s\n", find(set, 30) ? "found" : "not found"); return 0; } Stanford CS106B Lecture 6: Unordered Data Structures (Sets and Maps) https://github.com/godinhojoao/dsa-studies/blob/main/dsa-in-c/set.c https://github.com/godinhojoao/dsa-studies/blob/main/dsa-in-c/hashtable.c