Write a C program. Hashing Table from input. Write a program to calculate the ha

Question

Write a C program. Hashing Table from input.

Write a program to calculate the hashing table of input data. The program reads from the standard input the table size k. The program reads the data to be hashed from a text file named “input.txt”. Then it calculates the hashing table After the program reads the size k, open and reads the data from “input.txt”.Then it displays some statistics and continue to read from the standard input till the end of the file (standard input).

The “input.txt” file consists of records (strings, and may contain spaces) each record is in a separate line. Note that the space is a part of the record to be hashed.

You can assume that the maximum record length is 50 and the maximum value for k is 256

The statistics to be displayed is as follows (each line terminated by a new line).

•The number of entries with collision is xxx (xxx is an integer left justified in 5 digits, note there is a space between is and the first digit), where a collision is a tabel entry that received.

•The number of unused entries is xxx (again xxx is an integer left justified in 5 digits, the unused entries are the entries in the k -length table where no strings are mapped).

Sample input.txt (7 lines), k=10

sample output:

Explanation / Answer

#include <stdio.h>

// compute a hash value for string
unsigned long hash_value(char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}

int main ( void )
{
// read value of hash table from user
printf("Enter size of hash: ");
int k;
scanf("%d", &k);
int hash[k];

int i = 0;

// initialize array to be zero
// we just want to determine collision
// and empty so not storing actual values
for(i = 0; i < k; i++)
hash[i] = 0;

int collision = 0;

static const char filename[] = "input.txt";
FILE *file = fopen ( filename, "r" );
if ( file != NULL )
{
char line [ 128 ];
// read from file
while ( fgets ( line, sizeof line, file ) != NULL ) /* read a line */
{
size_t ln = strlen(line)-1;
// removing any new line
if (line[ln] == ' ')
line[ln] = '';

// computing hash within range of array
int h = (abs(hash_value(line)))%k;

// setting position of hash value in h
// in a actual hash function here we will store actual value
if (hash[h] == 0)
hash[h] = 1;
else
collision++; // increase collision count
}
fclose ( file );

int empty = 0;
// count empty values
for(i = 0; i < k; i++)
if (hash[i] == 0)
empty++;

printf("The number of entries with collision is %*d ", 5, collision);
printf("The number of unused entries is %*d ", 5, empty);
}
else
{
perror ( filename ); /* why didn't the file open? */
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.