Skip to content

Instantly share code, notes, and snippets.

@ijklr
Created January 14, 2016 15:56
Show Gist options
  • Save ijklr/2a9dac2b3259fe9da5c1 to your computer and use it in GitHub Desktop.
Save ijklr/2a9dac2b3259fe9da5c1 to your computer and use it in GitHub Desktop.
A very rudimentary C++ implementation of hashmap, allocated on the stack.
//This program is a simple demonstration of the speed difference between standard hashmap from C++ STL library vs. my simple hashmap allocated on the stack. My version is severely limited in for general use, but it is faster and can be run on Arduino devices, whereas there's no STL available for the arduino.
//To compile: g++ -std=c++11 StackHash.cpp
#include <iostream>
#include <unordered_set>
#include <ctime>
using namespace std;
//This default hash assumes T can be converted to int implicitly.
//The user can define how to map T to int with template specializations.
template <class T>
struct DefaultHashFunc
{
inline static int to_int(const T& t) {
return t;
}
};
//This is a stack based hash table supporting basic operations:
//1)insert an element into the hash
//2)see if an element exist
//Pros: Fast, no heap memory, no STL header needed. e.g. embeded programming
//Cons: User must anticipate max memory usage. Limited functionality.
//NOTE: if N is not enough to hold all element, error will be reported.
template <class T, int N, class HashFunc = DefaultHashFunc<T> >
class StackHash {
private:
struct Node{
T val;
Node *next;
};
Node buffer[N];
Node *hash[N] = {nullptr};
int buf_i=0;
public:
void insert(const T& t) {
if(buf_i >= N) {
cerr <<"error: exceeded capacity!"<<endl;
return;
}
buffer[buf_i].val = t;
int hash_value = HashFunc::to_int(t)%N;
if(hash[hash_value] == nullptr) {
buffer[buf_i].next = nullptr;
hash[hash_value] = &buffer[buf_i];
} else {
buffer[buf_i].next = hash[hash_value];
hash[hash_value] = &buffer[buf_i];
}
buf_i++;
}
bool exist(const T& t){
int hash_value = HashFunc::to_int(t)%N;
if(hash[hash_value] == nullptr) {
return false;
} else {
Node *p = hash[hash_value];
while(p) {
if(p->val == t) return true;
p = p->next;
}
}
return false;
}
};
class SimpleTimer {
public:
SimpleTimer(){
start_ = clock();
}
~SimpleTimer(){
double duration = (clock() - start_) / static_cast<double>(CLOCKS_PER_SEC);
cout<<"clock duration: "<< duration <<'\n';
}
private:
std::clock_t start_;
};
int main()
{
const int sz = 10000;
{
SimpleTimer t;
StackHash<int, sz> stack_hash_table;
for(int i = 0; i<sz; ++i) stack_hash_table.insert(i);
int answer = 0;
for(int i = 0; i<sz; ++i) answer += stack_hash_table.exist(i);
cout<<"StackHash found count="<<answer<<endl;
}
{
SimpleTimer t;
unordered_set<int> stl_hash_table;
for(int i = 0; i<sz; ++i) stl_hash_table.insert(i);
int answer = 0;
for(int i = 0; i<sz; ++i) {
answer += (stl_hash_table.find(i) != stl_hash_table.end());
}
cout<<"STL found count="<<answer<<endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment