ハッシュテーブルをc言語で実装(サンプルコードあり)

ハッシュテーブルをc言語で実装

今回は下記のようなハッシュ関数を採用することにしました。
とてもシンプルです。
キーとなる入力文字列の各文字のアスキーコードの和を求めて、ハッシュテーブルのテーブルサイズで割った余りをハッシュ値としました。

int hashFunc(char* keyStr){
	int sum = 0;
	int i = 0;
	
	while(keyStr[i] != '\0'){
		sum += keyStr[i];
		i++;
	}
	
	return sum % SIZE_TABLE;
}

今回はキーの衝突（異なるキーでもハッシュ値が同じになる場合にがある）を前提としています。
衝突した場合は、同じハッシュ値となったキー同士を連結リストを使って格納していきます。

参考：連結リスト(片方向)でpushとpopをc言語で実装(サンプルコードあり)

typedef struct node{
	char			keyStr[SIZE_KEYSTR];
	int 			value;
	struct node*	pNextNode;
}node_t;

そして、ハッシュテーブルには連結リストの先頭のポインタを格納します。
下記のように宣言します。

int main(){
	node_t* pHashTable[SIZE_TABLE];

	//省略
}

それでは、ハッシュテーブルにキーを登録する関数です。
大まかに下記のステップで関数を実装しています。
1. キーのハッシュ値を求める
2. ハッシュ値を、ハッシュテーブルの配列のインデックスとする
3. ハッシュ値に紐付く連結リストへのポインタを取得する
※ハッシュ値で指定した要素は、連結リストの先頭のポインタとなっている
4. 連結リストを検索して、入力キーが存在するか判定
　　存在しない→値を書き換え
　　存在した　→新規でノードを登録

node_t* initNode(char* keyStr, int value){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("init malloc error\n");
		return NULL;
	}
	
	strcpy(pNode->keyStr, keyStr);
	pNode->value = value;
	pNode->pNextNode = NULL;
	
	return pNode;
}

void registerKeyVal(node_t** pHashTable, char* keyStr, int value){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	
	if(strlen(keyStr) > SIZE_KEYSTR - 1){
		printf("arg error\n");
		return;
	}
	
	//連結リストが存在しない場合
	if(pHashTable[hashFunc(keyStr)] == NULL){
		pHashTable[hashFunc(keyStr)] = initNode(keyStr, value);
		if(pHashTable[hashFunc(keyStr)] == NULL){
			return;
		}
		printf("Registered\n");
		printfHashTable(pHashTable);
		return;
	}

	//連結リストが存在した場合
	pNode = pHashTable[hashFunc(keyStr)];
	pPreNode = pNode;
	while(pNode != NULL){
		if(strcmp(keyStr, pNode->keyStr) == 0){
			pNode->value = value;
			printf("Reregistered\n");
			printfHashTable(pHashTable);
			return;
		}
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	
	pPreNode->pNextNode = initNode(keyStr, value);
	//error chkはなし
	
	printf("Registered\n");
	printfHashTable(pHashTable);
	
	return;
}

続いて、キーを削除する関数です。
ハッシュテーブルに紐付く連結リストに、同じキーが存在するか検索します。
存在すればfreeして、freeした左右のノードを連結し直します。

void deleteKey(node_t** pHashTable, char* keyStr){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	
	if(pHashTable[hashFunc(keyStr)] == NULL){
		printf("No key\n");
		printfHashTable(pHashTable);
		return;
	}
	pNode =  pHashTable[hashFunc(keyStr)];
	while(pNode != NULL){
		if(strcmp(keyStr, pNode->keyStr) == 0){
			//連結リストの先頭のノードの処理
			if(pNode == pHashTable[hashFunc(keyStr)]){
				pHashTable[hashFunc(keyStr)] = pNode->pNextNode;
			//連結リストの2ノード目以降の場合は、連結リストを連結し直す
			}else{
				pPreNode->pNextNode = pNode->pNextNode;
			}
			free(pNode);
			printf("Delete key\n");
			printfHashTable(pHashTable);
			return;
		}
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	printf("No key\n");
	printfHashTable(pHashTable);
	
	return;
}

pPreNodeの役割についていくつかご質問を頂いていたので、
この場で回答させて頂きます。

    while(pNode != NULL){
　　　　〜省略〜
                pPreNode->pNextNode = pNode->pNextNode;
            }
　　　　〜省略〜
        }
        pPreNode = pNode;
        pNode = pNode->pNextNode;
    }

理由としては、pNodeの中身を書き換えたあとに、書き換える前のpNodeの値を参照するからです。
なので、一旦pNodeの中身を書き換える前に、pPreNodeに退避させておきます。
そうすることで、pNodeの中身を書き換えたあともpPreNodeを使えば、書き換える前のpNodeを参照することができます。

・一旦pNodeの中身を書き換える前に、pPreNodeに退避させておきます。

pPreNode->pNextNode = pNode->pNextNode;

・pNodeの値を書き換えます。

pNode = pNode->pNextNode

pPreNodeを参照することで、書き換える前のpNodeの値を参照することができる。

                pPreNode->pNextNode = pNode->pNextNode;

サンプルコード

下記がサンプルコードになります。

 $ cat sample.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE_KEYSTR 3
#define SIZE_TABLE 3

typedef struct node{
	char			keyStr[SIZE_KEYSTR];
	int 			value;
	struct node*	pNextNode;
}node_t;

