Directional Vector
varishangout.com
I was bored the last few days, read a bit about hashes and hash tables and thought it would be fun to rewrite them.
Anyways here is my abomination that may contain code or logic from random websites. Please tell me that I'm retarded (pointing out the issue optional)
main.cpp (nothing interesting here)
hashtable.h. The actual interesting bit
prime.h. "Calculates" a high prime number that I'm using in the compressing function.
This is pretty shit but it werks most of the time. Collisions happen often tho and trying to make an instance of hst::HashTable<std::string> is crashing with a lot of errors that I don't have the patience to actually work out.
Also the
Anyways here is my abomination that may contain code or logic from random websites. Please tell me that I'm retarded (pointing out the issue optional)
main.cpp (nothing interesting here)
C++:
#include <iostream>
#include "hashtable.h"
int main(int argc, char const *argv[])
{
hst::HashTable<int> map = hst::HashTable<int>(150); // New map type int; size 150
map.insert("integer", 99); // Insert integer
map.insert("2", 21);
map.insert("3", 19);
map.remove("3"); // Remove by key
map.resize(200); // Resize map (size 200)
std::cout << map.get("integer") << std::endl; // Get value by key
std::cout << map.get("2") << std::endl;
return 0;
}
hashtable.h. The actual interesting bit
C++:
#ifndef HASHTABLE_INCLUDE
#define HASHTABLE_INCLUDE
#include <iostream>
#include <stdlib.h>
#include <vector>
#include "prime.h"
namespace hst
{
template <class T>
class HashTable
{
private:
T *arr; // The content of the map
std::vector<std::string> keys; // A list of used keys. Used for reallocating and returning every key.
int r1; // Random parameter 1
int r2; // Random parameter 2
long long int p; // Prime number larger than arr
__int128 hash(const std::string &key) // Generate a hash based on the key
{
__int128 hash = 0;
for (int i = 0; i < key.length(); i++)
{
hash = (hash << 5) - hash + key[i]; // Hash = hash*31 + key[i] (a lot of collisions don't @ me)
}
return hash;
}
int compressedHash(__int128 hash)
{
return ((r1 * hash + r2) % p) % sizeof(arr); // Compress hash into usable index (same as above)
}
public:
HashTable(int size)
{
srand(time(NULL)); // Seed
r1 = rand() % 5000 + 200; // Set first random parameter
r2 = rand() % 5000 + 200; // Set second random parameter
arr = new T[size]; // Set array to size
p = prime::highest(sizeof(arr), sizeof(arr) + 1000); // Get a (more or less) appropriate prime number
}
void insert(std::string key, T content)
{
arr[compressedHash(hash(key))] = content; // Set content
keys.push_back(key); // Add to used keys
}
T get(std::string key)
{
return arr[compressedHash(hash(key))]; // Kind of self explaining
}
void remove(std::string key)
{
arr[compressedHash(hash(key))] = NULL; // This will give you a warning but fuck it
std::vector<std::string>::iterator el = keys.begin(); // First element
for (int i = 0; i < keys.size(); i++) //For every element
{
if (keys[i] == key)
{
keys.erase(el);
return;
}
el++; // Next element
}
}
void resize(int size)
{
T *contents = new T[keys.size()]; // Temporary array for every value by key
for (int i = 0; i < keys.size(); i++)
{
contents[i] = get(keys[i]);
}
arr = new T[size]; // I'm pretty sure this is memory leakage
for (int i = 0; i < keys.size(); i++)
{
arr[compressedHash(hash(keys[i]))] = contents[i]; // Rehash & store every stored element
}
delete[] contents; // Delete temp array
}
std::vector<std::string> getKeys()
{
return keys; // Yeah
}
/**
* Get a pointer to a new array holding every inserted key.
* Remember to delete.
*/
std::string *getKeysArray()
{
std::string *k = new std::string[keys.size()];
for (int i = 0; i < keys.size(); i++)
{
k[i] = keys[i];
}
return k;
}
};
}
#endif
prime.h. "Calculates" a high prime number that I'm using in the compressing function.
C++:
#ifndef PRIME_INCLUDE
#define PRIME_INCLUDE
namespace prime
{
/**
* I copied this from SO and only edited a few bits.
* Don't ask why this works.
* Returns the highest prime number (lower than max & higher than min)
*/
int highest(long long int min, long long int max)
{
long long int p;
for (int i = min; i <= max; i++)
{
for (int j = 2; j <= i; j++)
{
if (!(i % j) && (i != j))
{
break;
}
if (j == i)
{
p = i;
}
}
}
return p;
}
}
#endif
This is pretty shit but it werks most of the time. Collisions happen often tho and trying to make an instance of hst::HashTable<std::string> is crashing with a lot of errors that I don't have the patience to actually work out.
Also the
arr[compressedHash(hash(key))] = NULL;
is bullshit but I have no memory efficient idea to make this work with every type.