Hash Table : open addressing

Hash Table : open addressing 

---

성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. 

open addressing 방식으로 충돌을 해결하는 Hash Table을 C로 구현하였습니다.

• problem

• m = 37

• Hash functions (not exactly same as the previous open address hash functions)

• linear probing: h(k, i) = (h'(k) + i) mod m where, h'(k) = k mod m
• quadratic probing: h(k, i) = (h'(k) + c1i + c2i2 ) mod m where, h'(k) = k mod m, c1 = 1, c2 = 3.
• double hashing: h(k, i) = (h1(k) + ih2(k)) mod m, where, h1(k) = k mod m, h2(k) = 1 + (k mod (m - 1)).

• 30 keys that are randomly generated. The keys are generated by rand()%1000. Execute srand(time(NULL)) first. (Duplicate keys should be avoided.)

 

1) Insert the randomly generated 30 keys to the three hash tables. (note that you need a function for the 90 insertions, 30 for each table)

 

2) Print the contents of the hash table for above three different hash functions. (Must show the correct positions of the inserted keys in the table). The print function also should print the average number of probes and primary (largest) cluster of the hash table.

• source code

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

typedef struct Node {
	int key;
	int value;
	int flag;
} Node;

int m = 37;

int hashFunction(int key) {
	return (key % m);
}
int hashFunction2(int key) {
	return (1 + key % (m-1));
}



void insert_linear_probing(Node* hashTable) {
	int i;
	double probe_sum = 0;
	srand(time(NULL));
	for (i = 0; i < 30; i++) {
		int j = 0;
		int probe = 0;
		int key = rand() % 1000;
		int hashValue = hashFunction(key);
		if (hashTable[hashValue].flag == 0) {
			probe++;
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		else if (hashTable[hashValue].flag == 1) {
			probe++;
			while (hashTable[hashValue].flag == 1) {
				j++;
				hashValue = (hashValue + j) % m;
			}
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		hashTable[hashValue].flag = 1;
		probe_sum += probe;
	}
	printf("average # of probes: %f\n", probe_sum / 30);
}

void insert_quadratic_probing(Node* hashTable) {
	int i;
	int c1 = 1;
	int c2 = 3;
	double probe_sum = 0;
	srand(time(NULL));
	for (i = 0; i < 30; i++) {
		int j = 0;
		int probe = 0;
		int key = rand() % 1000;
		int hashValue = hashFunction(key);
		if (hashTable[hashValue].flag == 0) {
			probe++;
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		else if (hashTable[hashValue].flag == 1) {
			probe++;
			while (hashTable[hashValue].flag == 1) {
				j++;
				hashValue = (hashValue + j*c1 + c2*(j^2)) % m;
			}
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		hashTable[hashValue].flag = 1;
		probe_sum += probe;
	}
	printf("average # of probes: %f\n", probe_sum / 30);
}

void insert_double_hashing(Node* hashTable) {
	int i;
	double probe_sum = 0;
	srand(time(NULL));
	for (i = 0; i < 30; i++) {
		int j = 0;
		int probe = 0;
		int key = rand() % 1000;
		int hashValue = hashFunction(key);
		if (hashTable[hashValue].flag == 0) {
			probe++;
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		else if (hashTable[hashValue].flag == 1) {
			probe++;
			while (hashTable[hashValue].flag == 1) {
				j++;
				hashValue = (hashValue + j*hashFunction2(hashValue)) % m;
			}
			hashTable[hashValue].key = key;
			hashTable[hashValue].value = hashValue;
		}
		hashTable[hashValue].flag = 1;
		probe_sum += probe;
	}
	printf("average # of probes: %f\n", probe_sum / 30);
}



void printTable(Node* hashTable) {
	int i;
	int p_cluster = 1;
	int cluster = 0;
	for (i = 0; i < 30; i++) {
		if (hashTable[i].key == -1) {
			if (cluster >= p_cluster) {
				int temp = cluster;
				cluster = 0;
				p_cluster = temp;
			}
			cluster = 0;
			printf("hash value: %d key: empty \n", i);
		}
		else {
			printf("hash value: %d key: %d \n", i, hashTable[i].key); 
			cluster++;
		}
	}
	if (cluster >= p_cluster) {
		p_cluster = cluster;
	}
	printf("primary cluster : %d\n", p_cluster);
}


void main() {
	int i;
	Node HashTable_linear[32];
	for (i = 0; i < 30; i++) {
		HashTable_linear[i].key = -1;
		HashTable_linear[i].value = -1;
		HashTable_linear[i].flag = 0;
	}
	printf("linear probing\n");
	insert_linear_probing(HashTable_linear);
	printTable(HashTable_linear);

	Node HashTable_quad[32];
	for (i = 0; i < 30; i++) {
		HashTable_quad[i].key = -1;
		HashTable_quad[i].value = -1;
		HashTable_quad[i].flag = 0;
	}
	printf("quadratic probing\n");
	insert_quadratic_probing(HashTable_quad);
	printTable(HashTable_quad);

	Node HashTable_double[32];
	for (i = 0; i < 30; i++) {
		HashTable_double[i].key = -1;
		HashTable_double[i].value = -1;
		HashTable_double[i].flag = 0;
	}
	printf("double hashing\n");
	insert_double_hashing(HashTable_double);
	printTable(HashTable_double);

}

• result