void printfHashTable(node_t** pHashTable){
	node_t* pNode = NULL;
	int i;
	
	for(i = 0; i < SIZE_TABLE; i++){
		if(pHashTable[i] != NULL){
			pNode = pHashTable[i];
			while(pNode != NULL){
				printf("hashVal:%d key:%s value:%d\n", i, pNode->keyStr, pNode->value);
				pNode = pNode->pNextNode;
			}
		}
	}
	printf("\n");
	
	return;
}

int hashFunc(char* keyStr){
	int sum = 0;
	int i = 0;
	
	while(keyStr[i] != '\0'){
		sum += keyStr[i];
		i++;
	}
	
	return sum % SIZE_TABLE;
}

void initHashTable(node_t** pHashTable){
	int i;
	
	for(i = 0; i < SIZE_TABLE; i++){
		pHashTable[i] = NULL;
	}
	printfHashTable(pHashTable);
}

node_t* initNode(char* keyStr, int value){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("init malloc error\n");
		return NULL;
	}
	
	strcpy(pNode->keyStr, keyStr);
	pNode->value = value;
	pNode->pNextNode = NULL;
	
	return pNode;
}

void registerKeyVal(node_t** pHashTable, char* keyStr, int value){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	
	if(strlen(keyStr) > SIZE_KEYSTR - 1){
		printf("arg error\n");
		return;
	}
	
	//連結リストが存在しない場合
	if(pHashTable[hashFunc(keyStr)] == NULL){
		pHashTable[hashFunc(keyStr)] = initNode(keyStr, value);
		if(pHashTable[hashFunc(keyStr)] == NULL){
			return;
		}
		printf("Registered\n");
		printfHashTable(pHashTable);
		return;
	}

	//連結リストが存在した場合
	pNode = pHashTable[hashFunc(keyStr)];
	pPreNode = pNode;
	while(pNode != NULL){
		if(strcmp(keyStr, pNode->keyStr) == 0){
			pNode->value = value;
			printf("Reregistered\n");
			printfHashTable(pHashTable);
			return;
		}
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	
	pPreNode->pNextNode = initNode(keyStr, value);
	//error chkはなし
	
	printf("Registered\n");
	printfHashTable(pHashTable);
	
	return;
}

void deleteKey(node_t** pHashTable, char* keyStr){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	
	if(pHashTable[hashFunc(keyStr)] == NULL){
		printf("No key\n");
		printfHashTable(pHashTable);
		return;
	}
	pNode =  pHashTable[hashFunc(keyStr)];
	while(pNode != NULL){
		if(strcmp(keyStr, pNode->keyStr) == 0){
			//連結リストの先頭のノードの処理
			if(pNode == pHashTable[hashFunc(keyStr)]){
				pHashTable[hashFunc(keyStr)] = pNode->pNextNode;
			//連結リストの2ノード目以降の場合は、連結リストを連結し直す
			}else{
				pPreNode->pNextNode = pNode->pNextNode;
			}
			free(pNode);
			printf("Delete key\n");
			printfHashTable(pHashTable);
			return;
		}
		pPreNode = pNode;
		pNode = pNode->pNextNode;
	}
	printf("No key\n");
	printfHashTable(pHashTable);
	
	return;
}

void deleteNode(node_t** pHashTable){
	node_t* pNode = NULL;
	node_t* pPreNode = NULL;
	int i;
	
	for(i = 0; i < SIZE_TABLE; i++){
		if(pHashTable[i] != NULL){
			pNode = pHashTable[i];
			while(pNode != NULL){
				pPreNode = pNode;
				pNode = pNode->pNextNode;
				free(pPreNode);
			}
			pHashTable[i] = NULL;
		}
	}
	printf("Delete all the node\n");
	printfHashTable(pHashTable);
	
	return;
}

int main(){
	node_t* pHashTable[SIZE_TABLE];
	
	initHashTable(pHashTable);
	
	registerKeyVal(pHashTable, "c", 3);
	registerKeyVal(pHashTable, "d", 4);
	registerKeyVal(pHashTable, "e", 5);
	registerKeyVal(pHashTable, "f", 6);
	registerKeyVal(pHashTable, "d", 1);
	
	deleteKey(pHashTable, "c");
	deleteKey(pHashTable, "c");
	deleteKey(pHashTable, "f");
	
	deleteNode(pHashTable);
	registerKeyVal(pHashTable, "c", 3);
	deleteNode(pHashTable);

	return 0;
}

下記が実行結果になります。

 $ gcc  sample.c -o sample
 $ ./sample 

Registered
hashVal:0 key:c value:3

Registered
hashVal:0 key:c value:3
hashVal:1 key:d value:4

Registered
hashVal:0 key:c value:3
hashVal:1 key:d value:4
hashVal:2 key:e value:5

Registered
hashVal:0 key:c value:3
hashVal:0 key:f value:6
hashVal:1 key:d value:4
hashVal:2 key:e value:5

Reregistered
hashVal:0 key:c value:3
hashVal:0 key:f value:6
hashVal:1 key:d value:1
hashVal:2 key:e value:5

Delete key
hashVal:0 key:f value:6
hashVal:1 key:d value:1
hashVal:2 key:e value:5

No key
hashVal:0 key:f value:6
hashVal:1 key:d value:1
hashVal:2 key:e value:5

Delete key
hashVal:1 key:d value:1
hashVal:2 key:e value:5

Delete all the node

Registered
hashVal:0 key:c value:3

Delete all the node