linear probing hash table Algorithm

Linear probing is a scheme in computer programming for resolve collisions in hash tables, data structures for keeping a collection of key – value pairs and looking up the value associated with a given key. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the nearest following free location and inserts the new key there. Another early publication of this method was by Soviet researcher Andrey Ershov, in 1958.

The first theoretical analysis of linear probing, showing that it takes constant expected time per operation with random hash functions, was given by Knuth. The idea of an associative array that lets data to be accessed by its value rather than by its address dates back to the mid-1940s in the work of Konrad Zuse and Vannevar shrub, but hash tables were not described until 1953, in an IBM memorandum by Hans Peter Luhn. significant later developments include a more detailed analysis of the probability distribution of the running time, and the proof that linear probing runs in constant time per operation with practically usable hash functions rather than with the idealized random functions assumed by earlier analysis.
// Copyright 2019

#include<stdlib.h>
#include<iostream>
#include<functional>
#include<string>

using std::endl;
using std::cout;
using std::cin;
using std::string;

// fwd declarations
struct Entry;
bool putProber(Entry entry, int key);
bool searchingProber(Entry entry, int key);
void add(int key);

// globals
int notPresent;
struct Entry* table;
int totalSize;
int tomb = -1;
int size;
bool rehashing;

// Node that holds key
struct Entry {
    explicit Entry(int key = notPresent) : key(key) {}
    int key;
};

// Hash a key
int hashFxn(int key) {
    std::hash<int> hash;
    return hash(key);
}

// Performs linear probing to resolve collisions
int linearProbe(int key, bool searching) {
    int hash = static_cast<int>(fabs(hashFxn(key)));
    int i = 0;
    Entry entry;
    do {
        int index = static_cast<int>(fabs((hash + i) % totalSize));
        entry = table[index];
        if (searching) {
            if (entry.key == notPresent) {
                return notPresent;
            }
            if (searchingProber(entry, key)) {
                cout << "Found key!" << endl;
                return index;
            }
            cout << "Found tombstone or equal hash, checking next" << endl;
            i++;
        } else {
            if (putProber(entry, key)) {
                if (!rehashing) cout << "Spot found!" << endl;
                return index;
            }
            if (!rehashing) cout << "Spot taken, looking at next" << endl;
            i++;
        }
        if (i == totalSize) {
            cout << "Linear probe failed" << endl;
            return notPresent;
        }
    } while (entry.key != notPresent);
    return notPresent;
}

// Finds empty spot
bool putProber(Entry entry, int key) {
    if (entry.key == notPresent || entry.key == tomb) {
        return true;
    }
    return false;
}

// Looks for a matching key
bool searchingProber(Entry entry, int key) {
    if (entry.key == key) return true;
    return false;
}

// Displays the table
void display() {
    for (int i = 0; i < totalSize; i++) {
        if (table[i].key == notPresent) {
            cout << " Empty ";
        } else if (table[i].key == tomb) {
            cout << " Tomb ";
        } else {
            cout << " ";
            cout << table[i].key;
            cout << " ";
        }
    }
    cout << endl;
}

// Rehashes the table into a bigger table
void rehash() {
    // Necessary so wall of add info isn't printed all at once
    rehashing = true;
    int oldSize = totalSize;
    Entry* oldTable = table;
    // Really this should use the next prime number greater than totalSize * 2
    table = new Entry[totalSize * 2];
    totalSize *= 2;
    for (int i = 0; i < oldSize; i++) {
        if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
            size--;  // Size stays the same (add increments size)
            add(oldTable[i].key);
        }
    }
    delete[] oldTable;
    rehashing = false;
    cout << "Table was rehashed, new size is: " << totalSize << endl;
}

// Adds entry using linear probing. Checks for load factor here
void add(int key) {
    Entry * entry = new Entry();
    entry->key = key;
    int index = linearProbe(key, false);
    table[index] = *entry;
    // Load factor greater than 0.5 causes resizing
    if (++size/ static_cast<double>(totalSize) >= 0.5) {
        rehash();
    }
}

// Removes key. Leaves tombstone upon removal.
void remove(int key) {
    int index = linearProbe(key, true);
    if (index == notPresent) {
        cout << "key not found" << endl;
    }
    cout << "Removal Successful, leaving tomb" << endl;
    table[index].key = tomb;
    size--;
}

// Information about the adding process
void addInfo(int key) {
    cout << "Initial table: ";
    display();
    cout << endl;
    cout << "hash of " << key << " is " << hashFxn(key) << " % "
        << totalSize << " == " << fabs(hashFxn(key) % totalSize);
    cout << endl;
    add(key);
    cout << "New table: ";
    display();
}

// Information about removal process
void removalInfo(int key) {
    cout << "Initial table: ";
    display();
    cout << endl;
    cout << "hash of " << key << " is " << hashFxn(key)
        << " % " << totalSize << " == " << hashFxn(key) % totalSize;
    cout << endl;
    remove(key);
    cout << "New table: ";
    display();
}

// I/O
int main(void) {
    int cmd, hash, key;
    cout << "Enter the initial size of Hash Table. = ";
    cin >> totalSize;
    table = new Entry[totalSize];
    bool loop = true;
    while (loop) {
        system("pause");
        cout << endl;
        cout << "PLEASE CHOOSE -" << endl;
        cout << "1. Add key. (Numeric only)" << endl;
        cout << "2. Remove key." << endl;
        cout << "3. Find key." << endl;
        cout << "4. Generate Hash. (Numeric only)" << endl;
        cout << "5. Display Hash table." << endl;
        cout << "6. Exit." << endl;
        cin >> cmd;
        switch (cmd) {
        case 1:
            cout << "Enter key to add = ";
            cin >> key;
            addInfo(key);
            break;
        case 2:
            cout << "Enter key to remove = ";
            cin >> key;
            removalInfo(key);
            break;
        case 3: {
            cout << "Enter key to search = ";
            cin >> key;
            Entry entry = table[linearProbe(key, true)];
            if (entry.key == notPresent) {
                cout << "Key not present";
            }
            break;
        }
        case 4:
            cout << "Enter element to generate hash = ";
            cin >> key;
            cout << "Hash of " << key << " is = " << fabs(hashFxn(key));
            break;
        case 5:
            display();
            break;
        default:
            loop = false;
            break;
            delete[] table;
        }
        cout << endl;
    }
    return 0;
}

LANGUAGE:

DARK MODE: