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++

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