Wednesday, December 7, 2011

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 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 any integer between 0 and 999, depending on the value of x. As we shall see shortly, it is 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 its has key is the same as that of k2, an attempt may be make 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++

#include<iostream>
#include<cstdlib>
using namespace std;
class hash{
    private:
        int hash_pos;
        int array[40];
    public:
        hash();
        void insert();
        void search();
        int Hash(int );
        int reHash(int );
        void Delete();
};
hash::hash(){
    for(int i = 0; i < 40; i++){
        array[i] = '*';
    }
}
void hash::insert(){
    int data;
    int count = 0;
    cout<<"Enter the data to insert: ";
    cin>>data;
    hash_pos = Hash(data);
    if(hash_pos >= 40){
        hash_pos = 0;
    }
    while(array[hash_pos] != '*'){
        hash_pos = reHash(hash_pos);
        count++;
        if(count>=40){
            cout<<"Memory Full!!No space is avaible for storage";
            break;
        }
    }
    if(array[hash_pos] == '*'){
        array[hash_pos] = data;
    }
    cout<<"Data is stored at index "<<hash_pos<<endl;
}
int hash::Hash(int key){
    return key%100;
}
int hash::reHash(int key){
    return (key+1)%100;
}
void hash::search(){
    int key,i;
    bool isFound = false;
    cout<<"Enter the key to search: ";
    cin>>key;
    for(i = 0; i < 40; i++){
        if(array[i] == key){
            isFound = true;
            break;
        }
    }
    if(isFound){
        cout<<"The key is found at index "<< i <<endl;
    }else{
        cout<<"No record found!!"<<endl;
    }
}
void hash::Delete(){
    int key,i;
    bool isFound = false;
    cout<<"Enter the key to delete: ";
    cin>>key;
    for(i = 0; i < 40; i++){
        if(array[i] == key){
            isFound = true;
            break;
        }
    }
    if(isFound){
        array[i] = '*';
        cout<<"The key is deleted"<<endl;
    }else{
        cout<<"No key is Found!!";
    }
}
int main(){
    hash h;
    int choice;
    while(1){
        cout<<"\n1. Insert\n2. Search\n3. Delete\n4. Exit\n";
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
                h.insert();
                break;
            case 2:
                h.search();
                break;
            case 3:
                h.Delete();
                break;
            case 4:
                exit(0);
            default:
                cout<<"\nEnter correct option\n";
                break;
        }
    }
    return 0;
}

6 comments:

  1. Helpful for student.

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

    ReplyDelete
  3. Yes. It is Linear Probing...

    ReplyDelete
  4. 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*);
    list* newnode_data_read(int);


    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;
    }

    }
    };

    list* newnode_data_read(int newelement)
    {
    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.deletion\n 3.exit";
    cout<<"\n Please Enter Your Choice:";
    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;
    newnode=newnode_data_read(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
    *************************************************************************************************
    please help in fixing this problem.

    ReplyDelete
  5. its a linear probing search technic

    ReplyDelete