{"id":187,"date":"2012-11-05T11:02:16","date_gmt":"2012-11-05T11:02:16","guid":{"rendered":"http:\/\/softwareeveryday.wordpress.com\/?p=187"},"modified":"2018-12-05T08:23:33","modified_gmt":"2018-12-05T08:23:33","slug":"why-should-hashtable-size-be-prime-number","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=187","title":{"rendered":"Why should hashtable size be prime number?"},"content":{"rendered":"<ul>\n<li>Lets say our hashtable size is 100 (which is NOT a prime number).<\/li>\n<li>Say we wish to hash some value x and its multiples 2x, 3x, 4x and so on. If x was = 2 then {2, 4, 6, 8, .., inf} would be our values. Since our hashtable is of size 100, only 50% buckets would be occupied.<\/li>\n<li>If x was = 3 then {3, 6, 9, 12, &#8230;, inf} would be our values. Only 33% would be occupied.<\/li>\n<li>I hope you see the problem there ^. We want a situation where for any key would be spread across buckets in the whole table and not just some % of the table.<\/li>\n<li>To formalize, for any x, your values are going to be spread in s number of buckets (given by the formula below).<br \/>\nspread (s) = table_length \/ GreatestCommonFactor(table_length, x)<\/p>\n<p>table_length = 10<br \/>\nx = 2<\/p>\n<p>s = 10 \/ GreatestCommonFactor(10, 2)<br \/>\ns = 10 \/ 2<br \/>\ns = 5<\/p>\n<p>Meaning values will be spread only in 5 out of 10 buckets (i.e. 50% of the table)\n<\/li>\n<li>We need\u00a0GreatestCommonFactor(table length, x) to be 1 if we want to spread (s) to be table length (meaning map to all buckets in hashtable). So lets make x and table length co-prime<sup>1<\/sup> for which we need to make table length prime!<\/li>\n<\/ul>\n<p>[1] In number theory, two integers a and b are said to be coprime if the only positive integer that divides both of them is 1. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Lets say our hashtable size is 100 (which is NOT a prime number). Say we wish to hash some value x and its multiples 2x, 3x, 4x and so on. If x was = 2 then {2, 4, 6, 8, .., inf} would be our values. Since our hashtable is of size 100, only 50% [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-187","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=187"}],"version-history":[{"count":7,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/187\/revisions"}],"predecessor-version":[{"id":10706,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/187\/revisions\/10706"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}