Exploring Swift Dictionary’s Implementation
There are multiple ways to store these (key, value) records one of which is open addressing with linear probing which is used by swift’s dictionary implementation.
[…]
Bitmap value of a bucket tells if the key and value in that bucket is valid and initialized or not. If not, then that bucket is called a hole.
[…]
Also note that the end of bucket array is connected to start of the bucket array forming a logical ring. This just means that if you’re at end of the bucket array and you call next method, you’ll end up at begining of the array.
[…]
squeezeHashValue does try to create a good hash by applying some transformation operations.
Also it looks like to keep hashValues different across executions, execution speed was supposed to mixed with hashValue provided by the Key type but its a constant placeholder value for now
[…]
[_NativeDictionaryStorageOwner] was created to keep track of correct reference count for Copy on Write feature, since the storage will be referenced by Dictionary and DictionaryIndex both, reference count will be 2 for the storage but if Dictionary refers this class and reference count of this class is tracked, everything should be fine.
[…]
If a Value has to be removed from the bucket array, we might end up creating a hole which might cause side effect of probing to stop earlier than expected. To take care of that the elements are rearranged at their ideal position.
Previously: Exploring Swift Array’s Implementation, Exposing NSDictionary.
