{"id":13343,"date":"2016-01-23T11:36:05","date_gmt":"2016-01-23T16:36:05","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=13343"},"modified":"2016-01-23T11:36:05","modified_gmt":"2016-01-23T16:36:05","slug":"exploring-swift-dictionarys-implementation","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2016\/01\/23\/exploring-swift-dictionarys-implementation\/","title":{"rendered":"Exploring Swift Dictionary&rsquo;s Implementation"},"content":{"rendered":"<p><a href=\"http:\/\/ankit.im\/swift\/2016\/01\/20\/exploring-swift-dictionary-implementation\/\">Ankit Aggarwal<\/a>:<\/p>\n<blockquote cite=\"http:\/\/ankit.im\/swift\/2016\/01\/20\/exploring-swift-dictionary-implementation\/\">\n<p>There are multiple ways to store these (key, value) records one of which is open addressing with linear probing which is used by swift&rsquo;s dictionary implementation.<\/p>\n<p>[&#8230;]<\/p>\n<p>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.<\/p>\n<p>[&#8230;]<\/p>\n<p>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&rsquo;re at end of the bucket array and you call next method, you&rsquo;ll end up at begining of the array.<\/p>\n<p>[&#8230;]<\/p>\n<p>squeezeHashValue does try to create a good hash by applying some transformation operations.<\/p>\n<p>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<\/p>\n<p>[&#8230;]<\/p>\n<p>[_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.<\/p>\n<p>[&#8230;]<\/p>\n<p>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.<\/p>\n<\/blockquote>\n<p>Previously: <a href=\"http:\/\/mjtsai.com\/blog\/2016\/01\/08\/exploring-swift-arrays-implementation\/\">Exploring Swift Array&rsquo;s Implementation<\/a>, <a href=\"http:\/\/mjtsai.com\/blog\/2014\/04\/08\/exposing-nsdictionary\/\">Exposing NSDictionary<\/a>.<\/p>","protected":false},"excerpt":{"rendered":"<p>Ankit Aggarwal: There are multiple ways to store these (key, value) records one of which is open addressing with linear probing which is used by swift&rsquo;s dictionary implementation. [&#8230;] 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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[46,571,74,71,901,943],"class_list":["post-13343","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-languagedesign","tag-memory-management","tag-opensource","tag-programming","tag-swift-programming-language","tag-swift-runtime"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13343","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=13343"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13343\/revisions"}],"predecessor-version":[{"id":13344,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13343\/revisions\/13344"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=13343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=13343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=13343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}