I writing Hash Table with Double Hashing. This Code working ONLY with ASCII text files and finding the number of occurrences of each word in Input File! I hope you look at my code and point out mistakes and shortcomings. Thanks in Advance :)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define STRINGSIZE 50
#define EXP 2
#define TABLESIZE 100
struct hashtable {
int amount;
char string[50];
};
struct hastable *insert(char *str, struct hashtable *table, int *psize, int *pbusy);
unsigned int hash(const char *str);
unsigned int hash2(const char *str);
int get(char *str, struct hashtable *table, int size);
struct hashtable *rehash(struct hashtable *table, int *size, int *pbusy) {
int i = 0;
int size2 = 0;
int psize2 = *size;
int result = 0;
(*size) *= EXP;
struct hashtable *temp = (struct hashtable*)calloc(sizeof(struct hashtable), *size);
*pbusy = 0;
while (i < psize2) {
temp = insert(table[i].string, temp, size, pbusy, table[i].amount);
i++;
}
free(table);
return temp;
}
int get(char *str, struct hashtable *table, int size) {
unsigned int value = hash(str) % size;
int i = 0;
while (value < size) {
if (!strcmp(table[value].string, str)) {
return table[value].amount;
}
value = (hash(str) + i + hash2(str)) % size;
i++;
if (value == (size - 1))
break;
}
return 0;
}
unsigned int hash2(const char *str) {
unsigned int hash = 0;
for(; *str; str++) {
hash += (unsigned char)(*str);
hash -= (hash << 13) | (hash >> 19);
}
return hash;
}
unsigned int hash(const char *str) {
static const unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
for (; *str; str++) {
hash = hash * a + (unsigned char)(*str);
a *= b;
}
return hash;
}
struct hastable *insert(char *str, struct hashtable *table, int *psize, int *pbusy, int amount) {
unsigned long long int value = 0;
if ((*pbusy) > ((2 * (*psize)) / 3)) {
printf("Rehash... ");
printf("Table Size = %d", *psize);
table = rehash(table, psize, pbusy, str);
printf(" [OK]\n");
}
value = hash(str) % (*psize);
if (!strcmp(table[value].string, str)) {
(table[value].amount)++;
} else if (!strlen(table[value].string)) {
strcpy(table[value].string, str);
if (!amount){
table[value].amount++;
} else {
table[value].amount = amount;
}
(*pbusy)++;
} else if ((strcmp(table[value].string, str)) && (strlen(table[value].string))) {
value = (hash(str) + hash2(str)) % (*psize);
int i = 0;
while (value < *psize) {
if (!strcmp(table[value].string, str)) {
table[value].amount++;
break;
} else if (!strlen(table[value].string)) {
strcpy(table[value].string, str);
if (!amount){
table[value].amount++;
} else {
table[value].amount = amount;
}
(*pbusy)++;
break;
}
value = (hash(str) + (i + hash2(str))) % (*psize);
i++;
}
}
return table;
}
void WorkWithFile(char *argv[]) {
FILE *text = fopen(argv[1], "r");
if (NULL == text) {
printf("Error! You was opened empty file or file doesn't exist!\n");
return;
} else {
printf("File was opened\n");
char string[STRINGSIZE] = { 0 };
int size = TABLESIZE;
int busy = 0;
int *psize = &size;
int *pbusy = &busy;
int i = 0;
struct hashtable *table = (struct hashtable*)calloc(size, sizeof(struct hashtable));
printf("Building HashTable...\n");
while (fscanf(text, "%s", string) == 1) {
table = insert(string, table, psize, pbusy, 0);
}
fclose(text);
printf("[OK]\n\n");
while (!strstr(string, "EOF")) {
printf("Enter Substring : ");
scanf("%s", string);
printf("The Number of Occurrences ");
printf("%d\n\n", get(string, table, size));
}
free(table);
}
}
int main(int argc, char *argv[]) {
printf("Welcome to HashTable Program!\n");
if (1 < argc) {
printf("Argument has been Received\n");
srand(time(NULL));
WorkWithFile(argv);
} else {
printf("The program requires an argument on the command line!\nPlease run this program from console with any arguments.\n");
return 1;
}
return 0;
}