{"id":1854,"date":"2019-01-03T12:00:00","date_gmt":"2019-01-03T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/hashing-with-open-addressing\/"},"modified":"2026-07-05T03:20:37","modified_gmt":"2026-07-05T01:20:37","slug":"hashing-with-open-addressing","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/hashing-with-open-addressing\/","title":{"rendered":"Hashing With Open Addressing"},"content":{"rendered":"<p><span style=\"font-size: 1rem;\">Today we are going to examine Open Addressing.\u00a0<\/span>Recall that the two methods of resolving collisions in a hash table are:<\/p>\n<ul>\n<li><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hash-tables-hashing-with-chaining\/\">Hashing with Chaining<\/a><\/li>\n<li><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hash-tables-hashing-with-chaining\/\">Open-Addressing<\/a><\/li>\n<\/ul>\n<p>We would cover the following:<\/p>\n<ol>\n<li><a href=\"#t1\">Introduction to Open Addressing<\/a><\/li>\n<li><a href=\"#t2\"><strong>Insertion<\/strong> in Hash Table with Open Addressing<\/a><\/li>\n<li><a href=\"#t3\"><strong>Searching<\/strong> in Hash Table with Open Addressing<\/a><\/li>\n<li><a href=\"#t4\"><strong>Deletion<\/strong> in Hash Table with Open Addressing<\/a><\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-377 size-medium\" src=\"https:\/\/www.kindsonthegenius.com\/wp-content\/uploads\/2020\/09\/Hashing-With-Open-Addressing-300x140.jpg\" alt=\"Hashing With Open Addressing\" width=\"300\" height=\"140\" \/><\/p>\n<h5><strong id=\"t1\">1. Introduction to Hashing with Open Addressing<\/strong><\/h5>\n<p>In Hashing with Open Addressing, all the element are placed in the hash table. Unlike <a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hash-tables-hashing-with-chaining\/\">Hashing With Chaining,<\/a> no external linked list is used. When an element is searched for, we examine the hash table slots one after another until we find the search element or determine that the element is not in the hash table.<\/p>\n<p>In open addressing, the hash table can get completely filled up with the key such that no further keys can be inserted into the table. The consequence is that\u00a0 the load factor (\u03b1\u00a0 = n\/m) will always be at most 1.<\/p>\n<p>The benefit of open-addressing over chaining is that in open addressing, pointers are avoided completely. Instead a sequence of slots to be examined (probed) is computed. Since not using pointers results in additional free memory(and more free slots), we can be sure that that there would be fewer collisions relative to when pointers are used.<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t2\">2. Insertion Into Hash Table With Open Addressing<\/strong><\/h5>\n<p>To insert an element into a hash table with open addressing, we successively probe, or examine the hash table slots one after the other until an empty slot if found to insert the key. However, the sequence of slots to be probed is not sequential as this would require\u00a0\u0398(n) time. The sequence of slots to be examined depends on the particular key we want to insert. To determine this sequence, we use a probe number in addition to the hash function. So what we have is:<\/p>\n<p>h: U x {0, 1, 2, . . . , m-1}\u00a0\u2192 {0, 1, . . . , m-1}<\/p>\n<p>For every key in hashing with open addressing, it is required that the probe sequence be<\/p>\n<p>h(k,0), h(k,1), h(k,2), . . , h(k, m-1)<\/p>\n<p>This should be a permutation of {0, 1, 2, . . . , m-1}<\/p>\n<p>This means that at some point, every hash table slot is eventually examined as a position for a new key before the the table gets completely filled. The pseudocode for Hash-Insert into a hash table with open addressing is given in Listing 1.0. Here, the procedure take as input a hash table T and a key k and returns the slot number where the key is to be stored. It returns an error if the hash table is already full.<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<div style=\"background: #ffffff; overflow: auto; width: auto; border: solid gray; border-width: .1em .1em .1em .8em; padding: .2em .6em;\">\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #333399; font-weight: bold;\">Hash<\/span><span style=\"color: #333333;\">-<\/span><span style=\"color: #333399; font-weight: bold;\">Insert<\/span>(<span style=\"color: #333399; font-weight: bold;\">T<\/span>, k)\n  i <span style=\"color: #000000; font-weight: bold;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>\n  <span style=\"color: #008800; font-weight: bold;\">do<\/span>\n      j <span style=\"color: #000000; font-weight: bold;\">=<\/span> h(k, i)\n      <span style=\"color: #008800; font-weight: bold;\">if<\/span> <span style=\"color: #333399; font-weight: bold;\">T<\/span>[j] <span style=\"color: #333333;\">==<\/span> <span style=\"color: #333399; font-weight: bold;\">NIL<\/span>\n\t  <span style=\"color: #333399; font-weight: bold;\">T<\/span>[j] <span style=\"color: #000000; font-weight: bold;\">=<\/span> k\n\t  return j\n      <span style=\"color: #008800; font-weight: bold;\">else<\/span>\n\t  i <span style=\"color: #000000; font-weight: bold;\">=<\/span> i <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>\n  while i <span style=\"color: #333333;\">&lt;<\/span> m\n <span style=\"color: #ff0000; font-weight: bold;\">error<\/span> <span style=\"background-color: #fff0f0;\">\"hash table full\"<\/span>\n<\/pre>\n<\/div>\n<p>Listing 1.0: Pseudocode for Insert with Open Addressing<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t3\">3. Searching in Hash Table with Open Addressing<\/strong><\/h5>\n<p>The insertion algorithm examines the the hash table for a key k\u00a0 and follows the same probe sequence used for insertion of k. This means that if the search finds an empty slot, then key is not in the table. This is because an empty slot in the sequence means that the key should have been there, but it&#8217;s not). Also note that this is based on the assumption that keys have not being deleted from the table.<\/p>\n<p>The Search procedure take a hash table T and a key k as input. It returns j if it finds a slot that contains k otherwise it returns NIL meaning that that key is not in the table.<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<div style=\"background: #ffffff; overflow: auto; width: auto; border: solid gray; border-width: .1em .1em .1em .8em; padding: .2em .6em;\">\n<pre style=\"margin: 0; line-height: 125%;\"> <span style=\"color: #333399; font-weight: bold;\">Hash<\/span><span style=\"color: #333333;\">-<\/span><span style=\"color: #333399; font-weight: bold;\">Search<\/span>(<span style=\"color: #333399; font-weight: bold;\">T<\/span>, x)\n   i <span style=\"color: #000000; font-weight: bold;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>\n   <span style=\"color: #008800; font-weight: bold;\">do<\/span>\n     j <span style=\"color: #000000; font-weight: bold;\">=<\/span> h(k, i)\n\t <span style=\"color: #008800; font-weight: bold;\">if<\/span> <span style=\"color: #333399; font-weight: bold;\">T<\/span>[j] <span style=\"color: #000000; font-weight: bold;\">=<\/span> k\n\t   return j\n\t <span style=\"color: #008800; font-weight: bold;\">else<\/span>\n\t   i <span style=\"color: #000000; font-weight: bold;\">=<\/span> i <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>\n   while i <span style=\"color: #333333;\">&lt;<\/span> m and <span style=\"color: #333399; font-weight: bold;\">T<\/span>[j] <span style=\"color: #333333;\">!=<\/span> <span style=\"color: #333399; font-weight: bold;\">NIL<\/span>\n   return <span style=\"color: #333399; font-weight: bold;\">NIL<\/span>\n<\/pre>\n<\/div>\n<p>Listing 1.1: Pseudocode for Insert<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t4\">4. Deletion from Hash Table with Open Addressing<\/strong><\/h5>\n<p>Deletion from hash table with open addressing is a little tricky. The reason is this: if we delete a key and mark the slot as NIL, then subsequent searches would not be able to go past this positions (since searches terminate when it finds a NIL slot). So we cannot mark a slot as NIL\u00a0 when an item is deleted.<\/p>\n<p>The solution to this would be to mark the slot with a special value DEL (or DELETED) instead of NIL. Then the <strong>Insert<\/strong> procedure would be modified to treat the the DEL slots as empty. The search procedure would then pass over the DEL slots and continue searching.<\/p>\n<p>In the next lesson, we would examine the following three techniques used to compute the\u00a0 probe sequence namely:<\/p>\n<ul>\n<li>Linear Probing<\/li>\n<li>Quadratic Probing<\/li>\n<li>Double Hashing<\/li>\n<\/ul>\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","protected":false},"excerpt":{"rendered":"<p>Today we are going to examine Open Addressing.\u00a0Recall that the two methods of resolving collisions in a hash table are: Hashing with Chaining Open-Addressing We &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-1854","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1854","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=1854"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1854\/revisions"}],"predecessor-version":[{"id":2023,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1854\/revisions\/2023"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}