Hashing Functions

Some of the methods of defining a hash function are discussed in the following paragraphs.

Modular Arithmetic

In modular arithmetic, first the key is converted to an integer, then it is divided by the size of the index range, and the remainder is taken to be the hash value. The spread achieved depends very much on the modulus. If the modulus is the power of small integers such as 2 or 10, then many keys tend to map into the same index, while other indices remain unused. The best choice for the modulus is often, but not always, a prime number, which usually has the effect of spreading the keys quite uniformly.

Truncation

Truncation ignores part of the key, and uses the remainder directly as the hash value (using numeric code to represent non-numeric field data). If the keys, for example, are eight-digit numbers and the hash table has 1000 entries, then the first, second, and fifth digits from the right side might make the hash value. So, 62538194 maps to 394. It is a fast method, but it often fails to distribute keys evenly.

Folding

In folding, the identifier is partitioned into several parts, all but the last part being of the same length. These parts are then added together to obtain the hash value. For example, an eight-digit integer can be divided into groups of three, three, and two digits. The groups are then added together, and truncated, if necessary, to be in the proper range of indices. So 62538149 maps to 625 + 381 + 94 = 1100, truncated to 100. Since all information in the key can affect the value of the function, folding often achieves a better spread of indices than truncation.

Mid-square method

In this method, the identifier is squared (using numeric code to represent non- numeric field data), and then the appropriate number of bits from the middle of the square are used to get the hash value. Since the middle bits of the square usually depend on all the characters in the identifier, it is expected that different identifiers will result in different values. The number of middle bits that we select depends on table size. Therefore, if r is the number of middle bits used to form the hash value, then the table size will be 2r. So when we use the mid- square method, the table size should be a power of 2.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 50
#define MAX 10
typedef struct node 
{
	char symbol[MAX];
	int value;
	struct node *next;
} entry;
typedef entry *entry_ptr;

int hash_value(char * name) 
{
	int sum = 0;
	while (*name != '\0') 
	{
		sum += *name;
		name++;
	}
	return (sum % SIZE);
}
void initialize(entry_ptr table[]) 
{
	int i = 0;
	for (i = 0; i < SIZE; i++)
		table[i] = NULL;
}
void insert(entry_ptr table[], char *name, int val) 
{
	int h, flag = 1;
	entry_ptr temp;
	h = hash_value(name);
	temp = table[h];
	while (temp != NULL && flag) 
	{
		if (strcmp(temp->symbol, name) == 0) 
		{
			printf("The symbol %s is already present in the table\n", name);
			flag = 0;
		}
		temp = temp->next;
	}
	if (flag) 
	{
		temp = (entry_ptr) malloc(sizeof(entry));
		if (temp == NULL) 
		{
			printf("ERRRR .......\n");
			exit(0);
		}
		strcpy(temp->symbol, name);
		temp->value = val;
		temp->next = table[h];
		table[h] = temp;
	}
}
void retrieve(entry_ptr table[], char *name) 
{
	int h, flag = 1;
	entry_ptr temp;
	h = hash_value(name);
	temp = table[h];
	while (temp != NULL && flag) 
	{
		if (strcmp(temp->symbol, name) == 0) 
		{
			printf("The symbol %s is present in the table and having" 
"value = %d\n",name, temp->value);
			flag = 0;
		}
		temp = temp->next;
	}
	if (flag == 1)
		printf("The symbol %s is not present in the table \n", name);
}
int main() 
{
	entry_ptr table[SIZE];
	char name[MAX];
	int value, n;
	initialize(table);
	do 
	{
		do 
		{
			printf("Enter the symbol and value pair to be inserted\n");
			scanf("%s %d", name, &value);
			insert(table, name, value);
			printf("Enter 1 to continue\n");
			scanf("%d", &n);
		} while (n == 1);
		do {
			printf("Enter the symbol whose value is to be retrieved\n");
			scanf("%s", name);
			retrieve(table, name);
			printf("Enter 1 to continue\n");
			scanf("%d", &n);
		} while (n == 1);
		printf("Eneter 1 to continue\n");
		scanf("%d", &n);
	} while (n == 1);
	getchar();
	return 0;
}