初めに

学校でファイル操作を題とした課題が出されました。二つのファイルからデータを読み込み、その結果をまとめて、一つのファイルに書き込みます。Hash Tableを使うよりもっと簡単な方法は当然存在しますが、せっかくなので実装してみることに。

Qitta は初投稿でプログラミング初心者なのでツッコミどころも多いと思いますがスルーor指摘していただけると幸いです。

概要

char型配列をKeyとする開番地法のHash Tableを自作しました。

コード

普段はC++を書いているのでHash TableではなくMapと名前をつけています。深い意味はない。

Hash_table.c

# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define Max_key_length 128
# define Form int

typedef struct _Data {
	char key[Max_key_length];
	/*用途によって変更*/
	Form val;
} Data;

typedef struct _Map {
	Data *hash_table;
	unsigned size;
	unsigned amount;
} Map;

int make_hash(Map*, char*);
void init_map(Map*, unsigned);
void refresh(Map*, unsigned);
int put(Map*, char*, void*);
void* get(Map*, char*);

int main() {
	Map map;
	init_map(&map,20);
	/*省略*/
	free(map.hash_table);
}

int make_hash(Map* map, char* key) {
	int hash = 0;
	for (int i = 0; key[i] != '\0'; i++) {
		hash = (hash * 137 + (key[i] & 255)) % map->size;
	}
	return hash;
}

void init_map(Map* map, unsigned size) {
	map->hash_table = calloc(size, sizeof(Data));
	map->size = size;
	map->amount = 0;
}

void refresh(Map* map, unsigned new_size) {
	Data *old_hash_table = map->hash_table;
	unsigned old_size = map->size;
	init_map(map, new_size);
	for (int i = 0; i < old_size; i++) {
		if (old_hash_table[i].key[0] != '\0') {
			put(map, old_hash_table[i].key, &(old_hash_table[i].val));
		}
	}
	free(old_hash_table);
}

int put(Map* map, char* key, void* val) {
	int h = make_hash(map, key);
	for (int n = 0; n < map->size; n++) {
		int index = (h + n) % map->size;
		if (map->hash_table[index].key[0] == '\0') {
			strcpy(map->hash_table[index].key, key);
			/*場合によって書き換えあり*/
			map->hash_table[index].val = *((Form*)val);
			map->amount++;
			if (map->amount * 3 > map->size * 2) {
				refresh(map, map->size * 3 / 2);
			}
			return index;
		} else if (strcmp(map->hash_table[index].key, key) == 0) {
			return index;
		}
	}
	return -1;
}

void* get(Map* map, char* key) {
	int h = make_hash(map, key);
	for (int n = 0; n < map->size; n++) {
		int index = (h + n) % map->size;
		if (map->hash_table[index].key[0] == '\0') {
			return NULL;
		} else if (strcmp(map->hash_table[index].key, key) == 0) {
			/*場合によって書き換えの必要あり*/
			return &(map->hash_table[index].val);
		}
	}
	return NULL;
}

各部の説明

struct:Data

struct_Data

typedef struct _Data {
	char key[Max_key_length];
	/*用途によって変更*/
	Form val;
} Data;

各々が持っているデータです。#defineでFormが何かマクロ定義してやります。今回はintです。

struct:Map

struct_Map

typedef struct _Map {
	Data *hash_table;
	unsigned size;
	unsigned amount;
} Map;

Dataの配列を持ちます。sizeは配列のサイズでamountは今入っている量です。これを持っている理由はamountがsizeの2/3に到達するとHash Tableを再構成するためです。

make_hash

make_hash

int make_hash(Map* map, char* key) {
	int hash = 0;
	for (int i = 0; key[i] != '\0'; i++) {
		hash = (hash * 137 + (key[i] & 255)) % map->size;
	}
	return hash;
}

Hash自体は今回テキトーです。Mapのサイズより大きくならないように、テキトーに処理しています。衝突を前提にしています。(Hashについてはまた勉強したい。)

init_map

init_map

void init_map(Map* map, unsigned size) {
	map->hash_table = calloc(size, sizeof(Data));
	map->size = size;
	map->amount = 0;
}

初期化。callocでメモリを確保しているのでfreeを最後にしなければならない。サイズはユーザー指定。main関数内で宣言Mapのポインタをそのまま(つまりNullポインタ)、init_mapに掘り込んでBus errorをやりました(2敗)。

refresh

refresh

void refresh(Map* map, unsigned new_size) {
	Data *old_hash_table = map->hash_table;
	unsigned old_size = map->size;
	init_map(map, new_size);
	for (int i = 0; i < old_size; i++) {
		if (old_hash_table[i].key[0] != '\0') {
			put(map, old_hash_table[i].key, &(old_hash_table[i].val));
		}
	}
	free(old_hash_table);
}

Mapを新しく作り替えて、古いデータを入れます。keyが空かどうかの判定は一文字目がナル文字かどうかで判断しています。

put

put

int put(Map* map, char* key, void* val) {
	int h = make_hash(map, key);
	for (int n = 0; n < map->size; n++) {
		int index = (h + n) % map->size;
		if (map->hash_table[index].key[0] == '\0') {
			strcpy(map->hash_table[index].key, key);
			/*場合によって書き換えあり*/
			map->hash_table[index].val = *((Form*)val);
			map->amount++;
			if (map->amount * 3 > map->size * 2) {
				refresh(map, map->size * 3 / 2);
			}
			return index;
		} else if (strcmp(map->hash_table[index].key, key) == 0) {
			return index;
		}
	}
	return -1;
}

Hash Tableの要素はvoidでもらうのでポインタならなんでもよいです。charを代入するときなど、その時々で変更する必要があります。amountがsizeの2/3を超えるとrefreshします。返却値としてindexを返しています。

get

get

void* get(Map* map, char* key) {
	int h = make_hash(map, key);
	for (int n = 0; n < map->size; n++) {
		int index = (h + n) % map->size;
		if (map->hash_table[index].key[0] == '\0') {
			return NULL;
		} else if (strcmp(map->hash_table[index].key, key) == 0) {
			/*場合によって書き換えの必要あり*/
			return &(map->hash_table[index].val);
		}
	}
	return NULL;
}

これもchar*がvalだった場合などに書き換えが必要です。Mapにkeyが存在する場合はそのvalのポインタを返します。存在しない場合はNULLポインタを返します。

詰まったところ

init_mapにNULLポインタを突っ込むみBuss error(2敗)
Dataのkeyとvalをポインタにして、scanfしたものと対応させたところ、結局全部同じものを指している(半日)

おわりに

char型配列しかkeyにできないし、いろいろ甘いところもあるんだろうと思う反面、高々学校の課題レベルではかなり面白いことができたんじゃないかなと思います。ポインタの扱いが難しく四苦八苦しました。まだまだプログラミング初心者ですが、頑張っていきたいです。

謝辞

今回コードの大部分をこのサイトから~~パクリ~~、お借りしました。ありがとうございます。

ハッシュ法 : http://home.a00.itscom.net/hatada/c-tips/hash01.html