Dynamic growth of Map

[Trond]

Dynamic map growth
-----------------------------

To have to choose the number of slots beforehand is a big limitation with maps. So I suggest an improvement, which will allow seamless growth of maps. Instead of allowing just a single map, PB maps should create more and bigger maps behind the scenes, when the current map is full, according to the following algorithm:

NewMap creates a list of "blocks", where each block is just a hashmap. Initially, this list has exactly one element with the number of slots specified in the creation (or the default number of slots).

Insertion:

Code: Select all

Get the first block in the list.
If the block is less than 75% (not sure of optimal fullness) full
    insert the item as normal.
else
    add a new block as the first element of the list
    this new block should be bigger than the previous, according to the following growth curve:
    128 -> 256 -> 512 -> 1024 -> 2048 -> 4096 -> ... (the powers of two), until a point where the new blocks no longer grows so fast (it makes no sense to allocate a 2 GB block, if your current is 1 GB, a limit of 1 000 000 or something should be enforced.
    Insert the item in this new block.

Lookup:

Code: Select all

Starting before the start of the list:
repeat
    Get the next block in the list
    check if the key can be located, if yes, return it
    if no:
until past_end_of_list
return: element not found

[Fig]

Clustered hastable ?

[Mistrel]

What you're asking for is a complete replacement of PureBasic's map library to fit a niche requirement. There is no one solution and there are already other issues such as keys being limited to strings.

I think the current implementation is good for most use cases. If you want something to solve a specific problem then you can always write one yourself. Since we don't have a form of generics, PureBasic native containers are pretty limiting anyways.

What problem are you encountering that you need to optimize PureBasic's map?

[NicTheQuick]

When you change the number of blocks you normally have to rehash all the data in the map again because it can move to a different position as before.