C++ Data Structures with Templates
Chapter 10: Hash Tables
The Code
HashKey.h#ifndef HashKey_h
#define HashKey_h
#include <stdint.h>
template<typename K>
class HashKey {
public:
static uint16_t gethash(K key) {
// designed to hash non-numeric keys
uint16_t hash = 5381;
uint8_t* b = (uint8_t*)&key;
for (int i = 0, j = sizeof(K); i < j; i++) {
hash = ((hash << 5) + hash) + b[i];
}
return hash;
}
};
template<>
class HashKey<uint16_t> {
public:
static uint16_t gethash(uint16_t key) {
return key;
}
};
template<>
class HashKey<int16_t> {
public:
static uint16_t gethash(int16_t key) {
return key;
}
};
template<>
class HashKey<uint8_t> {
public:
static uint16_t gethash(uint8_t key) {
return key;
}
};
template<>
class HashKey<int8_t> {
public:
static uint16_t gethash(int8_t key) {
return key;
}
};
template<>
class HashKey<int32_t> {
public:
static uint16_t gethash(int32_t key) {
return key;
}
};
template<>
class HashKey<uint32_t> {
public:
static uint16_t gethash(uint32_t key) {
return key;
}
};
#endif
Pair.h
#ifndef Pair_h
#define Pair_h
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
pair() : first(T1()), second(T2()) {}
pair(const T1& a, const T2& b) : first(a), second(b) {}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& k, const T2& t)
{
return pair<T1, T2>(k, t);
}
#endif
HashTableLP.h
#ifndef HashTableLP_h
#define HashTableLP_h
#include "HashKey.h"
#include "Pair.h"
template<typename T, typename K>
class HashTableLP {
public:
class HashEntry;
class iterator;
HashTableLP(size_t);
HashTableLP(size_t, uint16_t);
~HashTableLP();
void insert(K, T);
void insert(K, T, uint16_t);
iterator begin();
T* find(K);
T* find(K, uint16_t);
size_t count();
void erase(K);
void erase(K, uint16_t);
void clear();
protected:
HashEntry **table;
const HashEntry* DELETED = (HashEntry*)1;
size_t tSize;
private:
uint16_t getPrime(size_t);
void initTable(size_t, uint16_t);
uint16_t moduloValue;
uint16_t primes[10] =
{ 19, 31, 47, 59, 61, 97, 127, 251, 509, 1021 };
};
template<typename T, typename K>
class HashTableLP<T, K>::HashEntry {
public:
HashEntry(K key, T data) {
this->key = key;
this->data = data;
}
K key;
T data;
};
template<typename T, typename K>
class HashTableLP<T, K>::iterator : public pair<K, T> {
public:
iterator(HashTableLP* p) {
parent = p;
nxtIdx = -1;
noMore = false;
setNext();
}
bool hasNext() {
return !noMore;
}
iterator &operator ++(int) {
setNext();
return *this;
}
iterator &operator ++() {
setNext();
return *this;
}
private:
size_t nxtIdx;
HashTableLP* parent;
bool noMore;
void setNext() {
nxtIdx++;
for (; nxtIdx <= parent->tSize; nxtIdx++) {
if (nxtIdx < parent->tSize && (parent->table[nxtIdx] && parent->table[nxtIdx] != parent->DELETED)) {
break;
}
}
if (nxtIdx < parent->tSize) {
setPair(nxtIdx);
}
else {
noMore = true;
}
}
void setPair(size_t idx) {
this->first = parent->table[idx]->key;
this->second = parent->table[idx]->data;
}
};
// constructors and destructor
template<typename T, typename K>
HashTableLP<T, K>::HashTableLP(size_t tableSize) {
int top = sizeof(primes) / sizeof(uint16_t) - 1;
uint16_t modulo = primes[top];
if (tableSize <= modulo) {
while (top > 0 && tableSize < modulo) {
modulo = primes[--top];
}
}
else {
modulo = getPrime(tableSize);
}
initTable(tableSize, modulo);
}
template<typename T, typename K>
HashTableLP<T, K>::HashTableLP(size_t tableSize, uint16_t modulo) {
initTable(tableSize, modulo);
}
template<typename T, typename K>
HashTableLP<T, K>::~HashTableLP() {
for (int i = 0; i < tSize; i++) {
if (table[i] && table[i] != DELETED) {
free(table[i]);
//delete table[i]; in most instances
}
}
free(table);
//delete[] table; would be normal
}
// public methods
template<typename T, typename K>
void HashTableLP<T, K>::insert(K key, T data) {
// no key hash supplied
insert(key, data, HashKey<K>::gethash(key)); // call the overloaded version
}
template<typename T, typename K>
void HashTableLP<T, K>::insert(K key, T data, uint16_t hash) {
hash %= moduloValue;
int deletedSlot = -1;
uint16_t saveHash = hash;
while (table[hash] == DELETED || (table[hash] && table[hash]->key != key)) {
if (table[hash] == DELETED) {
// passed a delete slot
deletedSlot = hash; // save it as usable slot
}
hash = ++hash % moduloValue;
if (hash == saveHash) {
// if the table is full of values and deleted slots
// then we want to stop looking for a duplicate key and
// just use a deleted slot
if (deletedSlot > -1) {
goto BeenAround;
}
else {
return; // no accessible slot left in the table
}
}
}
if (table[hash]) {
delete table[hash];
deletedSlot = -1; // not required
}
BeenAround:
if (deletedSlot > -1) {
table[deletedSlot] = new HashEntry(key, data);
}
else {
table[hash] = new HashEntry(key, data);
}
}
template<typename T, typename K>
T* HashTableLP<T, K>::find(K key) {
return find(key, HashKey<K>::gethash(key));
}
template<typename T, typename K>
T* HashTableLP<T, K>::find(K key, uint16_t hash) {
hash %= moduloValue;
while (table[hash] == DELETED || (table[hash] && table[hash]->key != key)) {
hash = ++hash % moduloValue;
}
if (table[hash]) {
return &table[hash]->data;
}
return NULL;
}
template<typename T, typename K>
void HashTableLP<T, K>::erase(K key) {
erase(key, HashKey<K>::gethash(key));
}
template<typename T, typename K>
void HashTableLP<T, K>::erase(K key, uint16_t hash) {
hash %= moduloValue;
while (table[hash] == DELETED || (table[hash] && table[hash]->key != key)) {
hash = ++hash % moduloValue;
}
if (table[hash]) {
delete table[hash];
table[hash] = (HashEntry*)DELETED;
}
}
template<typename T, typename K>
size_t HashTableLP<T, K>::count() {
size_t ctr = 0;
for (int i = 0; i < tSize; i++) {
if (table[i] && table[i] != DELETED) {
ctr++;
}
}
return ctr;
}
template<typename T, typename K>
typename HashTableLP<T, K>::iterator HashTableLP<T, K>::begin() {
iterator it(this);
return it;
}
template<typename T, typename K>
void HashTableLP<T, K>::clear() {
for (int i = 0; i < tSize; i++) {
if (table[i]) {
if (table[i] != DELETED) {
delete table[i];
}
table[i] = NULL;
}
}
}
// private methods
template<typename T, typename K>
void HashTableLP<T, K>::initTable(size_t tableSize, uint16_t modulo) {
tSize = tableSize;
table = new HashEntry*[tSize];
for (int i = 0; i < tSize; i++) {
table[i] = NULL;
}
moduloValue = modulo;
}
template<typename T, typename K>
uint16_t HashTableLP<T, K>::getPrime(size_t num) {
// returns the largest prime <= num
if (num % 2 == 0) { num--; }
for (uint16_t p = num; p > 2; p -= 2) {
bool f = false;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
f = true;
break;
}
}
if (!f) {
return p;
}
}
return num; // best we can do
}
#endif
HashTableLP.cpp
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "HashTableLP.h"
#include <iostream>
//using namespace std;
int32_t getIsbn(char*);
uint16_t hashISBN(char*);
void test1();
void test2();
void test3();
char TPBooks[][2][32] = { { "The shepherd's crown", "9780857534811" },
{ "Raising steam", "9780857522276" },
{ "Snuff", "9780385619264" },
{ "I shall wear midnight", "9780552555593" },
{ "Unseen academicals", "9780385609340" },
{ "Making money", "9780385611015" },
{ "Thud!", "9780552152679" },
{ "Going postal", "9780552149433" },
{ "Monstrous Regiment", "9780552154314" },
{ "Night watch", "9780552148993" },
{ "Thief of time", "9780552154260" } };
struct tpBook {
char title[32];
// maybe some other data
} book;
struct tpIsbn {
char isbn[14];
// we need a != operator
bool operator!=(tpIsbn& i) {
char *a = &isbn[0], *b = &i.isbn[0];
for (; *a == *b; a++, b++) {
if (*a == '\0' || *b == '\0') {
if (*a == *b) { return false; }
break; // end of one string
}
}
return true;
}
} key;
int main()
{
test1();
std::cout << "End of Test 1\n";
std::cin.get();
test2();
std::cout << "End of Test 2\n";
test3();
std::cout << "End of Test 3\n";
std::cin.get();
return 0;
}
void test1() {
HashTableLP<tpBook, tpIsbn> hashLP(20);
for (int i = 0; i < 11; i++) {
strcpy(book.title, TPBooks[i][0]);
strcpy(key.isbn, TPBooks[i][1]);
hashLP.insert(key, book, hashISBN(key.isbn));
//hashLP.insert(key, book);
}
std::cout << hashLP.count() << " items inserted\n";
for (HashTableLP<tpBook, tpIsbn>::iterator it = hashLP.begin(); it.hasNext(); it++) {
std::cout << it.first.isbn << " " << it.second.title << '\n';
}
tpBook* found = hashLP.find(key, hashISBN(key.isbn));
//tpBook* found = hashLP.find(key);
if (found) {
std::cout << "Found: " << found->title << '\n';
}
else {
std::cout << "Not Found\n";
}
}
void test2() {
HashTableLP<tpBook, int32_t> newLP(20);
for (int i = 0; i < 11; i++) {
strcpy(book.title, TPBooks[i][0]);
strcpy(key.isbn, TPBooks[i][1]);
newLP.insert(getIsbn(key.isbn), book);
}
std::cout << newLP.count() << " items inserted\n";
for (HashTableLP<tpBook, int32_t>::iterator it = newLP.begin(); it.hasNext(); it++) {
std::cout << it.first << " " << it.second.title << '\n';
}
}
void test3() {
std::cout << "In Test 3\n";
HashTableLP<int, int> hashLP(128);
for (int i = 0; i < 120; i++) {
hashLP.insert(i, i, i); // should get average 3 per slot
}
std::cout << hashLP.count() << " items inserted\n";
for (int i = 80; i < 99; i++) {
hashLP.erase(i, i);
}
std::cout << hashLP.count() << " items remaining\n";
hashLP.insert(98, 256, 98);
for (int i = 80; i < 99; i++) {
hashLP.insert(i, i, i); // put em back
}
std::cout << hashLP.count() << " items now\n";
hashLP.insert(80, 256, 80);
for (HashTableLP<int, int>::iterator it = hashLP.begin(); it.hasNext(); it++) {
std::cout << it.first << " " << it.second << '\n';
}
}
int32_t getIsbn(char *isbn) {
char subStr[9];
subStr[8] = '\0';
// drop leading 4 chars and final check digit
isbn += 4;
strncpy(subStr, isbn, 8);
return atol(subStr);
}
uint16_t hashISBN(char *isbn) {
char subStr[9];
subStr[8] = '\0';
// drop leading 4 chars and final check digit
isbn += 4;
strncpy(subStr, isbn, 8);
return (uint16_t)atol(subStr);
}
HashTableLP.ino
#include "HashTableLP.h"
//#include "HashTableSC.h"
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
const char TPBooks[][2][32] = {{"The shepherd's crown", "9780857534811"},
{"Raising steam", "9780857522276"},
{"Snuff", "9780385619264"},
{"I shall wear midnight", "9780552555593"},
{"Unseen academicals", "9780385609340"},
{"Making money", "9780385611015"},
{"Thud!", "9780552152679"},
{"Going postal", "9780552149433"},
{"Monstrous Regiment", "9780552154314"},
{"Night watch", "9780552148993"},
{"Thief of time", "9780552154260"}};
struct tpBook{
char title[32];
// maybe some other data
} book;
struct tpIsbn{
char isbn[14];
// we need a != operator
bool operator!=(const tpIsbn& i) {
char *a = &isbn[0], *b = &i.isbn[0];
for(; *a == *b; a++, b++) {
if(*a == '\0' || *b == '\0') {
if(*a == *b) { return false;}
break; // end of one string
}
}
return true;
}
} key;
void setup() {
Serial.begin(115200);
HashTableLP<tpBook, tpIsbn> hashSC(10);
for (int i = 0; i < 1; i++) {
strcpy_P(book.title, TPBooks[i][0]);
strcpy_P(key.isbn,TPBooks[i][1]);
hashSC.insert(key, book, hashISBN(key.isbn));
Serial << "Inserted\n";
}
Serial << hashSC.count() << " items inserted\n";
for(HashTableLP<tpBook, tpIsbn>::iterator it = hashSC.begin(); it.hasNext(); it++) {
Serial << it.first.isbn << " " << it.second.title << '\n';
}
tpBook* found = hashSC.find(key, hashISBN(key.isbn));
//tpBook* found = hashLP.find(key);
if(found) {
Serial << "Found: " << found->title << '\n';
} else {
Serial << "Not Found\n";
}
hashSC.erase(key, hashISBN(key.isbn));
Serial << hashSC.count() << " items remaining\n";
for(HashTableLP<tpBook, tpIsbn>::iterator it = hashSC.begin(); it.hasNext(); it++) {
Serial << it.first.isbn << " " << it.second.title << '\n';
}
hashSC.~HashTableLP();
}
int32_t getIsbn(char *isbn) {
char subStr[9];
subStr[8] = '\0';
// drop leading 4 chars and final check digit
isbn +=4;
strncpy(subStr, isbn, 8);
return atol(subStr);
}
uint16_t hashISBN(char *isbn){
char subStr[9];
subStr[8] = '\0';
// drop leading 4 chars and final check digit
isbn +=4;
strncpy(subStr, isbn, 8);
return (uint16_t)atol(subStr);
}
HashTableSC.h
#ifndef HashTableSC_h
#define HashTableSC_h
#include "Pair.h"
template<typename T, typename K>
class HashTableSC {
public:
class HashEntry;
class iterator;
HashTableSC(size_t);
HashTableSC(size_t, uint16_t);
~HashTableSC();
void insert(K, T, uint16_t);
iterator begin();
T* find(K, uint16_t);
size_t count();
void erase(K, uint16_t);
void clear();
protected:
HashEntry **table;
size_t tSize;
private:
uint16_t getPrime(size_t);
void initTable(size_t, uint16_t);
uint16_t moduloValue;
uint16_t primes[12] =
{ 7, 13, 19, 31, 47, 59, 61, 97, 127, 251, 509, 1021 };
};
template<typename T, typename K>
class HashTableSC<T, K>::HashEntry {
public:
HashEntry(K key, T data) {
this->key = key;
this->data = data;
next = NULL;
}
K key;
T data;
HashEntry* next;
};
template<typename T, typename K>
class HashTableSC<T, K>::iterator : public pair<K, T> {
public:
iterator(HashTableSC* p) {
parent = p;
nxtIdx = -1;
noMore = false;
currentEntry = NULL;
setNext();
}
bool hasNext() {
return !noMore;
}
iterator &operator++() {
setNext();
return *this;
}
iterator &operator++(int) {
setNext();
return *this;
}
private:
size_t nxtIdx;
HashTableSC* parent;
HashEntry* currentEntry;
bool noMore;
void setNext() {
// needs MOD to check if current entry has a forward link
if (currentEntry && currentEntry->next) {
currentEntry = currentEntry->next;
}
else {
nxtIdx++;
for (; nxtIdx <= parent->tSize; nxtIdx++) {
if (nxtIdx < parent->tSize && parent->table[nxtIdx]) {
break;
}
}
if (nxtIdx < parent->tSize) {
currentEntry = parent->table[nxtIdx];
}
else {
noMore = true;
currentEntry = NULL;
}
}
if (currentEntry) {
setPair(currentEntry);
}
}
void setPair(HashEntry* p) {
this->first = p->key;
this->second = p->data;
}
};
// constructors and destructor
template<typename T, typename K>
HashTableSC<T, K>::HashTableSC(size_t tableSize) {
int top = sizeof(primes) / sizeof(uint16_t) - 1;
uint16_t modulo = primes[top];
if (tableSize <= modulo) {
while (top > 0 && tableSize < modulo) {
modulo = primes[--top];
}
}
else {
modulo = getPrime(tableSize);
}
initTable(tableSize, modulo);
}
template<typename T, typename K>
HashTableSC<T, K>::HashTableSC(size_t tableSize, uint16_t modulo) {
initTable(tableSize, modulo);
}
template<typename T, typename K>
HashTableSC<T, K>::~HashTableSC() {
for (int i = 0; i < tSize; i++) {
if (table[i]) {
if (table[i]->next) {
HashEntry* h = table[i];
HashEntry* n = h->next;
while (n) {
free(h);
h = n;
n = n->next;
}
}
else {
free(table[i]);
//delete table[i]; in most instances
}
}
}
free(table);
//delete[] table; would be normal
}
// public Methods
template<typename T, typename K>
void HashTableSC<T, K>::insert(K key, T data, uint16_t hash) {
hash %= moduloValue;
if (table[hash]) {
// slot taken but might be an update
if (table[hash]->key != key) {
// chain the new entry
HashEntry* h = table[hash];
while (h->next) {
h = h->next;
}
h->next = new HashEntry(key, data); // fill slot with entry
}
else {
free(table[hash]);
table[hash] = new HashEntry(key, data);
}
}
else {
table[hash] = new HashEntry(key, data);
}
}
template<typename T, typename K>
T* HashTableSC<T, K>::find(K key, uint16_t hash) {
hash %= moduloValue;
if (table[hash]) {
// an entry in the hash slot but is it the key we want?
HashEntry* h = table[hash];
while (h && h->key != key) {
h = h->next;
}
if (h) {
return &h->data;
}
}
return NULL;
}
template<typename T, typename K>
void HashTableSC<T, K>::erase(K key, uint16_t hash) {
hash %= moduloValue;
if (table[hash]) {
HashEntry* h = table[hash];
if (h->key != key) {
HashEntry* n = NULL;
while (h && h->key != key) {
n = h;
h = h->next;
}
n->next = h->next; // NULL or next in the chain
}
else {
if (h->next) {
table[hash] = h->next;
}
else {
table[hash] = NULL;
}
}
if (h) {
free(h);
// delete h;
}
}
}
template<typename T, typename K>
size_t HashTableSC<T, K>::count() {
size_t ctr = 0;
for (int i = 0; i < tSize; i++) {
if (table[i]) {
ctr++;
HashEntry* h = table[i];
while (h->next) {
ctr++;
h = h->next;
}
}
}
return ctr;
}
template<typename T, typename K>
typename HashTableSC<T, K>::iterator HashTableSC<T, K>::begin() {
iterator it(this);
return it;
}
template<typename T, typename K>
void HashTableSC<T, K>::clear() {
for (int i = 0; i < tSize; i++) {
if (table[i]) {
if (table[i]->next) {
HashEntry* h = table[i];
HashEntry* n = h->next;
while (n) {
free(h);
h = n;
n = n->next;
}
}
else {
free(table[i]);
// delete table[i]; or delete
}
table[i] = NULL;
}
}
}
// Private methods
template<typename T, typename K>
void HashTableSC<T, K>::initTable(size_t tableSize, uint16_t modulo) {
tSize = tableSize;
table = new HashEntry*[tSize];
for (int i = 0; i < tSize; i++) {
table[i] = NULL;
}
moduloValue = modulo;
}
template<typename T, typename K>
uint16_t HashTableSC<T, K>::getPrime(size_t num) {
// returns the largest prime <= num
if (num % 2 == 0) { num--; }
for (uint16_t p = num; p > 2; p -= 2) {
bool f = false;
for (int i = 2; i < p / 2; i++) {
if (p % i == 0) {
f = true;
break;
}
}
if (!f) {
return p;
}
}
return num; // best we can do as num must be strange
}
#endif
HashTableSC.cpp
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "HashTableSC.h"
#include <iostream>
//using namespace std;
uint16_t hashISBN(char*);
void test1();
void test2();
char TPBooks[][2][32] = { { "The shepherd's crown", "9780857534811" },
{ "Raising steam", "9780857522276" },
{ "Snuff", "9780385619264" },
{ "I shall wear midnight", "9780552555593" },
{ "Unseen academicals", "9780385609340" },
{ "Making money", "9780385611015" },
{ "Thud!", "9780552152679" },
{ "Going postal", "9780552149433" },
{ "Monstrous Regiment", "9780552154314" },
{ "Night watch", "9780552148993" },
{ "Thief of time", "9780552154260" } };
struct tpBook {
char title[32];
// maybe some other data
} book;
struct tpIsbn {
char isbn[14];
// we need a != operator
bool operator!=(tpIsbn& i) {
char *a = &isbn[0], *b = &i.isbn[0];
for (; *a == *b; a++, b++) {
if (*a == '\0' || *b == '\0') {
if (*a == *b) { return false; }
break; // end of one string
}
}
return true;
}
} key;
int main()
{
test1();
std::cout << "End of Test 1\n";
test2();
std::cout << "End of Test 2\n";
std::cin.get();
return 0;
}
void test2() {
HashTableSC<int, int> hashSC(40);
for (int i = 0; i < 120; i++) {
hashSC.insert(i, i, i); // should get average 3 per slot
}
std::cout << hashSC.count() << " items inserted\n";
for(int i = 80; i < 120; i++) {
hashSC.erase(i, i);
}
std::cout << hashSC.count() << " items remaining\n";
for (int i = 80; i < 120; i++) {
hashSC.insert(i, i, i); // put em back
}
std::cout << hashSC.count() << " items now\n";
for (HashTableSC<int, int>::iterator it = hashSC.begin(); it.hasNext(); it++) {
std::cout << it.first << " " << it.second << '\n';
}
}
void test1() {
HashTableSC<tpBook, tpIsbn> hashSC(20);
for (int i = 0; i < 11; i++) {
strcpy(book.title, TPBooks[i][0]);
strcpy(key.isbn, TPBooks[i][1]);
hashSC.insert(key, book, hashISBN(key.isbn));
}
std::cout << hashSC.count() << " items inserted\n";
for (HashTableSC<tpBook, tpIsbn>::iterator it = hashSC.begin(); it.hasNext(); it++) {
std::cout << it.first.isbn << " " << it.second.title << '\n';
}
tpBook* found = hashSC.find(key, hashISBN(key.isbn));
if (found) {
std::cout << "Found: " << found->title << '\n';
}
else {
std::cout << "Not Found\n";
}
hashSC.erase(key, hashISBN(key.isbn));
std::cout << hashSC.count() << " items remaining\n";
for (HashTableSC<tpBook, tpIsbn>::iterator it = hashSC.begin(); it.hasNext(); it++) {
std::cout << it.first.isbn << " " << it.second.title << '\n';
}
}
uint16_t hashISBN(char *isbn) {
char subStr[9];
subStr[8] = '\0';
// drop leading 4 chars and final check digit
isbn += 4;
strncpy(subStr, isbn, 8);
return (uint16_t)atol(subStr);
}
HashTableSC.ino
Code as HashTableLP.ino with very minor changes
Or read the chapter in my book C++ Data Structures with immediate download from Amazon