Hashtable: use dynamic growth and use primes as size

Dynamically increase the hashmap size to not exceed the load factor and
avoid too long chains.

Switch from Separate Chaining to Robin Hood linear probing to improve
cache locality.

Use primes as size to further avoid collisions.

E.g. on a standard kde system the number of entries in the ProcessTable
might be around 650.

1 files changed, 4 insertions, 2 deletions

diff --git a/Hashtable.h b/Hashtable.h
index 15af9e0d..f7d1aae2 100644
--- a/Hashtable.h
+++ b/Hashtable.h
@@ -16,13 +16,13 @@ typedef void(*Hashtable_PairFunction)(hkey_t key, void* value, void* userdata);
 
 typedef struct HashtableItem_ {
    hkey_t key;
+   unsigned int probe;
    void* value;
-   struct HashtableItem_* next;
 } HashtableItem;
 
 typedef struct Hashtable_ {
    unsigned int size;
-   HashtableItem** buckets;
+   HashtableItem* buckets;
    unsigned int items;
    bool owner;
 } Hashtable;
@@ -37,6 +37,8 @@ Hashtable* Hashtable_new(unsigned int size, bool owner);
 
 void Hashtable_delete(Hashtable* this);
 
+void Hashtable_setSize(Hashtable* this, unsigned int size);
+
 void Hashtable_put(Hashtable* this, hkey_t key, void* value);
 
 void* Hashtable_remove(Hashtable* this, hkey_t key);