Data Structure – Hashing and Hash Table Generation using C/C++

Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string.

Hash Function

A function that transforms a key into a table index is called a hash function. If h is a hash function and key is a key, h(key) is called the hash of key and is the index at which a record with the key should be placed. If r is a record whose key hashes into hr, hr is called hash key of r.  The has function in the preceding example is h(k) = key % 1000. The values that h produce should cover the entire set of indices in the table. For example, the function x % 1000 can produce an integer between 0 and 999, depending on the value of x. As we shall see shortly, it is a good idea for the table size to be somewhat larger than the number of records that are to be inserted.

Hash Collision

Suppose that two keys k1 and k2 are such that h(k1) equals h(k2). Then when a k2 is hashed, because it has a key is the same as that of k2, an attempt may be made to insert the record into the same position where the record with key k1 is stored. Clearly, two records cannot occupy the same position, Such a situation is called a hash collision or a hash clash.

Source code for Hashing and Hash table generation in C/C++

SHARE Data Structure – Hashing and Hash Table Generation using C/C++

6 Responses

1. Anonymous says:

2. Anonymous says:

is it using open addressing? linear probing i guess. am i right?

3. Anonymous says:

Yes. It is Linear Probing…

4. Anonymous says:

facing problem:

#include
#include
using namespace std;

struct list
{
int item;
struct list *next;
};
struct list *lp1,**lpp1,*prevlp1,*newnode;
void delete_node(int,list*,list*);
void insert_node(list*,list**,list*);

void delete_node(int i,list *lp,list *prevlp)
{

for(lp = list; lp != NULL; lp = lp->next)
{
if(lp->item == i)
{
if(lp == list)
list = lp->next;
else
prevlp->next = lp->next;
break;
}
prevlp = lp;
}
};

void insert_node(list* newlp,list **lpp,list *lp)
{

for(lpp=&list;(*lpp)!=NULL;lpp=&(*lpp)->next)
{
lp=*lpp;
if(newlp->itemitem){
newlp->next=lp;
*lpp=newlp;
break;
}

}
};

{
struct list *newitem;
newitem->item=newelement;
return newitem;
};

int main()
{

while(1)
{
int choice,data;
//struct list **lpp1,*lp1,*prevlp1,*newnode;
cout<<"n This is the Menu for insertion and deletion of elements:n *****************************************************";
cout<<"n 1.insertion n 2.deletionn 3.exit";
cin>>choice;
switch(choice)
{
case 1:
cout<<"n Your choice is '1'.You opted for 'insertion'";
cout<<"n Enter the element to be inserted:";
cin>>data;
insert_node(newnode,lpp1,lp1);
break;
case 2:
cout<<"n Your choice is '2'.You opted for 'Deleted'";
cout<<"n Enter the element to be deleted:";
cin>>data;
delete_node(data,lp1,prevlp1);
break;
case 3:
exit(0);
break;
default:
cout<<"Please Enter Correct Choice:";
break;
}
}

***********************************
while compliling, getting these errors:
************************************************
double_pointer.cpp: In function ‘void delete_node(int, list*, list*)’:
double_pointer.cpp:19:15: error: expected primary-expression before ‘;’ token
double_pointer.cpp:23:17: error: expected primary-expression before ‘)’ token
double_pointer.cpp:24:32: error: expected unqualified-id before ‘=’ token
double_pointer.cpp: In function ‘void insert_node(list*, list**, list*)’:
double_pointer.cpp:36:23: error: expected primary-expression before ‘;’ token
*************************************************************************************************