Skip to content

Instantly share code, notes, and snippets.

@RichardTMiles
Last active February 4, 2018 00:50
Show Gist options
  • Save RichardTMiles/40443d5d856558e4ffb1d4cf7926c575 to your computer and use it in GitHub Desktop.
Save RichardTMiles/40443d5d856558e4ffb1d4cf7926c575 to your computer and use it in GitHub Desktop.
Compile with [ g++ -std=c++0x main.cpp ]. Run with [ ./a.out ], 110 lines.
#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";
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment