Compile with [ g++ -std=c++0x main.cpp ]. Run with [ ./a.out ], 110 lines.

HopHashTable.cpp

#include <iostream>
#include <bitset>
using namespace std;

const int TABLE_SIZE = 17;                  // You can change consts with
const int MAX_DIST = 4;                     // *((int*)(&a)) = 6
unsigned int startingPlace = 1;             // a binary representation of the hop

struct item {
    int *input;
    unsigned probing:MAX_DIST;  // <- MAX_DIST bits wide only probing;
    explicit item() : input(nullptr), probing(0) {}
};

item **table;

bool Search(int &value, bool remove = false) {
    int hash = value % TABLE_SIZE, hop;
    for (int i = 1, j = 1; i <= MAX_DIST; i++, j <<= 1)
        if (table[hash]->probing & j && *table[hop = hash + MAX_DIST - i]->input == value) {
            if (remove) {
                table[hash]->probing ^= j;
                table[hop]->input = nullptr;
                cout << value << " deleted from position " << hop << ".\n";
                return true;
            }
            cout << value << " found at position " << hop << ".\n";;
            return true;
        }
    return false;
}

bool hop(int value, unsigned int probing = 0) {
    int hash = value % TABLE_SIZE;

    auto insert = [hash, &value](int offset) {                  // Lambda Function.
        Search(value, true);
        cout << value << " inserted at position " << offset << ".\n";
        table[offset]->input = new int(value);
        offset = (offset >= hash ? offset - hash : offset + TABLE_SIZE - hash);
        table[hash]->probing |= (offset != 0 ? startingPlace >> offset : startingPlace);
        return true;
    };

    if (table[hash]->input == nullptr) return insert(hash);     // Is our hash available

    for (int secondPass = 0; secondPass < 2; secondPass++) {
        if (!secondPass) {
            // We need to recurse > & < our hash, This will prevent infinite looping
            unsigned int loop = (table[hash]->probing << (TABLE_SIZE - MAX_DIST - hash));
            if (probing & loop) return false;
            probing |= loop;
        }
        for (int i = 0, j = startingPlace, offset = hash;           // Look for empty spots nearby
             i < MAX_DIST; i++, j >>= 1, offset++)
            if (!(table[hash]->probing & j)) {
                if (offset == TABLE_SIZE) offset = 0;               // Circular
                if (!secondPass) {
                    if (table[offset]->input == nullptr) return insert(offset); // Empty spot
                } else if (hop(*table[offset]->input, probing))
                        return insert(offset);                      // Can it be moved? Recurse

            }
    }
    return false;
}

int main() {
    int input;

    table = new item *[TABLE_SIZE];

    for (input = 0; input < TABLE_SIZE; input++) table[input] = new item;
    for (input = 1; input < MAX_DIST; input++) startingPlace <<= 1;     // we need to start from the left for some reason

    auto take_input = [&input](string message) {
        cout << message;
        while (!((cin >> input) && input > 0)) {
            cin.clear();
            cout << message;
        }
    };

    for (;;) {
        take_input("HOPSCOTCH HASHING MENU:\n1 - Insert Value \n2 - Delete Value \n3 - Search Value \n4 - Output Table \n5 - Exit Program\nEnter operation to perform: ");

        if (input == 1) {
            take_input("Enter positive integer value to insert into Hopscotch Hash Table: ");
            if (!Search(input) && !hop(input))
                cout << "ERROR: Unable to insert " << input << " into Hash Table: Hopscotch Hash Failed\n";
        } else if (input == 2) {
            take_input("Enter positive integer value to delete from Hopscotch Hash Table: ");
            Search(input, true);
        } else if (input == 3) {
            take_input("Enter positive integer value to search for in Hopscotch Hash Table: ");
            Search(input);
        } else if (input == 4) {
            cout << "+----------------------+\n| #     | item   | hop |\n+----------------------+\n";
            for (int i = 0; i < TABLE_SIZE; i++) {
                (table[i]->input == nullptr ? printf("| %d\t| \t| ", i) : printf("| %d\t| %d\t| ", i, *table[i]->input));
                cout << bitset<MAX_DIST>(table[i]->probing) << " |\n";
            }
            cout << "+----------------------+\n";
        } else if (input == 5) {
            cout << "Program terminated by user...\n";
            return 1;
        } else {
            cout << "ERROR: Please select operation between 1 and 5, inclusively.\n";
        }
    }
}