Friday, 30 October 2015

Dictionary - implementation details in Pharo 4

In Pharo, the elements in a dictionary are physically held in an array.

There is an elements property, and an array property, and a tally property.

The elements property is what we mentally model as the dictionary - a list of Association objects

The array, is a an array of the same Association objects, stored in an array.

This array is a fixed size, larger than the set of associations stored in the elements property.
Any time the array becomes full, it automatically creates a larger array so there are still free slots for future adds.

I'm assuming this is done for two reasons - it's faster to extract and copy a full array into a fresh, larger array than it is to incrementally increase a collection in size by one every time a new item is added.

I suspect also that the positioning of the elements in the array provides a b-tree index for searching for the elements.

No comments:

Post a Comment