{"id":1855,"date":"2019-01-02T12:00:00","date_gmt":"2019-01-02T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/search-time-under-simple-uniform-hashing\/"},"modified":"2026-07-05T03:20:40","modified_gmt":"2026-07-05T01:20:40","slug":"search-time-under-simple-uniform-hashing","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/search-time-under-simple-uniform-hashing\/","title":{"rendered":"Search Time Under Simple Uniform Hashing"},"content":{"rendered":"<p>We are going to examine the time it takes for successful and unsuccessful search in a hash table where collision is resolved by chaining under<a href=\"https:\/\/www.youtube.com\/watch?v=Fr7Do5P1Tv8&amp;t=85s\" target=\"_blank\" rel=\"noopener\"><strong> Simple Uniform Hashing.<\/strong><\/a><\/p>\n<p><a href=\"https:\/\/www.youtube.com\/watch?v=Fr7Do5P1Tv8&amp;t=85s\" target=\"_blank\" rel=\"noopener\">Video on Simple Uniform Hashing<\/a><br \/>\n<iframe loading=\"lazy\" src=\"https:\/\/www.youtube.com\/embed\/Fr7Do5P1Tv8\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>We would state the Theorem and the try to prove it.<\/p>\n<h5><strong>1.\u00a0 Unsuccessful Search<\/strong><\/h5>\n<p>In a hash table where collision is resolved by chaining, and simple uniform hashing is assumed, then an unsuccessful search takes and average of\u00a0\u0398(1 +\u00a0\u03b1)<\/p>\n<p><strong>Proof:<\/strong> In simple uniform hashing is assumed, then any key k that is not already in the hash table would have equal likelihood of being hashed to any of the m slots in the table. The expected time to search unsuccessfully for a key is the same as the expected time to search from through the length of the list T[h(k)]. And expected length of the list is given as\u00a0\u03b1 or the load factor of the table. Therefore, the expected number of elements to check\u00a0 in an unsuccessful search is\u00a0\u03b1.\u00a0 If we add to time it takes to compute the hash function we would have a total expected time of\u00a0\u0398(1 +\u00a0\u03b1)<\/p>\n<p>&nbsp;<\/p>\n<h5><strong>2. Successful Search<\/strong><\/h5>\n<p>In a hash table where collision is resolved by chaining, and simple uniform hashing is assumed, then the expected time for a successful search is given as\u00a0\u0398(1 +\u00a0\u03b1).<br \/>\n<strong>Proof:<\/strong> In this case where the search is successful, all the items in the list is not equally likely to be searched. The probability that a list is searched is proportional to the number of elements contained in the list<\/p>\n<p>So, we assume that the element being searched\u00a0 for could equally be any of the n elements stored in the table. If the element being searched for is x, then the number of elements checked during the search is one more than the number of elements that appear before x in the linked list containing x. Since new elements are placed in front of a linked list, elements before x in the list were all inserted after x was inserted.<\/p>\n<h6>Expected Number of Elements<\/h6>\n<p>To get the expected number of elements examined, we would take an average\u00a0 over the n elements in the list\u00a0 and 1 plus the expected number of elements inserted into x&#8217;s list after x have been inserted.<\/p>\n<p>Let x<sub>i<\/sub> be the i<sup>th<\/sup> element inserted into the table, for i = 1, 2, . . . , n and k<sub>i<\/sub> = x<sub>i<\/sub>.key. We would then use an indicator random variable to iterate through the keys\u00a0 to check if there is a match. Let For keys k<sub>i<\/sub> and k<sub>j<\/sub>, we define an indicator random variable:<\/p>\n<p>X<sub>ij<\/sub> = I{h(k<sub>i<\/sub>) = h(k<sub>j<\/sub>)}<\/p>\n<p>Under simple uniform hashing, we would have that:<\/p>\n<p>Pr{h(k<sub>i<\/sub>) = h(k<sub>j<\/sub>)} = 1\/m<\/p>\n<p>We can then find this expectation as:<\/p>\n<p>E[X<sub>ij<\/sub>] = 1\/m<\/p>\n<p>This is therefore we can find the expected number of elements examined in a successful search using the derivation given below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-369 size-full\" src=\"https:\/\/www.kindsonthegenius.com\/wp-content\/uploads\/2020\/09\/Hashing-successful-proof.jpg\" alt=\"\" width=\"459\" height=\"619\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Finally we have the total time required for a successful search (which includes the time it takes to compute the hash function )\u00a0 as<\/p>\n<p style=\"text-align: center;\">\u0398(2 +\u00a0\u03b1\/2 &#8211;\u00a0\u03b1\/2n) =\u00a0\u0398(1 +\u00a0\u03b1)<\/p>\n<p>This means that if the number of slots in the hash table is at least proportional to the number of elements stored in the table then we have n = O(m) and it follows that\u00a0\u03b1 = n\/m = O(m)\/m = O(1).<\/p>\n<p>Therefore, this we can see that searching takes constant time on the average. Since insertion of item takes O(1) time in the worst-case, and deletion takes O(1) time in the worst-case, it means that all the operations can be done in O(1) on average assuming simple uniform hashing.<\/p>\n<p>&nbsp;<\/p>\n<h5><strong>Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n<ul>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/skip-lists-and-how-they-work\/\">Skip Lists and How They Work<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/perfect-hashing\/\">Perfect Hashing \u2013 How it Works<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hashing\/\">Linear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hashing-with-open-addressing\/\">Hashing With Open Addressing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/universal-hashing\/\">Universal Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/search-time-under-simple-uniform-hashing\/\">Search Time Under Simple Uniform Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hash-tables-hashing-with-chaining\/\">Hash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/introduction-to-hash-tables-and-direct-addressing\/\">Introduction to Hash Tables and Direct Addressing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/recurrences-in-divide-and-conquer-algorithm\/\">Recurrences in Divide and Conquer Algorithm<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/how-bloom-filters-work\/\">How Bloom Filters Work<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/cuckoo-hashing\/\">How Cuckoo Hashing Works<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/introduction-to-avl-trees-with-examples\/\">Introduction to AVL Trees (With Examples)<\/a><\/strong><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We are going to examine the time it takes for successful and unsuccessful search in a hash table where collision is resolved by chaining under &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"pagelayer_contact_templates":[],"_pagelayer_content":"","footnotes":""},"categories":[35],"tags":[],"class_list":["post-1855","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1855","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/comments?post=1855"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1855\/revisions"}],"predecessor-version":[{"id":2024,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1855\/revisions\/2024"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1855"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1855"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1855"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}