Collision and Probing

Collision and Probing Technques
5A. Write a program to implement the collision technique

#include <stdio.h>
#include <conio.h> // Required for Turbo C functions

int main() {
    int n, i, m, key, hi[10], h[10], rel_add;
    m = 10;

    clrscr(); // Clear the screen for Turbo C

    // Initialize the hash table
    for (i = 0; i < m; i++) {
        hi[i] = -1;
    }

    printf("\nHash Table Size: %d", m);
    printf("\nNo Of Keys: ");
    scanf("%d", &n);

    printf("\nEnter The Keys: ");
    for (i = 0; i < n; i++) {
        printf("\n%d. ", i + 1);
        scanf("%d", &key);

        // Calculate the relative address
        rel_add = key % m;

        // Check for collision
        if (hi[rel_add] == -1) {
            hi[rel_add] = 1;
            h[rel_add] = key;
            printf("\tH(%d) = %d mod %d = %d", key, key, m, rel_add);
        } else {
            printf("\tH(%d) = %d mod %d = %d (Collision Case)", key, key, m, rel_add);
        }
    }

    getch(); // Wait for a key press before exiting
    return 0;
}

5B. Write a program to implement the concept of linear probing.
#include <stdio.h>
#include <conio.h> // Required for Turbo C functions

int main() {
    int n, i, m, key, hi[10], h[10], rel_add, p;
    m = 10;

    clrscr(); // Clear the screen for Turbo C

    // Initialize the hash table
    for (i = 0; i < m; i++) {
        hi[i] = -1; // Indicates empty slots
    }

    printf("\nHash Table Size: %d", m);
    printf("\nNo of Keys: ");
    scanf("%d", &n);

    printf("Enter Keys: ");
    for (i = 0; i < n; i++) {
        printf("\n%d. ", i + 1);
        scanf("%d", &key);

        p = 0; // Probing count
        rel_add = key % m;

        // Check if slot is available
        if (hi[rel_add] == -1) {
            hi[rel_add] = 1;
            h[rel_add] = key;
            printf("\tH(%d, %d) = %d", key, p, rel_add);
        } else {
            // Handle collision
            printf("\tH(%d, %d) = %d (Collision Case!)", key, p, rel_add);
            p = 1;

            // Perform linear probing
            while (p < m) {
                printf("\n");
                rel_add = ((key % m) + p) % m;

                if (hi[rel_add] == -1) {
                    hi[rel_add] = 1;
                    h[rel_add] = key;
                    printf("\tH(%d, %d) = %d", key, p, rel_add);
                    break;
                } else {
                    p++;
                }
            }

            // If table is full
            if (p == m) {
                printf("\nHash table is full. Unable to insert key: %d", key);
            }
        }
    }

    // Display the hash table
    printf("\n\nFinal Hash Table:\n");
    for (i = 0; i < m; i++) {
        if (hi[i] != -1) {
            printf("Slot %d: %d\n", i, h[i]);
        } else {
            printf("Slot %d: Empty\n", i);
        }
    }

    getch(); // Wait for a key press before exiting
    return 0;
}