Hash Table : separate chaining

Hash Table  : separate chaining 

---

성균관대학교 소프트웨어학과 조대호 교수님의 알고리즘 수업을 들으며 수행했던 과제입니다. 

rand() 함수로 랜덤 값들을 뽑아 해시 테이블에 적절한 해시 함수를 적용하여 삽입하는 코드입니다. 

해시 함수는 전역 변수 N 의 값으로 설정할 수 있습니다.

• source code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
	int key;
	int value;
	struct Node* next;
} Node;

typedef struct listItem {
	Node* head;
	Node* tail;
	int length;
} ListItem;

ListItem* hashTable;
int N = 7;


int hashFunction(int key) {
	return (key % N);
}

Node* initNode(int key, int value) {
	Node* newnode = malloc(sizeof(Node));
	newnode->key = key;
	newnode->value = value;
	newnode->next = NULL;
	return newnode;
}
int k = 0;
void insertToHash(Node* newnode) {

	//printf("%d 번째 노드 insertion : %d, %d \n", k++, newnode->key, newnode->value);
	int i;
	/*first node insertion to the empty hash table*/
	if (hashTable == NULL) {
		hashTable = malloc(sizeof(ListItem) * N);
		for (i = 0; i < N; i++) {
			hashTable[i].length = 0;
			hashTable[i].head = i;
			hashTable[i].head = initNode(0, 0);
			hashTable[i].head->next = hashTable[i].tail;
		}

	}
	int valueIndex = 0;
	for (i = 0; i < N; i++) {
		if (newnode->value == i) {
			valueIndex = i;
		}
	}
	if (hashTable[valueIndex].head->next == hashTable[valueIndex].tail) {
		newnode->next = hashTable[valueIndex].head->next;
		hashTable[valueIndex].head->next = newnode;
		hashTable[valueIndex].length++;
	}
	else {
		Node* temp = hashTable[valueIndex].head;
		while (temp->next != hashTable[valueIndex].tail) {
			temp = temp->next;
		}
		temp->next = newnode;
		newnode->next = hashTable[valueIndex].tail;
		hashTable[valueIndex].length++;
	}
}

void printTable() {
	int i;
	int min = 50, max = 0, sum = 0;
	for (i = 0; i < N; i++) {
		printf("Hash Value: %d\n", i);
		Node* temp = hashTable[i].head;
		while (temp->next != hashTable[i].tail) {
			printf("%d ->", temp->next->key);
			temp = temp->next;
		}
		printf("end of the chain");
		printf("\nlength of the chain: %d\n\n", hashTable[i].length);
		if (min >= hashTable[i].length) min = hashTable[i].length;
		if (max <= hashTable[i].length) max = hashTable[i].length;
		sum += hashTable[i].length;
	}

	printf("min length: %d\n", min);
	printf("max length: %d\n", max);
	printf("average length: %d\n", sum / N);

}

void insert() {
	int i;
	srand(time(NULL));
	for (i = 0; i < 50; i++) {
		int k = 0;
		int key = rand() % 1000;
		int hashValue = hashFunction(key);
		Node* newnode = initNode(key, hashValue);

		insertToHash(newnode);
	}
	printTable();
}



int main(void) {

	printf("h(k) = k mode %d\n", N);
	insert();
	return;

}

• result