
C言語でハッシュテーブルを教えて!
こういった悩みにお答えします.
本記事の信頼性
- リアルタイムシステムの研究歴12年.
- 東大教員の時に,英語でOSの授業.
- 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部(2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
- プログラミング歴15年以上,習得している言語: C/C++,Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
- 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開.
こういった私から学べます.
ハッシュテーブル(ハッシュ表)
ハッシュテーブル(ハッシュ表)とは,キー(key)と値(value)のペアでデータを管理し,キーに対応する値を高速に参照するためのデータ構造です.
ハッシュテーブルは連想配列や集合の効率的な実装の一つですので,よく利用されます.
ハッシュテーブルの平均計算量は\(\mathcal{O}(1)\)ですが,最悪計算量は\(\mathcal{O}(n)\)になります.
また,ハッシュテーブルは探索アルゴリズムの側面を持ちます.
代表的な探索アルゴリズムである線形探索と二分探索を知りたいあなたはこちらからどうぞ.
-
-
【C言語】線形探索と二分探索で数値と文字列の検索【lfind/lsearch/bsearch関数と自作関数】
こういった悩みにお答えします. こういった私から学べます. 目次1 線形探索と二分探索2 線形探索と二分探索の標準ライブラリ関数2.1 lfind/lsearch関数2.2 bsearch関数3 線形 ...
続きを見る
C++言語のSTLにはC++11規格からハッシュテーブルの実装としてstd::unordered_mapやstd::unordered_setが採用されました.
これに対して,C言語の標準ライブラリにはハッシュテーブルの実装がありません.
また,GNUのC言語ライブラリにはハッシュテーブルの管理関数(hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数)はありますが,使い方が少し難しいです.
ハッシュテーブルの管理関数の使い方を知りたいあなたはこちらからどうぞ.
-
-
【C言語】ハッシュテーブルの管理関数の使い方【hcreate/hsearch/hdestroy/hcreate_r/hsearch_r/hdestroy_r関数】
こういった悩みにお答えします. こういった私から学べます. 目次1 ハッシュテーブルの管理関数2 ハッシュテーブルの管理関数の使い方2.1 hcreate/hsearch/hdestroy関数の使い方 ...
続きを見る
本記事では,C言語でハッシュテーブルを深く理解するための自作コードを紹介します.
複数の異なるキーが同じハッシュ値(ハッシュ関数から計算した添字)になることを衝突(collision),同じハッシュ値となるキーを同族キー,ハッシュテーブルにある各々の値のことをバケットと呼びます.
ハッシュ値の衝突が発生した場合は,ハッシュチェイン法(オープンハッシュ法)とオープンアドレス法(クローズドハッシュ法)で主に対処するので,それぞれ解説していきます.
ハッシュチェイン法(オープンハッシュ法)
ハッシュチェイン法(オープンハッシュ法) は,ハッシュテーブルで衝突を起こしたキー同士をポインタでつなぐ連結リスト(linked list)で値を格納します.
ハッシュテーブルの各々の番地にはキーそのものではなく,同族キーを保持する連結リストを格納します.
連結リストを知りたいあなたはこちらからどうぞ.(番兵ノードありの実装です.)
-
-
【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】
こういった悩みにお答えします. こういった私から学べます. 目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例:Linuxカーネル3. ...
続きを見る
ハッシュチェイン法を利用するコードは以下になります.(番兵ノードなしの実装です.)
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言語】マークル木とマークルパトリシア木【ビットコインとイーサリアムで利用】
こういった悩みにお答えします. こういった私から学べます. 本記事では,ハッシュテーブルを理解していることを前提とします. 目次1 マークル木(マークルハッシュ木,ハッシュ木)【ビットコインで利用】2 ...
続きを見る
C言語を独学で習得することは難しいです.
私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.
私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!
独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!