【C言語】ハッシュテーブルとは【ハッシュチェイン法，オープンアドレス法】

悩んでいる人

C言語でハッシュテーブルを教えて！

こういった悩みにお答えします．

本記事の信頼性

リアルタイムシステムの研究歴12年．
東大教員の時に，英語でOSの授業．
2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部（2021年の世界大学学術ランキングで20位）で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
プログラミング歴15年以上，習得している言語: C/C++，Solidity，Java，Python，Ruby，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．

こういった私から学べます．

1 ハッシュテーブル（ハッシュ表）
2 ハッシュチェイン法（オープンハッシュ法）
3 オープンアドレス法（クローズドハッシュ法）
4 まとめ

ハッシュテーブル（ハッシュ表）

ハッシュテーブル（ハッシュ表）とは，キー（key）と値（value）のペアでデータを管理し，キーに対応する値を高速に参照するためのデータ構造です．

ハッシュテーブルは連想配列や集合の効率的な実装の一つですので，よく利用されます．

C++言語のSTLにはC++11規格からハッシュテーブルの実装としてstd::unordered_mapやstd::unordered_setが採用されました．

しかし，C言語の標準ライブラリにはハッシュテーブルの実装はありませんので，自作コードを紹介します．

複数の異なるキーが同じハッシュ値（ハッシュ関数から計算した添字）になることを衝突（collision），同じハッシュ値となるキーを同族キー，ハッシュテーブルにある各々の値のことをバケットと呼びます．

ハッシュ値の衝突が発生した場合は，ハッシュチェイン法（オープンハッシュ法）とオープンアドレス法（クローズドハッシュ法）で主に対処するので，それぞれ解説していきます．

ハッシュチェイン法（オープンハッシュ法）

ハッシュチェイン法（オープンハッシュ法）は，ハッシュテーブルで衝突を起こしたキー同士をポインタでつなぐ連結リスト（linked list）で値を格納します．

ハッシュテーブルの各々の番地にはキーそのものではなく，同族キーを保持する連結リストを格納します．

連結リストを知りたいあなたはこちらからどうぞ．（番兵ノードありの実装です．）

: 【C言語】連結リストとは【片方向リスト，双方向リスト，双方向循環リスト】

こういった悩みにお答えします．こういった私から学べます．目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例：Linuxカーネル3. ...

続きを見る

ハッシュチェイン法を利用するコードは以下になります．（番兵ノードなしの実装です．）

/*
 * 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;
}

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;

}

実行結果は以下になります．

$ 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}

$ 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した場所）の空いているキーの場所に値を格納します．

線形探索法でオープンアドレス法を利用するコードは以下になります．

/*
 * 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;
}

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;

}

実行結果は以下になります．

$ 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

$ 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社で自分に合うスクールを見つけましょう．後悔はさせません！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．本記事の内容：おすすめのC言語を学べるオンラインプログラミングスクール5社 SAMURAI ENGINEER（侍エンジニア） Tech Teacher KENスクール ...

続きを見る