{"id":83882,"date":"2021-08-24T09:00:07","date_gmt":"2021-08-24T03:30:07","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=83882"},"modified":"2021-08-24T09:00:07","modified_gmt":"2021-08-24T03:30:07","slug":"hash-table-in-data-structure","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/","title":{"rendered":"Hash Table| Hashing in Data Structure"},"content":{"rendered":"<p>A Hash table is a type of data structure that makes use of the hash function to map values to the key. This data structure stores values in an associative manner i.e. it associates a key to each value. Hash tables make use of array data structures for storing values. The process or technique of mapping keys to the values is known as <strong>Hashing.<\/strong> The purpose of using hash tables as a data structure is to enable faster access.<\/p>\n<h3>What is a Hash Function?<\/h3>\n<p>A hash function is a function that maps keys to one of the values in the hash table. Hash functions return the location\/address where we can store the particular key. We input the key to the hash function and the output is an address. The following diagram depicts the way a hash function operates:<\/p>\n<p>For example, A possible hash function could be<\/p>\n<p style=\"text-align: center\"><strong>h(k) = k mod m<\/strong><\/p>\n<p>Where h(k) denotes the hash function, m denotes the hash table size and k denotes the keys or values.<\/p>\n<h3>Characteristics of an Ideal Hash Function:<\/h3>\n<p>An ideal hash function has the following properties:<\/p>\n<ul>\n<li>Easy to compute<\/li>\n<li>For distinct keys, there must be distinct outputs.<\/li>\n<li>Uniformly distributed keys<\/li>\n<\/ul>\n<h3>Ways to Calculate Hash Functions:<\/h3>\n<p>There are three ways through which we can calculate hash functions:<br \/>\n1. Division method<br \/>\n2. Folding method<br \/>\n3. Mid square method<\/p>\n<h3>What is Hashing?<\/h3>\n<p>Hashing is a technique in which we make use of hash functions to search or calculate the address at which the value is present in the memory. The benefit of using this technique is that it has a time complexity of O(1). We calculate this address and store it in the hash table. We need to take care that the concept of hashing is applicable on distinct keys.<\/p>\n<p>For example, let the hash function be <strong>h(k) = k mod 10<\/strong> where k represents the keys. Let the keys be: 12, 11, 14, 17, 16, 15, 18 and 13. The empty table will look as follows having a table size of 10 and index starting from 0.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image02.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84168\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image02.jpg\" alt=\"Hash Table\" width=\"276\" height=\"396\" \/><\/a><\/p>\n<p>To insert values into the hash table, we make use of the hash function. h(12) = 12mod10 = 2<br \/>\nh(11) = 11mod10 = 1<br \/>\nh(14) = 14mod10 = 4<br \/>\nh(17) = 17mod10 = 7<br \/>\nh(16) = 16mod10 = 6<br \/>\nh(15) = 15mod10 = 5<br \/>\nh(18) = 18mod10 = 8<br \/>\nh(13) = 13mod10 = 3<br \/>\nThe output of h(k) is the index at which we need to place the particular value in the hash table. Thus, after inserting values, the hash table will be:<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image03.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84169\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image03.jpg\" alt=\"hashing in data structure\" width=\"276\" height=\"396\" \/><\/a><\/p>\n<h3>Basic Operations on hash function:<\/h3>\n<p>The basic operations that we can perform on a hash function are:<br \/>\n<strong>1. Search:<\/strong> This operation helps to search an element from a hash table.<br \/>\n<strong>2. Insert:<\/strong> Insert operation is used to insert values into the hash table.<br \/>\n<strong>3. Delete:<\/strong> It is used to delete values from the hash table.<\/p>\n<h3>Collision in Hashing:<\/h3>\n<p>Collision is said to occur when two keys generate the same value. Whenever there is more than one key that point\/map to the same slot in the hash table, the phenomenon is called a collision. Thus, it becomes very important to choose a good hash function so that the hash function does not generate the same index for multiple keys in the hash table.<\/p>\n<p>For example, let keys be<strong> 10, 12, 23, 42, 51<\/strong> and let the hash function be <strong>h(k) = k mod 10<\/strong>.<\/p>\n<p>Then, h(12) = 12mod10 = 2<br \/>\nAnd, h(42) = 42mod10 = 2<\/p>\n<p>Thus, both the keys 12 and 42 are generating the same index. So which value will we store in that particular index as we can store only one of them? This problem is solved by collision resolution techniques.<\/p>\n<h3>Collision Resolution Techniques:<\/h3>\n<p>Collision resolution techniques come into use when a collision has occurred and we need to fix it. Broadly speaking, collision resolution techniques are divided into two categories:<br \/>\n1. Open addressing<br \/>\n2. Separate chaining<\/p>\n<p>Open addressing also has various further categories used to resolve collision problems.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image04.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84170\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image04.jpg\" alt=\"Collision resolution techniques\" width=\"838\" height=\"334\" \/><\/a><\/p>\n<h3>Open Addressing:<\/h3>\n<p>It is one of the collision resolution techniques. In this technique, we store all the keys in the table itself. Therefore, the size of the table has to be greater than or equal to the total number of keys present in the hash function. Open addressing comprises three different categories: Linear probing, quadratic probing and double hashing.<\/p>\n<h4>1. Linear Probing:<\/h4>\n<p>In linear probing, we look for the next empty slot linearly if the allotted slot is filled already. Let <strong>H<\/strong> denote the new hash function that will form after linear probing. Then,<\/p>\n<p style=\"text-align: center\"><strong>H(k, i) = [ h(k) + i] mod m<\/strong><\/p>\n<p>Here,<strong> i<\/strong> is the collision number of the key where i = 0, 1, 2, 3, 4\u2026..<br \/>\nAnd<strong> h(k)<\/strong> is the original hash function.<\/p>\n<p>In simple words, if there is a collision at h(k,3) i.e. some value is already present at that position, then, by linear probing, we will check h(k, 4) and if it is empty, we will place out value at h(k, 4). If h(k, 4) is not empty, again h(k, 5) will be checked until we have found an empty place.<\/p>\n<h5>Primary clustering:<\/h5>\n<p>Linear probing faces the problem of primary clustering. In primary clustering, we need to traverse the whole cluster every time we wish to insert a new value in case of collision.<\/p>\n<p>For example, let the hash function be h(k) = k mod 12 and let the keys be 31, 26, 43, 27, 34, 46, 14, 58, 13, 17, 22. Then,<br \/>\nh(31) = 7<br \/>\nh(26) = 2<br \/>\nh(43) = 7<br \/>\nh(27) = 3<br \/>\nh(34) = 10<br \/>\nh(46) = 10<br \/>\nh(14) = 2<br \/>\nh(58) = 10<br \/>\nh(13) = 1<br \/>\nh(17) = 5<\/p>\n<p>Thus, the collision occurs at 43, 46, 14, 58, 22.<br \/>\nTherefore, H(43, 1) = [h(43) + 1] mod 12 = 8mod12 = 8<\/p>\n<p>H(46, 1) = [h(46)+1]mod12 = 11mod12 = 11<\/p>\n<p>H(14, 1) = [h(14)+1]mod12 = 3mod12 = 3<br \/>\nBut, index 3 is already filled, therefore, we will solve this for i=2.<br \/>\nH(14, 2) = h(14)+2 mod12 = 4<\/p>\n<p>H(58, 1) = [h(58)+1]mod12 = 11<br \/>\nBut 11th index already has a value, so perform hashing for i=2<br \/>\nH(58, 2) = [h(58)+2]mod12 = 0<\/p>\n<p>Next, h(22) has a collision. But slots of index 10, 11, 0, 1, 2, 3, 4, 5 are already filled. This is a<strong> primary cluster<\/strong>.<br \/>\nIn order to find a free slot, we need to get through this group of clusters. This increases the number of comparisons. In the worst case, the number of comparisons could be<strong> m-1<\/strong> where m = size of the hash table.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image05.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84171\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image05.jpg\" alt=\"Primary Clustering in data structure\" width=\"276\" height=\"436\" \/><\/a><\/p>\n<p>To resolve this problem, quadratic probing was introduced.<\/p>\n<h4>2. Quadratic Probing:<\/h4>\n<p>In quadratic probing, the degree of i is 2 where i is the collision number. Thus, in quadratic probing, the hash function formed is:<\/p>\n<p style=\"text-align: center\"><strong>H(k, i) = [h(k) + i2] mod m<\/strong><\/p>\n<p>However, quadratic probing has a drawback. There are chances of secondary clustering in quadratic probing.<\/p>\n<h5>Secondary clustering:<\/h5>\n<p>Let us understand the concept of secondary clustering with the help of an example.<br \/>\nLet keys = 24, 17, 32, 2, 13, 50, 30, 16 and let m = 11 for h(k) = k mod m.<br \/>\nThen,<br \/>\n<strong>h(24) = 2<\/strong><br \/>\nh(17) = 6<br \/>\nh(32) = 10<br \/>\n<strong>h(2) = 2 <\/strong><br \/>\n<strong>h(13) = 2<\/strong><br \/>\nh(50) = 6<br \/>\nh(30) = 8<br \/>\nh(61) = 6<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image06.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84172\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image06.jpg\" alt=\"Secondary Clustering in data structure\" width=\"276\" height=\"412\" \/><\/a><\/p>\n<p>Here, 3 keys are mapping to the same location: 24, 2, 13. Suppose the 2nd index is already filled, then a collision occurs for all three keys.<br \/>\nTo find the next possible value, we will compute H(k) as follows:<br \/>\nH(24, 1) = 3<br \/>\nH(2, 1) = 3<br \/>\nH(13, 1) = 3<\/p>\n<p>If 3rd index is already filled, then we will look for the next possible value.<br \/>\nH(24, 2) = 6<br \/>\nH(2, 2) = 6<br \/>\nH(13, 2) = 6<\/p>\n<p>Similarly, if we check for consequent values, they will produce the same index.<\/p>\n<p>From here, we can conclude that the keys that are mapped to the same memory location follow the same collision resolution path. In this example, the number of free slots is 5 and the number of filled slots are 6. But, every time we are reaching those 6 filled slots. Due to this, we can\u2019t utilize the table effectively, as we can\u2019t reach those free slots.<\/p>\n<h4>3. Double Hashing:<\/h4>\n<p>As the name suggests, in double hashing, we use two hash functions instead of one. If a collision occurs due to one hash function we can make use of the other hash function to find the next free slot.<\/p>\n<p>Let H(k) represent the new hash function formed. Then, its value will be:<\/p>\n<p style=\"text-align: center\"><strong>H(k, i) = [h(k) + i* h\u2019(k)] mod m<\/strong><\/p>\n<p>Here, h(k) = primary hash function<br \/>\nAnd, h\u2019(k) = secondary hash function<\/p>\n<h3>Separate Chaining:<\/h3>\n<p>In separate chaining, we store all the values with the same index with the help of a linked list. This technique functions by maintaining a list of nodes.<\/p>\n<p>For example, let the keys be 100, 200, 25, 125, 76, 86, 96 and let m = 10. Given, h(k) = k mod 10<br \/>\nThen, h(100) = 100 mod 10 = 0<br \/>\nh(200) = 200 mod 10 = 0<br \/>\nh(25) = 25 mod 10 = 5<br \/>\nh(125) = 125 mod 10 = 5<br \/>\nh(76) = 76 mod 10 = 6<br \/>\nh(86) = 86 mod 10 = 6<br \/>\nh(96) = 96 mod 10 = 6<\/p>\n<p>Then, the values will be as follows and the linked list will be maintained.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image07.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-84173\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TechVidvan-Hash-Table-normal-image07.jpg\" alt=\"Separate chaining in data structure\" width=\"817\" height=\"412\" \/><\/a><\/p>\n<p><strong>Drawback of Separate chaining:<\/strong> The use of a linked list requires extra pointers. For n keys, there will be n extra pointers. If the table size is m, then the number of pointers will be (m+n).<\/p>\n<h3>Implementation of hash table in C:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nstruct set\n{\n    int key;\n    int value;\n};\nstruct set *array;\nint capacity = 10;\nint size = 0;\n\nint Hash_function(int key)\n{\n    return (key % capacity);\n}\n\nint check_prime(int n)\n{\n    int i;\n    if (n == 1 || n == 0)\n        return 0;\n    for (i = 2; i &lt; n \/ 2; i++)\n    {\n        if (n % i == 0)\n            return 0;\n    }\n    return 1;\n}\n\nint get_prime(int n)\n{\n    if (n % 2 == 0)\n        n++;\n    while (!check_prime(n))\n        n += 2;\n    return n;\n}\n\nvoid init_array()\n{\n    capacity = get_prime(capacity);\n    array = (struct set *)malloc(capacity * sizeof(struct set));\n    for (int i = 0; i &lt; capacity; i++)\n    {\n        array[i].key = 0;\n        array[i].value = 0;\n    }\n}\n\nvoid insert(int key, int value)\n{\n    int index = Hash_function(key);\n    if (array[index].value == 0)\n    {\n        array[index].key = key;\n        array[index].value = value;\n        size++;\n        printf(\"\\n Key (%d) has been inserted \\n\", key);\n    }\n    else if (array[index].key == key)\n        array[index].value = value;\n    else\n        printf(\"\\n Collision occured  \\n\");\n}\n\nvoid Remove_element(int key)\n{\n    int index = Hash_function(key);\n    if (array[index].value == 0)\n        printf(\"\\n This key does not exist \\n\");\n    else\n    {\n        array[index].key = 0;\n        array[index].value = 0;\n        size--;\n        printf(\"\\n Key (%d) has been removed \\n\", key);\n    }\n}\n\nvoid display()\n{\n    int i;\n    for (i = 0; i &lt; capacity; i++)\n    {\n        if (array[i].value == 0)\n            printf(\"\\n array[%d]: \/ \", i);\n         else\n            printf(\"\\n key: %d array[%d]: %d \\t\", array[i].key, i, array[i].value);\n    }\n}\n\nint size_of_hashtable()\n{\n    return size;\n}\n\nint main()\n{\n    int choice, key, value, n;\n    int c = 0;\n    init_array();\n\n    do\n    {\n        printf(\"1.Insert item in the Hash Table\"\n        \"\\n2.Remove item from the Hash Table\"\n        \"\\n3.Check the size of Hash Table\"\n        \"\\n4.Display a Hash Table\"\n        \"\\n\\n Please enter your choice: \");\n\n        scanf(\"%d\", &amp;choice);\n        switch (choice)\n        {\n            case 1:\n                printf(\"Enter key -:\\t\");\n                scanf(\"%d\", &amp;key);\n                printf(\"Enter data -:\\t\");\n                scanf(\"%d\", &amp;value);\n                insert(key, value);\n                break;\n\n            case 2:\n                printf(\"Enter the key to delete-:\");\n                scanf(\"%d\", &amp;key);\n                Remove_element(key);\n                break;\n\n            case 3:\n                n = size_of_hashtable();\n                printf(\"Size of Hash Table is-:%d\\n\", n);\n                break;\n\n            case 4:\n                display();\n                break;\n    \n            default:\n                printf(\"Invalid Input\\n\");\n        }\n\n        printf(\"\\nDo you want to continue (press 1 for yes): \");\n        scanf(\"%d\", &amp;c);\n\n    } while (c == 1);\n}\n<\/pre>\n<h3>Hash Table Implementation in C++:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;bits\/stdc++.h&gt;\n\nstruct set\n{\n    int key;\n    int value;\n};\nstruct set *array;\nint capacity = 10;\nint size = 0;\n\nint Hash_function(int key)\n{\n    return (key % capacity);\n}\n\nint check_prime(int n)\n{\n    int i;\n    if (n == 1 || n == 0)\n        return 0;\n    for (i = 2; i &lt; n \/ 2; i++)\n    {\n        if (n % i == 0)\n            return 0;\n    }\n    return 1;\n}\n\nint get_prime(int n)\n{\n    if (n % 2 == 0)\n        n++;\n    while (!check_prime(n))\n        n += 2;\n    return n;\n}\n\nvoid init_array()\n{\n    capacity = get_prime(capacity);\n    array = (struct set *)malloc(capacity * sizeof(struct set));\n    for (int i = 0; i &lt; capacity; i++)\n    {\n        array[i].key = 0;\n        array[i].value = 0;\n    }\n}\n\nvoid insert(int key, int value)\n{\n    int index = Hash_function(key);\n    if (array[index].value == 0)\n    {\n        array[index].key = key;\n        array[index].value = value;\n        size++;\n        cout &lt;&lt; \"\\n Key (%d) has been inserted \\n\"&lt;&lt; key;\n    }\n    else if (array[index].key == key)\n        array[index].value = value;\n    else\n        cout &lt;&lt;\"\\n Collision occured  \\n\";\n}\n\nvoid Remove_element(int key)\n{\n    int index = Hash_function(key);\n    if (array[index].value == 0)\n        cout &lt;&lt; \"\\n This key does not exist \\n\";\n    else\n    {\n        array[index].key = 0;\n        array[index].value = 0;\n        size--;\n        cout &lt;&lt; \"\\n Key (%d) has been removed \\n\" &lt;&lt; key;\n    }\n}\n\nvoid display()\n{\n    int i;\n    for (i = 0; i &lt; capacity; i++)\n    {\n        if (array[i].value == 0)\n            cout &lt;&lt;\"\\n array[%d]: \/ \" &lt;&lt; i;\n         else\n            cout &lt;&lt;\"\\n key: %d array[%d]: %d \\t\"&lt;&lt; array[i].key &lt;&lt; i &lt;&lt; array[i].value;\n    }\n}\n\nint size_of_hashtable()\n{\n    return size;\n}\n\nint main()\n{\n    int choice, key, value, n;\n    int c = 0;\n    init_array();\n\n    do\n    {\n        cout &lt;&lt;\"1.Insert item in the Hash Table\"\n        \"\\n2.Remove item from the Hash Table\"\n        \"\\n3.Check the size of Hash Table\"\n        \"\\n4.Display a Hash Table\"\n        \"\\n\\n Please enter your choice: \";\n\n        cin &gt;&gt; choice;\n        switch (choice)\n        {\n            case 1:\n                cout &lt;&lt;\"Enter key -:\\t\";\n                cin &gt;&gt; key;\n                printf(cout &lt;&lt;\"Enter data -:\\t\";\n                cin &gt;&gt; value;\n                insert(key, value);\n                break;\n\n            case 2:\n                cout &lt;&lt; \"Enter the key to delete: \";\n                cin &gt;&gt; key;\n                Remove_element(key);\n                break;\n\n            case 3:\n                n = size_of_hashtable();\n                cout &lt;&lt; \"Size of Hash Table is-:%d\\n\" &lt;&lt; n;\n                break;\n\n            case 4:\n                display();\n                break;\n    \n            default:\n                cout &lt;&lt; \"Invalid Input\\n\";\n        }\n\n        cout &lt;&lt; \"\\nDo you want to continue (press 1 for yes): \";\n        cin &gt;&gt; c;\n\n    } while (c == 1);\n}\n<\/pre>\n<h3>Implementation of hash table in Java:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">import java.util.*; \n\nclass Hash_Table { \n  public static void main(String args[]) \n  {\n  hash_table&lt;Integer, Integer&gt; \n    ht = new hash_table&lt;Integer, Integer&gt;(); \n  \n  ht.put(123, 432); \n  ht.put(12, 2345);\n  ht.put(15, 5643); \n  ht.put(3, 321);\n\n  ht.remove(12);\n\n  System.out.println(ht); \n  } \n} \n<\/pre>\n<h3>Implementation of hash Function\u00a0 in Python:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">hash_table = [[],] * 10\n\ndef check_prime(n):\n    if n == 1 or n == 0:\n        return 0\n\n    for i in range(2, n\/\/2):\n        if n % i == 0:\n            return 0\n    return 1\n\n\ndef get_prime(n):\n    if n % 2 == 0:\n        n = n + 1\n\n    while not check_prime(n):\n        n += 2\n    return n\n\n\ndef hash_function(key):\n    capacity = get_prime(10)\n    return key % capacity\n\n\ndef insert_value(key, value):\n    index = hash_function(key)\n    hash_table[index] = [key, value]\n\ndef remove_value(key):\n    index = hash_function(key)\n    hash_table[index] = 0\n\ninsert_value(123, \"C\")\ninsert_value(432, \"DS\")\ninsert_value(213, \"Python\")\ninsert_value(654, \"Java\")\n\nprint(hash_table)\n\nremove_value(123)\n\nprint(hash_table)\n<\/pre>\n<h3>Applications of Hashing:<\/h3>\n<ul>\n<li>In Symbol table<\/li>\n<li>For constant-time lookup operations and insertion operations<\/li>\n<li>In Domain name Servers(DNS)<\/li>\n<li>In cryptography applications<\/li>\n<\/ul>\n<h3>Conclusion:<\/h3>\n<p>Hashing is a very good technique to reduce or solve the computational problems in O(1) time. However, we need to note that, hashing does produce results in O(1) time. Whenever collisions occur, the time complexity increases. Thus, the best way to make use of hashing techniques and hash tables is by avoiding collisions.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A Hash table is a type of data structure that makes use of the hash function to map values to the key. This data structure stores values in an associative manner i.e. it associates&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":84167,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[4094,4095,4096,4097,4098],"class_list":["post-83882","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-collision-in-hashing","tag-hash-mapping","tag-hash-table","tag-hashing","tag-hashing-in-data-structure"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Hash Table| Hashing in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn what is hash function and ways to calculate it. See what is hashing, basic operations on hash functions, collision in hashing etc.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hash Table| Hashing in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn what is hash function and ways to calculate it. See what is hashing, basic operations on hash functions, collision in hashing etc.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-24T03:30:07+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"13 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hash Table| Hashing in Data Structure - TechVidvan","description":"Learn what is hash function and ways to calculate it. See what is hashing, basic operations on hash functions, collision in hashing etc.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Hash Table| Hashing in Data Structure - TechVidvan","og_description":"Learn what is hash function and ways to calculate it. See what is hashing, basic operations on hash functions, collision in hashing etc.","og_url":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-08-24T03:30:07+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"13 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Hash Table| Hashing in Data Structure","datePublished":"2021-08-24T03:30:07+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/"},"wordCount":1483,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg","keywords":["collision in hashing","Hash mapping","Hash Table","Hashing","hashing in data structure"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/","url":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/","name":"Hash Table| Hashing in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg","datePublished":"2021-08-24T03:30:07+00:00","description":"Learn what is hash function and ways to calculate it. See what is hashing, basic operations on hash functions, collision in hashing etc.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TechVidvan-Hash-Table.jpg","width":1200,"height":628,"caption":"Hash Table in data Structure"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/hash-table-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Hash Table| Hashing in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83882","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83882"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83882\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/84167"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83882"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83882"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83882"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}