[Feature Request] add ordered, cache-friendly, general-purpose Hashtable

[assyrianic]

Help us help you

• I have checked that my issue doesn't exist yet.

Description

StringMap is good for specific use cases where you need to map data to strings but works poorly in many smaller cases or cases where you want to map non-strings to data. Iterating requires creating a StringMapSnapshot [which could fail in creation] in order to iterate its data and even wanting to iterate a specific piece of data requires creating a StringMapSnapshot. This isn't even mentioning that you need to delete each StringMapSnapshot after creation.

Given this, there is no proper way to store insertion order without requiring something like an ArrayList. Normally this wouldn't be an issue except in cases where you want to iterate by key, in order.

Iterating the keys in order is very difficult, even with an ArrayList since ArrayList can't store variable-length blocks of strings [strings have to be a certain width as given the block size on constructor]. string keys need their length and data tracked which feasibly would require something like an "ArrayListBlock" where you'd have a pool of ArrayLists with blocks of power of 2, basically like a buddy memory allocator but with ArrayLists.

Based on my previous work with OrdMap [obsolete by my personal standards], I am proposing to create a specially designed general-purpose, cache-friendly, type-safe, performant, and naturally-ordered hash table implementation.

the hash table I'm proposing will have the following qualities:

• can search by [str/arr/cell] key or index:

any data = htab.GetValueByStrKey("test");
data = htab.GetValueByCellKey(10);
data = htab.GetValueByArrayKey({ 1,2,3 }, 3);

int len = htab.Len;
for( int i; i < len; i++ ) {
    any data = htab.GetValueByIndex(i);
}

• keys and values are typed and their types can be retrieved for runtime inspection note: the names just a proof of concept, not their planned names.

enum MapType { MapTypeCell, MapTypeStr, MapTypeArray };
MapType map::GetKeyType(int index);

any  map::GetCellKey(int index, bool &res);
int  map::GetStrKeyLen(int index);
bool map::GetStrKey(int index, char[] buffer, int len);
int  map::GetArrKeyLen(int index);
bool map::GetArrKey(int index, any[] buffer, int len);


MapType map::GetValueTypeByStrKey(const char[] key);
MapType map::GetValueTypeByArrKey(const any[] key);
MapType map::GetValueTypeByCellKey(any key);
MapType map::GetValueTypeByIndex(int index);


int  map::GetStrValueLenByStrKey(const char[] key);
bool map::GetStrValueByStrKey(const char[] key, char[] buffer, int len);

int  map::GetStrValueLenByArrKey(const any[] key);
bool map::GetStrValueByArrKey(const any[] key, char[] buffer, int len);

int  map::GetStrValueLenByCellKey(any key);
bool map::GetStrValueByCellKey(any key, char[] buffer, int len);

int  map::GetStrValueLenByIndex(int index);
bool map::GetStrValueByIndex(int index, char[] buffer, int len);

int  map::GetArrValueLenByStrKey(const char[] key);
bool map::GetArrValueByStrKey(const char[] key, any[] buffer, int len);

int  map::GetArrValueLenByArrKey(const any[] key);
bool map::GetArrValueByArrKey(const any[] key, any[] buffer, int len);

int  map::GetArrValueLenByCellKey(any key);
bool map::GetArrValueByCellKey(any key, any[] buffer, int len);

int  map::GetArrValueLenByIndex(int index);
bool map::GetArrValueByIndex(int index, any[] buffer, int len);

• likewise, values can be removed either by [str/arr/cell] key or by index.