Dynamic growth of Map
Posted: Fri Jun 15, 2018 2:18 pm
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:
Lookup:
-----------------------------
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.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
