Currently, the sparse array grows automatically to accommodate keys larger than the current maximum key size (which is equal to the length of sparse). When inserting a new key-value pair, the length of the sparse array is used to find out if the currently largest key is smaller than the new key. In case the currently largest key is smaller than the new key, the size of the sparse array is increased.
If the largest key is deleted, the size of sparse could be decreased again, so that less memory is used. To decrease the array's size, we need to know the minimum size needed to access all keys that are still in the map. That is, we need to know the size of the largest key in the map after removing the previously largest key.
One could find the largest key by simply scanning the entire map. Alternatively, some kind of linked-list data structure could be used to keep track of the largest keys in sequence.
Currently, the
sparsearray grows automatically to accommodate keys larger than the current maximum key size (which is equal to the length ofsparse). When inserting a new key-value pair, the length of thesparsearray is used to find out if the currently largest key is smaller than the new key. In case the currently largest key is smaller than the new key, the size of thesparsearray is increased.If the largest key is deleted, the size of
sparsecould be decreased again, so that less memory is used. To decrease the array's size, we need to know the minimum size needed to access all keys that are still in the map. That is, we need to know the size of the largest key in the map after removing the previously largest key.One could find the largest key by simply scanning the entire map. Alternatively, some kind of linked-list data structure could be used to keep track of the largest keys in sequence.