Refinement for HashMap

[ZSShen]

I'd like to propose the new set of operation interfaces for HashMap container.

• Container Status Code:
  • SUCC: Indicate that the operation is finished successfully.
  • END: Indicate that the iterator locates at the end of the map.
  • ERR_NOINIT: Indicate that the container has not initialized.
  • ERR_NOMEM: Indicate that there is no capacity for key value pair insertion.
  • ERR_NOKEY: Indicate that the map entry cannot be found via the given key.
• Operation Interface:
  • int HashMapPut (HashMap*, Key, Value)
  • return: SUCC, ERR_NOINIT, ERR_NOMEM
  • int HashMapGet (HashMap, Key, Value)
  • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapFind (HashMap*, Key)
  • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapRemove (HashMap*, Key)
  • return: SUCC, ERR_NOINIT, ERR_NOKEY
  • int HashMapSize (HashMap*)
  • return: size, ERR_NOINIT
  • int HashMapSetHash (HashMap, int()(Key))
  • return: SUCC, ERR_NOINIT
  • int HashMapSetCompare (HashMap, int()(Key, Key))
  • return: SUCC, ERR_NOINIT
  • int HashMapSetCleanKey (HashMap, void()(Key))
  • return: SUCC, ERR_NOINIT
  • int HashMapSetCleanValue (HashMap, void()(Value))
  • return: SUCC, ERR_NOINIT
  • int HashMapHasNext (HashMap*)
  • return: SUCC, END, ERR_NOINIT
  • int HashMapNext (HashMap, Pair)
  • return: SUCC, END, ERR_NOINIT

Here is the simple draft, but there are still some issues to be solved: Do users really need to care for the error return code? Or, should we simply return the NULL for users when there is no memory capacity or the key cannot be found?

[rcarbone]

Hi ZongXian, please find my draft of a proposed API. It does not include return codes. A boolean should be enough.

/* Calculate hash of a table entry / typedef int ( HashMapHash) (void * key);

/* Compare a table entry with a possible entry / typedef int ( HashMapCmp) (void * obj1, void * obj2);

/* Cleanup function called whenever a live element is removed from the hash table / typedef void ( HashMapSetCleanKey) (void * key);

/* The constructor for HashMap / HashMap \ HashMapInit (void);

/* The destructor for HashMap / void HashMapDeinit (HashMap \ map);

/* Return the number of stored key/value pairs / unsigned HashMapSize (HashMap \ map);

/* Insert a key/value pair into the map / bool HashMapPut (HashMap * map, void * key, void \ val);

/* Delete the key/value pair corresponding to the designated key / bool HashMapRemove (HashMap * map, void \ key);

/* Retrieve the value corresponding to the designated key / void * HashMapGet (HashMap * map, void \ key);

/* Check if the map contains the designated key / bool HashMapFind (HashMap * map, void \ key);

/* Get first key/value pair / void * HashMapFirst (HashMap \ map);

/* Get next key/value pair / void * HashMapFirst (HashMap \ map);

/* Set the custom hash function / bool HashMapSetHash (HashMap \ map, R_HashMapHash hash);

/* Set the custom keys compare function / bool HashMapSetCompare (HashMap \ map, HashMapCmp cmp);

/* Set the custom key/value pair resource clean method / bool HashMapSetDestroy (HashMap \ map, HashMapSetCleanKey rm);

Bye /rocco

[ZSShen]

Hi Rocco,

I reduce the error return code and put the status in Linux errno. Thus users do not have to care about the container status for each operation. But for debugging purpose, they can check errno for detailed information.

// Calculate the hash of the given key.
typedef int (*HashMapHash) (void*);

// Compare the equality of two keys.
typedef int (*HashMapCompare) (void*, void*);

// Cleanup function called whenever the key of a live entry is removed from the table. 
typedef void (*HashMapCleanKey) (void*);

// Cleanup function called whenever the value of a live entry is removed from the table.
typedef void (*HashMapCleanValue) (void*);

// Constructor of HashMap.
HashMap* HashMapInit();

// Destructor of HashMap.
void HashMapDeinit(HashMap*);

// Get the number of stored key/value pairs.
unsigned HashMapSize(HashMap*);

// Insert a key/value pair into the map.
bool HashMapPut(HashMap*, void*, void*);

// Delete the key/value pair corresponding to the designated key.
bool HashMapRemove(HashMap*, void*);

// Retrieve the value corresponding to the designated key.
void* HashMapGet(HashMap*, void*);

// Check if the map contains the designated key.
bool HashMapFind(HashMap*, void*);

// Initialize the map iterator. 
void HashMapFirst(HashMap*);

// Get the kay/value pair pointed by the iterator and move the iterator to the next entry.
// When the iterator reaches the end, return NULL.
void* HashMapNext(HashMap*);

// Set the custom hash function.
void HashMapSetHash(HashMap*, HashMapHash);

// Set the custom key comparison function.
void HashMapSetCompare(HashMap*, HashMapCmp);

// Set the custom key clean function.
void HashMapSetCleanKey(HashMap*, HashMapCleanKey);

// Set the custom value clean function.
void HashMapSetCleanKey(HashMap*, HashMapCleanValue);

Based on this version, I'll finish the refinement ASAP.

Regards, ZongXian.

[rcarbone]

ok. but please do not forget that is is just a simple idea maybe not the best API. If you prefer a stable implementation we need more investigation.

ciao /rocco

[ZSShen]

Hi Rocco,

The listed APIs are frequently used map operations. Any ideas to enrich them?

And you're right. The quality of hash based containers are highly related to the mathematical model. For example, the bucket loading factor, the bucket size, and the hash function. It really needs more time to fine tune those parameters. Can we refer to some empirical result?

Regards, ZongXian.

[rcarbone]

Hi ZongXian, please find attacched 2 text files with the results of running my Hash Table Machine over 21 different hash table implementations on a Debian x64 and Debian x86 systems.

My implementation is so far to be completed but I am working on it.

Do not hesitate to contact me if you need more.

ciao /rocco htm-results.tar.gz