# custom hash table<K,T> that take responsibility to assign hashcode/index

## Introduction

I try to create a game engine with component-based architecture.

There are many type game components and different game systems.

For example, the components can be

• Com_HP (health), Com_Physics , Com_Graphics, ...

The systems can be

• Physics_Manager, Graphics_Manager, Binder_Manager, ...

Most systems want to cache relation (map{Key->Value}) that has game component as Key, but the Value can be any type.

For example,

System_Binder : Hashtable<Com_Graphics*,Com_Physics*>.
System_PhysicFactory : Hashtable<Com_Physics*,someInternalData*>.


The components that are cached are only subset of all instance of components of that type.

In other words, not all Com_Graphics instances in the game engine are in the key of the System_Binder's Hashtable.

This problem can be solved easily with some standard library.

However, the retrieve, insert, erase performance is very crucial.
- After test, I found that standard hashmap/hashtable's performance is not good enough.

Therefore, I developed a custom hash table, let's name it AMap.

## The custom HashTable (hashmap)

AMap works almost like general hash table, but it take responsibility to create hashCode (instead of the Key's responsibility), and assign hashCode to a special field of Key.

The special field of Key have to be fed to the AMap, let's call this field as dedicated###.

Here is pseudo code of AMap :-

template<class Key,class Value, int Key::*dedicatedField>class AMap{
Array<pair<Key,Value>> chunk; //like a pool
// Key & Value are usually pointers.
Queue<int> recycleNotUsed; //contain index of "chunk" that is not used
int indexRunner=0; //count from 0 and so on ...
int index; // replace traditional hashCode
if( recycleNotUsed.isEmpty() ){
index = indexRunner++; //count from 0 and so on ...

}else{
index = recycleNotUsed.popFirstElement(); //use recycled key
}
key.dedicatedField = index ; //### assign to the dedicated field
chunk[index ] = {key,value};
//... house keeping about flag that [index] is valid ....
}
void remove(Key key){
recycleNotUsed.pushLastElement(key.dedicatedField );  //###
//... house keeping about flag that the [key.dedicatedField] is invalid ....
}
Value get(Key key){
chunk.get(key.dedicatedField).second; //### so fast
}
//.... other function like iterator, get, set, ....
}


The ### line mark dedicated field. I will show how to feed it to a certain AMap.

When I want to create any AMap, I have to create a dedicated field in the Key class.

// System_Binder.h : This is a field that I want.
AMap<Com_Graphics*,Com_Physics*> graphic_to_physics;

// Com_Graphics.h : I have to add a dedicated field to Com_Graphics.h
int dedicated_System_Binder = -1;  //###

// System_Binder.h : This is what I have to declare
AMap<Com_Graphics*,
Com_Physics*,
&Com_Graphics::dedicated_System_Binder>   //###
graphic_to_physics;


After another test, AMap, compared to std::unorder_map, is astonishing fast (30-40x). Memory is also packed.

## Disadvantage of my custom HashMap

• I have to create 1 dedicated field for any Com_XXX per 1 hash map that use that Com_XXX as a key, as in the example.

• For example, if a system has 2 maps, both use Com_HP as key, I have to create 2 dedicated fields within Com_HP.

• Lower maintainability, e.g.,

if I want to remove the field ...

// System_Binder.h :
AMap<Com_Graphics*,Com_Physics*, ...dedicate...> graphic_to_physics;


... I should also remove this line

// Com_Graphics.h :
int dedicated_System_Binder = -1;

• A limited number of map have to be defined beforehand, because each one has to have a corresponding dedicated variable in the Key class. For example, if there are 2 instances of the same system (e.g. 2 Physic_Manager) , the game will potentially crash.

## Question :

• Is the code good in term of design?

• Are there any better alternatives that provide similar/better performance, but higher maintainability, flexibility and usability?