'Linear Probing - Collision Troubleshooting when Inserting Element

I'm trying to create a Linear Probing program. So far, I'm stuck trying to create an insertElement function. The idea is that as key values are being inserted in a list (hash table), it will fill in all of the slots by looking for empty slots of the list and inserting the keys in them.

Visual image of the linear probing concept

Here is my code for that:

class HashMapTable
{
    // initializing the size of the hash table
    int table_size;

    // a pointer* vector that points to an array on the hash table containing the keys
    vector<int>* table;

public:
    // creating a parameterized constructor of the above class containing all the methods
    HashMapTable(int key);

    // hash function formula to compute the index using table_size and key
    int hashFunction(int key) {
        return (key % table_size);
    }
    // inserting a key in the hash table
    void insertElement(int key);
}

HashMapTable::HashMapTable(int ts)
{
    table.size() = ts;      // 'this' pointer calling this object's copy of Class table_size object
    table = new vector<int>[table.size()];  // allocating 'new' dynamic memory to create vector during runtime
}

// insert function to push the keys in hash table
void HashMapTable::insertElement(int key)
{
    int index = hashFunction(key);    // index of array equating to the key%table_size

    // iterate through hash table. insert key in slot, unless it is occupied
    if (table[index].empty())
        table[index].push_back(key);    // adds the key at the end of the hash table array
    else {
        vector<int> ::iterator i;
        for (auto& i : table[index]) {  // ranged for-loop (C++11 things)
            table[index].push_back(key);
            break;
        }
    }
}

int main()
{
    // array of all the keys to be inserted in the hash table
    int arr[] = { 20, 34, 56, 54, 76, 87 };
    int n = sizeof(arr) / sizeof(arr[0]);

    // table_size of hash table as 6
    HashMapTable ht(6);
    for (int i = 0; i < n; i++)
        ht.insertElement(arr[i]);

    // displaying the final data of hash table
    ht.displayHashTable();

    return 0;
}

The output would look like this:

0 ==> 54
1
2 ==> 20 ==> 56
3 ==> 87
4 ==> 34 ==> 76
5

The numbers on the left are the index positions of the hash table array. The numbers on the right of the ==> are the keys inserted into each element given the table size and the modulo (following the hash(key) = key % table_size formula).

So, my question is this: How do I get the other keys of the list that share the same index as some other keys to move to the next empty slot in the list?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source