悩んでいる人
C言語でハッシュテーブルを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
ハッシュテーブル（ハッシュ表）
ハッシュテーブル（ハッシュ表）とは，キー（key）と値（value）のペアでデータを管理し，キーに対応する値を高速に参照するためのデータ構造です．
ハッシュテーブルは連想配列や集合の効率的な実装の一つですので，よく利用されます．
ハッシュテーブルの平均計算量は\(\mathcal{O}(1)\)ですが，最悪計算量は\(\mathcal{O}(n)\)になります．
また，ハッシュテーブルは探索アルゴリズムの側面を持ちます．
代表的な探索アルゴリズムである線形探索と二分探索を知りたいあなたはこちらからどうぞ．
C++言語のSTLにはC++11規格からハッシュテーブルの実装としてstd::unordered_mapやstd::unordered_setが採用されました．
これに対して，C言語の標準ライブラリにはハッシュテーブルの実装がありません．
また，GNUのC言語ライブラリにはハッシュテーブルの管理関数（hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数）はありますが，使い方が少し難しいです．
ハッシュテーブルの管理関数の使い方を知りたいあなたはこちらからどうぞ．
本記事では，C言語でハッシュテーブルを深く理解するための自作コードを紹介します．
複数の異なるキーが同じハッシュ値（ハッシュ関数から計算した添字）になることを衝突（collision），同じハッシュ値となるキーを同族キー，ハッシュテーブルにある各々の値のことをバケットと呼びます．
ハッシュ値の衝突が発生した場合は，ハッシュチェイン法（オープンハッシュ法）とオープンアドレス法（クローズドハッシュ法）で主に対処するので，それぞれ解説していきます．
ハッシュチェイン法（オープンハッシュ法）
ハッシュチェイン法（オープンハッシュ法） は，ハッシュテーブルで衝突を起こしたキー同士をポインタでつなぐ連結リスト（linked list）で値を格納します．
ハッシュテーブルの各々の番地にはキーそのものではなく，同族キーを保持する連結リストを格納します．
連結リストを知りたいあなたはこちらからどうぞ．（番兵ノードありの実装です．）
ハッシュチェイン法を利用するコードは以下になります．（番兵ノードなしの実装です．）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NR_BUCKETS 5 struct bucket { char *key; char *val; struct bucket *next; }; void init_hash(struct bucket *table[NR_BUCKETS]) { int i; for (i = 0; i < NR_BUCKETS; i++) { table[i] = NULL; } } void clear_bucket(struct bucket *bucket) { if (bucket->key != NULL) { free(bucket->key); } if (bucket->val != NULL) { free(bucket->val); } free(bucket); } void clear_hash(struct bucket *table[NR_BUCKETS]) { int i; struct bucket *p, *q; for (i = 0; i < NR_BUCKETS; i++) { p = table[i]; while (p != NULL) { q = p->next; clear_bucket(p); p = q; } } init_hash(table); } int get_hash_val(char *key) { int hash_val = 0; while (*key) { hash_val += *key++; } return hash_val % NR_BUCKETS; } char *find_hash(struct bucket *table[NR_BUCKETS], char *key) { int hash_val = get_hash_val(key); struct bucket *p; for (p = table[hash_val]; p != NULL; p = p->next) { if (strcmp(key, p->key) == 0) { return p->val; } } return NULL; } int insert_hash(struct bucket *table[NR_BUCKETS], char *key, char *val) { struct bucket *p = NULL; int hash_val; if (find_hash(table, key) != NULL) { fprintf(stderr, "key[%s] already exists in hash table.\n", key); return 1; } if ((p = (struct bucket *) malloc(sizeof(struct bucket))) == NULL) { fprintf(stderr, "Error: cannot allocate memory %zu bytes.\n", sizeof(struct bucket)); exit(1); } if ((p->key = strdup(key)) == NULL) { fprintf(stderr, "Error: strdup()\n"); exit(2); } if ((p->val = strdup(val)) == NULL) { fprintf(stderr, "Error: strdup()\n"); exit(3); } hash_val = get_hash_val(key); p->next = table[hash_val]; table[hash_val] = p; return 0; } int erase_hash(struct bucket *table[NR_BUCKETS], char *key) { struct bucket *p, *q; int hash_val = get_hash_val(key); if ((p = table[hash_val]) == NULL) { fprintf(stderr, "Error: table[%s] does not exist in hash table.\n", key); return 1; } q = p->next; if (strcmp(key, p->key) == 0) { table[hash_val] = q; clear_bucket(p); return 0; } while (p != NULL) { if (strcmp(key, p->key) == 0) { q->next = p->next; clear_bucket(p); return 0; } q = p; p = p->next; } return 2; } void print_hash(struct bucket *table[NR_BUCKETS]) { struct bucket *chain = NULL; int i; for (i = 0; i < NR_BUCKETS; i++) { if (table[i] != NULL) { printf("table[%d]:{", i); for (chain = table[i]; chain != NULL; chain = chain->next) { printf("{%s:%s}->", chain->key, chain->val); } printf("NULL}\n"); } } } int main(void) { struct bucket *table[NR_BUCKETS]; char *key = "three"; init_hash(table); insert_hash(table, "one", "val1"); insert_hash(table, "two", "val2"); insert_hash(table, "three", "val3"); insert_hash(table, "twenty", "val20"); insert_hash(table, "seven", "val7"); insert_hash(table, "ten", "val10"); print_hash(table); printf("find key = %s, val = %s\n", key, find_hash(table, key)); erase_hash(table, key); print_hash(table); clear_hash(table); return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc hash_table_hash_chain.c $ a.out table[0]:{{seven:val7}->NULL} table[1]:{{three:val3}->{two:val2}->NULL} table[2]:{{ten:val10}->{one:val1}->NULL} table[3]:{{twenty:val20}->NULL} find key = three, val = val3 table[0]:{{seven:val7}->NULL} table[1]:{{two:val2}->NULL} table[2]:{{ten:val10}->{one:val1}->NULL} table[3]:{{twenty:val20}->NULL} |
オープンアドレス法（クローズドハッシュ法）
オープンアドレス法（クローズドハッシュ法）は，衝突が発生した場合，ハッシュテーブル中の空いている別の番地を探す方式です．
例えば，線形探索法（linear probing）では，次の添字（添字を+1した場所）の空いているキーの場所に値を格納します．
線形探索法でオープンアドレス法を利用するコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NR_BUCKETS 5 enum bucket_status { BUCKET_EMPTY, BUCKET_FULL, BUCKET_ERASE }; struct bucket { char *key; char *val; enum bucket_status stat; }; void init_hash(struct bucket table[NR_BUCKETS]) { int i; for (i = 0; i < NR_BUCKETS; i++) { table[i].stat = BUCKET_EMPTY; table[i].key = NULL; table[i].val = NULL; } } void clear_hash(struct bucket table[NR_BUCKETS]) { int i; for (i = 0; i < NR_BUCKETS; i++) { if (table[i].key != NULL) { free(table[i].key); } if (table[i].val != NULL) { free(table[i].val); } } } int get_hash_val(char *key) { int hash_val = 0; while (*key) { hash_val += *key++; } return hash_val % NR_BUCKETS; } int get_rehash_val(int hash_val) { return (hash_val + 1) % NR_BUCKETS; } char *find_hash(struct bucket table[NR_BUCKETS], char *key) { int i = 0; int hash_val = get_hash_val(key); while (table[hash_val].stat == BUCKET_FULL) { if (strcmp(table[hash_val].key, key) == 0 && table[hash_val].stat != BUCKET_ERASE) { return table[hash_val].val; } if (++i > NR_BUCKETS) { break; } hash_val = get_rehash_val(hash_val); } return NULL; } int insert_hash(struct bucket table[NR_BUCKETS], char *key, char *val) { int i = 0; int hash_val; if (find_hash(table, key) != NULL) { fprintf(stderr, "Error: key[%s] already exists in hash table.\n", key); return 1; } hash_val = get_hash_val(key); while (table[hash_val].stat == BUCKET_FULL) { if (++i > NR_BUCKETS) { fprintf(stderr, "Error: cannot insert key[%s] into hash table.\n", key); return 2; } hash_val = get_rehash_val(hash_val); } table[hash_val].stat = BUCKET_FULL; if ((table[hash_val].key = strdup(key)) == NULL) { fprintf(stderr, "Error: strdup()\n"); exit(1); } if ((table[hash_val].val = strdup(val)) == NULL) { fprintf(stderr, "Error: strdup()\n"); exit(2); } return 0; } int erase_hash(struct bucket table[NR_BUCKETS], char *key) { int i = 0; int hash_val = get_hash_val(key); while (table[hash_val].stat != BUCKET_EMPTY) { if (strcmp(table[hash_val].key, key) == 0 && table[hash_val].stat != BUCKET_ERASE) { table[hash_val].stat = BUCKET_ERASE; free(table[hash_val].key); table[hash_val].key = NULL; free(table[hash_val].val); table[hash_val].val = NULL; return 0; } if (++i > NR_BUCKETS) { break; } hash_val = get_rehash_val(hash_val); } fprintf(stderr, "key[%s] is not found.\n", key); return 1; } void print_hash(struct bucket table[NR_BUCKETS]) { int i; for (i = 0; i < NR_BUCKETS; i++) { if (table[i].stat == BUCKET_FULL) { printf("table[%d]:", i); printf("{%s:%s}\n", table[i].key, table[i].val); } else if (table[i].stat == BUCKET_ERASE) { printf("table[%d]: erase\n", i); } else { printf("table[%d]: empty\n", i); } } } int main(void) { struct bucket table[NR_BUCKETS]; char *key = "three"; char *key2 = "nine"; init_hash(table); insert_hash(table, "one", "val1"); insert_hash(table, "nine", "val9"); insert_hash(table, "three", "val3"); print_hash(table); printf("find key = %s, val = %s\n", key, find_hash(table, key)); erase_hash(table, key); erase_hash(table, key2); print_hash(table); insert_hash(table, key2, "val9(2nd)"); insert_hash(table, key, "val3(2nd)"); print_hash(table); clear_hash(table); return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
$ gcc hash_table_open_addressing.c $ a.out table[0]: empty table[1]:{nine:val9} table[2]:{one:val1} table[3]:{three:val3} table[4]: empty find key = three, val = val3 table[0]: empty table[1]: erase table[2]:{one:val1} table[3]: erase table[4]: empty table[0]: empty table[1]:{nine:val9(2nd)} table[2]:{one:val1} table[3]:{three:val3(2nd)} table[4]: empty |
まとめ
C言語でハッシュテーブルを紹介しました．
ハッシュ値の衝突が発生した場合は，ハッシュチェイン法とオープンアドレス法で対処することがわかりました．
ハッシュテーブルの応用のマークル木とマークルパトリシア木を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
