4
Nov
0
C++ – Custom Hash container, fast & portable
After Vector, List & Array here is the Hash container for Brainable.
Information
This container need the BList file.
Also it can be optimized if you are using BString but in this case you have to include BString before BHash.
Some part are coming from the Qt container.
Code
#ifndef BHASHMAP_HPP
#define BHASHMAP_HPP
// The BList container from http://berenger.eu/blog/2010/10/27/c-blist-a-faster-list-but-also-the-lighter/
#include "../BList/BList.h"
//
// Some parts of the code have been inspirated
// by the qt framework (nokia copyright)
//
/**
* @author Berenger
* @version 0.5
* @date 24 novembre 2009
* @file BVector.hpp
* @package Utils
* @brief Basic vecctor based on a memory area
*
* This Vector used a memory area, so you have to use it as an array.
* So it is easy and fast to put data at start/end position.
* But it takes a long time to insert or remove value in the center arrea
*
* @must You must give the buffer size if you know it!
*
* @example BHashMap<int, int> hashX;
* @example for(int index = 0 ; index < 20 ; ++index){
* @example //or hashX.add(index,index%5);
* @example hashX[index] = index%5;
* @example }
* @example
* @example for(int index = 0 ; index < 20 ; ++index){
* @example std::cout << index << " " << hashX[index] << '\n';
* @example }
*/
/**
Other hash functions, if you prefer :
int hash32shift(int key, const int in_arrayLenght)
{
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >> 12);
key = key + (key << 2);
key = key ^ (key >> 4);
key = key * 2057; // key = (key + (key << 3)) + (key << 11);
key = key ^ (key >> 16);
return key%in_arrayLenght;
}
int hash2( int key, const int in_arrayLenght)
{
key = (a+0x7ed55d16) + (key<<12);
key = (a^0xc761c23c) ^ (key>>19);
key = (a+0x165667b1) + (key<<5);
key = (a+0xd3a2646c) ^ (key<<9);
key = (a+0xfd7046c5) + (key<<3);
key = (a^0xb55a4f09) ^ (key>>16);
return key%in_arrayLenght;
}
int hash32shiftmult(int key, const int in_arrayLenght)
{
int c2=0x27d4eb2d; // a prime or an odd constant
key = (key ^ 61) ^ (key >> 16);
key = key + (key << 3);
key = key ^ (key >> 4);
key = key * c2;
key = key ^ (key >> 15);
return key%in_arrayLenght;
}
*/
/**
* Current used hash function
*/
int BHashFunction(int in_key, const int in_arrayLenght){
return ((in_key >> 16) + (in_key & 0x0000FFFF)) % in_arrayLenght;
}
///////////////////////////////////////////////////////
// Hash for all types
///////////////////////////////////////////////////////
/** Hash function for another type */
template <class M>
int BHash(const M* key) { return reinterpret_cast<int*>(key); }
/** Hash function for another type */
int BHash(unsigned char key) { return int(key); }
/** Hash function for another type */
int BHash(char key) { return int(key); }
/** Hash function for another type */
int BHash(unsigned short key) { return int(key); }
/** Hash function for another type */
int BHash(short key) { return int(key); }
/** Hash function for another type */
int BHash(int key) { return key; }
/** Hash function for another type */
int BHash(unsigned int key) { return int(key); }
/** Hash function for another type */
int BHash(unsigned long key)
{
if (sizeof(unsigned long) > sizeof(int)) {
return int((key >> (8 * sizeof(int) - 1)) ^ key);
}
else {
return int(key);
}
}
/** Hash function for another type */
int BHash(long key) { return BHash(static_cast<unsigned long>(key)); }
// If BString used
#ifdef BSTRING
/** Hash function for BString type */
int BHash(BString key) {
int result = 0u;
int size = key.lenght();
while(size--){
result |= int((key[size]>96?0x01:0x00)<<(size%sizeof(int)));
}
return result;
}
#endif
///////////////////////////////////////////////////////
// BHashPair
///////////////////////////////////////////////////////
/**
* This class is like a node
*/
template <class Key, class T>
struct BHashPair
{
int h; /**< Real key after hashing */
Key key; /**< The key */
T value; /**< The value */
/** Empty constructor */
BHashPair(){}
/**
* Constructor with parameter
* @param key0
* @param value0
* @param h0
*/
BHashPair(const Key &inKey, const T &inValue, int inH):
h(inH), key(inKey), value(inValue){
}
/** Test if key is equal */
bool hasSameKey(int inH, const Key &inKey) const {
return inH == this->h && inKey == this->key;
}
};
///////////////////////////////////////////////////////
// BHashMap
///////////////////////////////////////////////////////
/**
* The Hash container
*/
template <class Key, class T>
class BHashMap {
protected:
const static int capacity = 1024u; /**< Compiler-time const default size*/
int nbOccupedLists; /**< Number of list used*/
int nbElements; /**< Number of items*/
BList< BHashPair<Key , T> > data[capacity]; /**< Data container */
static T defaultValue; /**< Default Value*/
public:
/** Constructor */
BHashMap(){
this->nbOccupedLists = 0u;
this->nbElements = 0u;
}
/** Destructor */
virtual ~BHashMap(){
}
/** Test if not equal */
bool operator!=(const BHashMap<Key, T> &other) const {
return !(*this == other);
}
/** To know if it is empty */
bool isEmpty() const {
return !this->nbOccupedLists;
}
/** container capacity eg number of lists */
int getCapacity() const {
return this->capacity;
}
/** number of elements */
int count() const{
return this->nbElements;
}
/** To know it a key is used */
bool contains(const Key& key) const;
/** Count a value occurences */
int count(const T& value) const;
/** Add a key-value paire */
void add(const Key& key, const T& value);
/** Equal operator */
BHashMap<Key, T> &operator=(const BHashMap<Key , T> &other);
/** Test if equal */
bool operator==(const BHashMap<Key, T> &other) const;
/** Reset the container */
void clear();
/** Remove a key */
bool remove(const Key& key);
/** Remove all value */
bool removeValue(const T& value);
/** Find and remove this key */
T take(const Key &key, const T &myDefaultValue = defaultValue);
/** Get the first key from a value */
const Key key(const T &value) const{
Key k;
return key(value, k);
}
/** Get the first key from a value withe a default key returned is not found */
const Key key(const T &value, const Key &defaultKey) const;
/** To access element by [] */
T& operator[](const Key &key);
/** To access element by [] */
const T operator[](const Key &key) const;
/** All keys */
BList<Key> keys() const;
/** All keys with this value */
BList<Key> keys(const T &value) const;
/** All values */
BList<T> values() const;
/**
*@brief Iterator class
*/
class Iterator
{
typename BList< BHashPair<Key,T> >::Iterator iter; /**< list iter */
BHashMap* const map; /**< map it is working on */
int index; /**< index */
protected:
/** Constructor */
Iterator() : iter(0),map(0),index(0){
}
Iterator(BHashMap* const inMap) : iter(0),map(inMap),index(0){
}
public:
/** Constructor */
Iterator(const Iterator& other) :
iter(other.iter),map(other.map),index(other.index){
}
/** Equality */
Iterator& operator=(const Iterator& other){
iter = other.iter;
map = other.map;
index = other.index;
return *this;
}
/** pre++ */
Iterator &operator++() {
if(iter != map->data[BHashMap::capacity - 1].end()){
++iter;
if(iter.end() && index != BHashMap::capacity - 1){
while( index < BHashMap::capacity - 1 && !map->data[++index].size()){
}
iter = map->data[index].begin();
}
}
return *this;
}
/** post++ */
Iterator operator++(int) {
Iterator r = *this;
operator++();
return r;
}
/** pre-- */
Iterator &operator--() {
--iter;
if(iter.begin()){
int indexDec = index - 1;
while( 0 <= indexDec && !map->data[indexDec].size()){
--indexDec;
}
if(indexDec >= 0){
index = indexDec;
iter = map->data[index].constEnd() - 1;
}
}
return *this;
}
/** post-- */
Iterator operator--(int) {
Iterator r = *this;
operator--();
return r;
}
/** adding a number to progress */
Iterator operator+(int j) const
{
Iterator r = *this;
if (j > 0) while (j--) ++r;
else while (j++) --r;
return r;
}
/** reducing a number to progress */
Iterator operator-(int j) const {
return operator+(-j);
}
/** adding a number to progress */
Iterator &operator+=(int j) {
return *this = *this + j;
}
/** redugin a number to progress */
Iterator &operator-=(int j) {
return *this = *this - j;
}
/** to know if we are at the end */
bool isEnd(){
return index == BHashMap::capacity - 1
&& iter == this->data[BHashMap::capacity - 1].end();
}
/** current element key */
const Key &key() const {
return (*iter).key;
}
/** current element value */
const T &value() const {
return (*iter).value;
}
/** current element value */
T &operator*() const {
return (*iter).value;
}
/** current element value */
T *operator->() const {
return &(*iter).value;
}
/**
*@brief test equality (if data are equal)
*@return true if equal
*/
bool operator==(const Iterator &o) const {
return index == o.index && map == o.map && iter == o.iter;
}
/**
*@brief test different (if data are different)
*@return true if different
*/
bool operator!=(const Iterator &o) const {
return !((*this) == o);
}
// Need to be friend of
friend class BHashMap;
};
class ConstIterator
{
typename BList< BHashPair<Key,T> >::ConstIterator iter;/**< list iter */
const BHashMap* const map; /**< map it is working on */
int index; /**< index */
protected:
/** Constructor */
ConstIterator() : iter(0),map(0),index(0){
}
/** Constructor */
ConstIterator(const BHashMap* const inMap) : iter(0),map(inMap),index(0){
}
public:
/** Constructor */
ConstIterator(const ConstIterator& other) :
iter(other.iter),map(other.map),index(other.index){
}
/** equal operator */
ConstIterator& operator=(const ConstIterator& other){
iter = other.iter;
map = other.map;
index = other.index;
return *this;
}
/** ++pre */
ConstIterator &operator++() {
if(iter != map->data[BHashMap::capacity - 1].constEnd()){
++iter;
if(iter.end() && index != BHashMap::capacity - 1){
while( index < BHashMap::capacity - 1 && !map->data[++index].size()){
}
iter = map->data[index].constBegin();
}
}
return *this;
}
/** post++ */
ConstIterator operator++(int) {
Iterator r = *this;
operator++();
return r;
}
/** --pre */
ConstIterator &operator--() {
--iter;
if(iter.begin()){
int indexDec = index - 1;
while( 0 <= indexDec && !map->data[indexDec].size()){
--indexDec;
}
if(indexDec >= 0){
index = indexDec;
iter = map->data[index].constEnd() - 1;
}
}
return *this;
}
/** post-- */
ConstIterator operator--(int) {
Iterator r = *this;
operator--();
return r;
}
/** progressing */
ConstIterator operator+(int j) const
{
Iterator r = *this;
if (j > 0) while (j--) ++r;
else while (j++) --r;
return r;
}
ConstIterator operator-(int j) const {
return operator+(-j);
}
ConstIterator &operator+=(int j) {
return *this = *this + j;
}
ConstIterator &operator-=(int j) {
return *this = *this - j;
}
/** To know if we are at the ending position */
bool isEnd(){
return index == BHashMap::capacity - 1
&& iter == this->data[BHashMap::capacity - 1].end();
}
/** current element key */
const Key &key() const {
return (*iter).key;
}
/** current element value */
const T &value() const {
return (*iter).value;
}
/** current element value */
const T &operator*() const {
return (*iter).value;
}
/** current element value */
const T *operator->() const {
return &(*iter).value;
}
/**
*@brief test equality (if data are equal)
*@return true if equal
*/
bool operator==(const ConstIterator &o) const {
return index == o.index && map == o.map && iter == o.iter;
}
/**
*@brief test different (if data are different)
*@return true if different
*/
bool operator!=(const ConstIterator &o) const { return !((*this) == o); }
// Need to be friend of
friend class BHashMap;
};
/** need to be friend */
friend class Iterator;
/** need to be friend */
friend class ConstIterator;
/** begin Iterator */
Iterator begin() {
if(this->nbElements){
Iterator iter;
iter.map = this;
iter.index = 0;
while(iter.index < BHashMap::capacity - 1
&& !this->data[iter.index].size()){
++iter.index;
}
iter.iter = this->data[iter.index].begin();
return iter;
}
else{
return end();
}
}
/** end Iterator */
Iterator end() {
Iterator iter(this);
iter.iter = this->data[BHashMap::capacity - 1].end();
iter.index = this->capacity - 1;
return iter;
}
/** const begin Iterator */
ConstIterator constBegin() const{
if(this->nbElements){
ConstIterator iter(this);
iter.index = 0;
while(iter.index < BHashMap::capacity - 1
&& !this->data[iter.index].size()){
++iter.index;
}
iter.iter = this->data[iter.index].constBegin();
return iter;
}
else{
return constEnd();
}
}
/** const end Iterator */
ConstIterator constEnd() const{
ConstIterator iter(this);
iter.iter = this->data[BHashMap::capacity - 1].constEnd();
iter.index = this->capacity - 1;
return iter;
}
};
///////////////////////////////////////////////////////
// Outline methods
///////////////////////////////////////////////////////
/** does it contains the key */
template <class Key, class T>
bool BHashMap<Key, T>::contains(const Key& key) const{
if(this->nbElements){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::ConstIterator iter(this->data[position].constBegin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ) return true;
}
}
}
return false;
}
/** add a key/value */
template <class Key, class T>
void BHashMap<Key, T>::add(const Key& key, const T& value){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::ConstIterator iter(this->data[position].constBegin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ){
(*iter).value = value;
return;
}
}
}
else{
++this->nbOccupedLists;
}
this->data[position].pushFront( BHashPair<Key , T>(key, value, position) );
++this->nbElements;
}
/** equal */
template <class Key, class T>
BHashMap<Key, T> & BHashMap<Key, T>::operator=(const BHashMap<Key , T> &other){
if(&other != this){
for(int index = 0u ; index < this->capacity ; ++index ){
if(other.data[index].size()) this->data[index] = other.data[index];
else if(this->data[index].size()) this->data[index].clear();
}
this->nbOccupedLists = other.nbOccupedLists;
this->nbElements = other.nbElements;
}
}
/** test equality */
template <class Key, class T>
bool BHashMap<Key, T>::operator==(const BHashMap<Key, T> &other) const{
if(this->nbOccupedLists != other.nbOccupedLists || this->nbElements != other.nbElements) return false;
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size() != other.data[index].size()) return false;
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
if( !other.data[index].contains(*iter) ) return false;
}
}
return true;
}
/** clear data */
template <class Key, class T>
void BHashMap<Key, T>::clear(){
for(int index = 0u ; index < this->capacity && this->nbOccupedLists-- ; ++index ){
this->data[index].clear();
}
this->nbOccupedLists = 0u;
this->nbElements = 0u;
}
/** remove a value from key */
template <class Key, class T>
bool BHashMap<Key, T>::remove(const Key& key){
if(this->nbElements){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[position].begin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ){
if(this->data[position].size() == 1) --this->nbOccupedLists;
--this->nbElements;
this->data[position].erase(iter);
return true;
}
}
}
}
return false;
}
/** remove a key/value from value */
template <class Key, class T>
bool BHashMap<Key, T>::removeValue(const T& value){
bool ret = false;
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
if( (*iter).value == value ){
iter = this->data[index].erase(iter);
--this->nbElements;
ret = true;
}
}
if(!this->data[index].size()) --this->nbOccupedLists;
}
}
}
return ret;
}
/** take element */
template <class Key, class T>
T BHashMap<Key, T>::take(const Key &key, const T &myDefaultValue){
if(this->nbElements){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[position].begin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ){
T ret = (*iter).value;
this->data[position].erase(iter);
if(!this->data[position].size()) --this->nbOccupedLists;
--this->nbElements;
return ret;
}
}
}
}
return myDefaultValue;
}
/** get first key from value */
template <class Key, class T>
const Key BHashMap<Key, T>::key(const T &value, const Key &defaultKey) const{
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
if( (*iter).value == value ){
return (*iter).key;
}
}
}
}
}
return defaultKey;
}
template <class Key, class T>
T& BHashMap<Key, T>::operator[](const Key &key){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->nbElements){
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[position].begin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ) return (*iter).value;
}
}
else{
++this->nbOccupedLists;
}
}
++this->nbElements;
this->data[position].pushFront( BHashPair<Key , T>(key, T(), position) );
return this->data[position].front().value;
}
template <class Key, class T>
const T BHashMap<Key, T>::operator[](const Key &key) const{
if(this->nbElements){
const int position = BHashFunction(BHash(key), this->capacity);
if(this->data[position].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[position].begin()); !iter.end() ; ++iter){
if( (*iter).hasSameKey(position, key) ) return (*iter).value;
}
}
}
return defaultValue;
}
/** count value occurence */
template <class Key, class T>
int BHashMap<Key, T>::count(const T& value) const{
int count = 0u;
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
if( (*iter).value == value ){
++count;
}
}
}
}
}
return count;
}
/** get all keys */
template <class Key, class T>
BList<Key> BHashMap<Key, T>::keys() const{
BList<Key> lkeys;
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
lkeys.pushBack((*iter).key);
}
}
}
}
return lkeys;
}
/** get all keys with this value */
template <class Key, class T>
BList<Key> BHashMap<Key, T>::keys(const T &value) const{
BList<Key> allKeys;
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
if( (*iter).value == value ){
allKeys.pushBack((*iter).key);
}
}
}
}
}
return allKeys;
}
/** get all values */
template <class Key, class T>
BList<T> BHashMap<Key, T>::values() const{
BList<T> lvalues;
if(this->nbElements){
for(int index = 0u ; index < this->capacity ; ++index ){
if(this->data[index].size()){
for(typename BList< BHashPair<Key, T> >::Iterator iter(this->data[index].begin()); !iter.end() ; ++iter){
lvalues.pushBack((*iter).value);
}
}
}
}
return lvalues;
}
#endif
Example
#include "BHashMap.h"
#include <time.h>
#include <iostream>
#include <cstdlib>
void Print(const BHashMap<int, unsigned int>& hashX){
BHashMap<int, unsigned int>::ConstIterator iter(hashX.constBegin());
BHashMap<int, unsigned int>::ConstIterator iterEnd(hashX.constEnd());
for(; iter != iterEnd ; ){
//--iterEnd;
//std::cout<< iterEnd.key() << " " << iterEnd.value() << "\n";
std::cout<< iter.key() << " " << iter.value() << "\n";
++iter;
}
}
int main(){
srand ( time(NULL) );
BHashMap<int, unsigned int> hashX;
for(unsigned int index = 0 ; index < 1024 ; ++index){
int key = int(36000 * (rand()/float(RAND_MAX)));
hashX[key] = index;
}
hashX.contains(55);
Print(hashX);
return 0;
}
Download
Enjoyed reading this post?
Subscribe to the RSS feed and have all new posts delivered straight to you.
Subscribe to the RSS feed and have all new posts delivered straight to you.
