Related data structures: Hashtable, Array

Linear Probing

This method resolves the problem by probing or searching through alternative locations in the probe sequence until the target or an unused slot is found.

When two records demand for the same location in the hash table, the collision can be solved by placing second record linearly down wherever an empty location is found. Lookups are performed in the same way (by searching the table sequentially starting at the position given by the hash function) until finding a cell with a matching key or an empty cell. Because linear probing is especially sensitive to unevenly distributed hash values, it is important to combine it with a high-quality hash function that does not produce such irregularities.

Consider the following hash table.

Index Data
0  
1 131
2 21
3 31
4 4
5 5
6 61
7 7
8 8
9  

Given the hash table on the left, if the first number which is to be placed is 131 then 131 % 10 equals to 1. The remainder is 1, so the hash key is 1. That means we are supposed to place the record at index 1.

Next number is 21 which also gives hash key = 1 as 21 % 10 = 1. But 131 is already placed at index 1. That means collision has occurred. We will now apply linear probing.

In this method, we will search the place for number 21 from location of 131. In this case we can place the number 21 at index 2. Then if 31 has to be stored, it can be stored at index 3. Similarly, 61 can be stored at 6 because number 4 and 5 are stored before 61.
This technique makes the search operation efficient, as we have to search only limited list to obtain the desired number.

Example hashtable implementation holding maximum 10 student records. 

#include<stdio.h>
#include<stdlib.h>
 
#define LIMIT 10
 
enum record_status {EMPTY, DELETED, OCCUPIED};
 
struct Student
{
    int student_id, student_age;
    char student_name[42];
};
 
struct Record
{
    struct Student info;
    enum record_status status;
}; 
 
int hash_function(int key)
{
    return (key % LIMIT);
}
 
int search_records(int key, struct Record hash_table[])
{
    int count, temp, position;
    temp = hash_function(key); 
    position = temp;

    for (count = 1; count != LIMIT - 1; count++) {
        if (hash_table[position].status == EMPTY) {
            return -1;
        }

        if (hash_table[position].info.student_id == key) {
            return position;
        }

        position = (temp + count) % LIMIT; 
    }
    
    return -1;
}
 
void insert_records(struct Student student_rec, struct Record hash_table[])
{
    int count, position, temp;
    int key = student_rec.student_id;
    temp = hash_function(key); 
    position = temp; 

    for (count = 1; count != LIMIT - 1; count++) {
        if (hash_table[position].status == EMPTY || hash_table[position].status == DELETED) {
            hash_table[position].info = student_rec;
            hash_table[position].status = OCCUPIED; 
            printf("\nNew record inserted into hashtable.\n");
            return;
        }

        if (hash_table[position].info.student_id == key) {
            printf("\nCannot insert duplicate record.\n");
            return;
        }

        position = (temp + count) % LIMIT; 
    }

    printf("\nHashtable limit exceeded.\n");
}
 
void print_records(struct Record hash_table[])
{
    int count;
    printf("\nHashtable\n");

    for (count = 0; count < LIMIT; count++) {
        printf("\n[%d]:\t", count);

        if (hash_table[count].status == OCCUPIED) {
            printf("Occupied - ID: %d Name: %s Age: %d", hash_table[count].info.student_id, hash_table[count].info.student_name, hash_table[count].info.student_age);
        } else if(hash_table[count].status == DELETED) {
            printf("Record was deleted\n");
        } else {
            printf("Empty\n");
        }
    }
}
 
void delete_records(int key, struct Record hash_table[])
{
    int position = search_records(key, hash_table);

    if (position == -1) {
        printf("\nCould not find the key\n");
    } else {
        hash_table[position].status = DELETED;
    }
}
 
int main()
{
    int count, key, option;
    struct Record hash_table[LIMIT];
    struct Student student_rec;

    for (count = 0; count <= LIMIT - 1; count++) {
        hash_table[count].status = EMPTY;
    } 

    while(1) {
        printf("1. Insert a student record\n");
        printf("2. Delete a student record\n");
        printf("3. Search a student by ID\n");
        printf("4. Display All\n");
        printf("5. Exit\n");
        printf("Enter option number:\t");
        scanf("%d", &option);

        switch(option)
        {
            case 1: 
                printf("\nEnter Student ID:\t");
                scanf("%d", &student_rec.student_id); 
                
                printf("Enter Student Name:\t");
                scanf("%s", student_rec.student_name);

                printf("Enter Student Age:\t");
                scanf("%d", &student_rec.student_age);

                insert_records(student_rec, hash_table);
                break;

            case 2: 
                printf("\nEnter the key (ID) to delete a student:\t");
                scanf("%d", &key);

                delete_records(key, hash_table);
                break;

            case 3: 
                printf("\nEnter the key (ID) to search for a student:\t");      
                scanf("%d", &key);
                count = search_records(key, hash_table);

                if (count == -1) {
                    printf("\nCould not find a student record with given ID.\n");
                } else {
                    printf("\nStudent record found at index position:\t%d\n", count);
                }
                break;

            case 4: 
                print_records(hash_table);
                break;

            case 5: 
                exit(1);
        }
    }

    return 0;
}