{"id":415773,"date":"2024-06-30T00:34:12","date_gmt":"2024-06-30T00:34:12","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=415773"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=415773","title":{"rendered":"<span>Hashing<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>It is an efficient searching technique. Searching is a widespread operation on any data structure. Hashing is used to search specific records from a large domain of records. If we can efficiently search a record out of\u00a0 many records, we easily perform different operations on that data. Hashing is storing and retrieving data from the database in the order of O(1) time. We can also call it the mapping technique because we try to map smaller values into larger values by using hashing.<\/p>\n<p>Following are the significant terminologies related to hashing<\/p>\n<p><strong>Search Key<\/strong><\/p>\n<p>In the database, we usually perform searching with the help of some keys. These keys are called search keys. If we take the student data, then we search by some registration number. This registration number is a search key. We have to put the search keys in hash tables.<\/p>\n<p><strong>Hash Table<\/strong><\/p>\n<p>It is a data structure that provides us the methodology to store data properly. A hash table is shown below. It is similar to an array. And we have indexes in it also like an array.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/e4d\/eca\/987\/e4deca9879021ee26279dc47ce896609.jpg\" width=\"124\" height=\"266\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e4d\/eca\/987\/e4deca9879021ee26279dc47ce896609.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p><strong>Hash Function<\/strong>  <\/p>\n<p>When we perform searching, inserting, or deleting some data from it, we don\u2019t need to scan the whole table. With the help of a hash function, we will perform it with the order of O(1) time. There are different hash functions such as:<\/p>\n<ul>\n<li>\n<p>K mod 10<\/p>\n<\/li>\n<li>\n<p>K mod n<\/p>\n<\/li>\n<li>\n<p>Mid Square<\/p>\n<\/li>\n<li>\n<p>Folding Method   <\/p>\n<\/li>\n<\/ul>\n<p>\u2018K mod 10\u2019 and \u2018K mod n\u2019 are the most widely used methods.\u00a0<\/p>\n<p>Suppose we have a number 24 and hash function \u2018K mod 10\u2019.With the help of the hash function, we will map 24 in the hash table. For this purpose, we can put K is equal to 24 so:<\/p>\n<p><em>                                                                       24 mod 10 = 4<\/em>  <\/p>\n<p>So we can place 24 at index 4 in the hash table. Then for 52 number   <\/p>\n<p><em>                                                                       52 mod 10 = 2<\/em>  <\/p>\n<p>52 will go to index 2 location. Next for number 91  <\/p>\n<p><em>                                                                       91 mod 10 = 1<\/em>  <\/p>\n<p>So, 91 will be placed at index 1 in the table. Then finally for 67  <\/p>\n<p><em>                                                                       67 mod 10 = 7<\/em>  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/773\/173\/d61\/773173d619a3037ec848c03a2966ded9.jpg\" width=\"126\" height=\"268\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/773\/173\/d61\/773173d619a3037ec848c03a2966ded9.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>A hash table uses two components:  <\/p>\n<ul>\n<li>\n<p>Hash function<\/p>\n<\/li>\n<li>\n<p>Bucket Array<\/p>\n<\/li>\n<\/ul>\n<p>For an element key pair, the hash function calculates some value based on a key. A hash function is a function with a key as an input parameter. A hash function will give us two parts:  <\/p>\n<p><strong>Hash Codes<\/strong>  <\/p>\n<p>In this, we assign an integer to the key. It is going to map the key to some integer.  <\/p>\n<p><strong>Compression Map<\/strong>  <\/p>\n<p>It will convert the integer, or rather it will map the integer which we have received from the hash code to an integer in the range 0 to n-1. Once we have the hash function of the key, we would first receive an integer, and then map that integer to 0 to n-1. So the outcome of the hash code or the outcome of the hash function will be an integer in the range 0 to the n-1. This integer depends on the key of the input element.<\/p>\n<p>In the bucket array, we are going to store the element in an array of hash functions of the key. So once we will receive an integer in the range 0 to n minus 1.So, we will store the element in an array of not just the key but the array of hash function of the key. So, once we do this, the keys no longer have to be integers. Also, we don\u2019t need to know the range of keys because we are going to map it into a range which is provided by us.<\/p>\n<p><strong>Hash Code<\/strong>  <\/p>\n<p>Hash code is a function that converts a key to an integer. So it&#8217;s going to convert a key of any type to an integer.<\/p>\n<p>Following are some properties of a good hash code:<\/p>\n<ul>\n<li>\n<p>It will minimize collisions. It means that if we are given two keys that are different, their hash codes should also be different. So if two keys say \u2018K1\u2019 does not equal \u2018K2\u2019.<\/p>\n<\/li>\n<\/ul>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                      <em>K1 \u2260K2<\/em><\/p>\n<p>        It implies that the hash code of key 1 should also not equal to the hash code of key 2.If two keys are a map to the same hash code, then we say a collision has occurred. We don\u2019t want this. We want different hash codes for different keys. So we want to minimize collisions.<\/p>\n<ul>\n<li>\n<p>A good hashcode should be uniform. If we have a key \u2018K1\u2019 and that is equal to key \u2018K2\u2019.<\/p>\n<\/li>\n<\/ul>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                         <em>K1 = K2<\/em><\/p>\n<p>       Then we don\u2019t need different answers for hash code. Because for the same value of the key, if we run our hash code, then we should always get the same value of the hash code. So if both keys are equal, then the hash code of Key 1 has to equal the hash code of Key 2.<\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                  <em>hash(K1) = hash(K2)<\/em><\/p>\n<p><strong>Hash Code Map Example<\/strong>  <\/p>\n<p><strong><em>Memory Address<\/em><\/strong>  <\/p>\n<p>In this, we are going to interpret the memory address of the key as the hash code. So we are going to take the memory address of the key as the hash code of the key.<\/p>\n<p>Let&#8217;s take an example of it. We have a key 1, and this is at a memory address of 5000. Then we have key 2, and this is at memory address 5010.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/6f6\/4b5\/39f\/6f64b539fa0bd75b83fb24db17a8e242.jpg\" width=\"315\" height=\"165\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6f6\/4b5\/39f\/6f64b539fa0bd75b83fb24db17a8e242.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p><em>                                                                  Hash(K1) = 5000<\/em><\/p>\n<p><em>                                                                 Hash(K2) =\u00a0 5010<\/em><\/p>\n<p>It can be seen that the key, whatever the data type it may be, has arrived at an integer that maps to that data.<\/p>\n<p><em>Disadvantage<\/em><\/p>\n<p>The disadvantage of this hash code is that this is not uniform.<\/p>\n<p><strong><em>Integer Cast<\/em><\/strong>  <\/p>\n<p>It is a method of mapping to an integer. In this, whatever the data type of the key may be, typecast it to an integer. So if we have a string and we typecast a character of that string, it is going to return an ASCII value to us. And thereby, we will get an integer.<\/p>\n<p><em>Disadvantage<\/em><\/p>\n<p>Its disadvantage is that for data types like double or float, we encounter a loss of data. And a lot of collisions will occur in this method.<\/p>\n<p><strong><em>Component Sum<\/em><\/strong>  <\/p>\n<p>It is a type of hash code in which the partition bits of the key into fixed-length components. Suppose we have a float or a double that\u2019s going to be 64 bits for us. We will partition them into a fixed bit component. So we will partition these 64 bits into two 32 bits. Then we will add these two 32 bits to get a 32-bit hash code after ignoring overflow.  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/79a\/17f\/2eb\/79a17f2ebee86d7612823fb992e30f7b.jpg\" width=\"492\" height=\"195\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/79a\/17f\/2eb\/79a17f2ebee86d7612823fb992e30f7b.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Suppose we use a string case. And We have a key that is equal to the string \u2018NAME\u2019. So, in this case, we will not directly typecast this to an integer. We will divide this into four 32 bit segments. Then we will add these values. For each of these values, we take ASCII values of each of these characters. Then we will get the final hash code by adding each of these values.<\/p>\n<p><em>                                                                    Key = \u2018NAME\u2019<\/em>  <\/p>\n<p><em>                                                   ASC(N) + ASC(A) + ASC(M) + ASC(E)<\/em> <\/p>\n<p><em>                                                               Hash Code (Key)\u00a0 =\u00a0 X<\/em>   <\/p>\n<p>Disadvantage<\/p>\n<p>Its disadvantage is that a lot of collisions can occur with different arrangements of various segments.  <\/p>\n<p><strong><em>Polynomial Accumulation<\/em><\/strong>  <\/p>\n<p>In this, firstly, we divide a key into different segments like component sum. But in polynomial accumulation, we just take some variables or integers or some non-zero constant.<\/p>\n<p>Suppose we have a key that is equal to a string \u2018CODE\u2019. We will divide this key into 32-bit segments. Then we will take the ASCII value of each of the string characters. Then we will take the sum of ASCII of each character into non-zero constant ( a ).<\/p>\n<p><em>                                                                    Key = \u2018CODE\u2019<\/em><\/p>\n<p><em>                                  ( ASC(C) x a0 )+( ASC(O) x a1)\u00a0 + (ASC(D) x a2)\u00a0 + (ASC(E) x a3)<\/em><\/p>\n<p><em>                                                                 Hash Code (Key, a)<\/em><\/p>\n<p>In this, if we change the arrangement of letters, the hash code is also going to change. For the same keys, we will get the same hash code. For the different keys, we will get different hash codes. Now let&#8217;s take a look at the program of hash code. Let&#8217;s say that key is going to be an array. Elements of this array will contain 32-bit segments which we have divided our key into. At position 0, we will have ASCII of \u2018C\u2019. At position 1,2, and 3, we will have ASCII of \u2018O\u2019,\u2019D\u2019, and \u2018E\u2019. Now program to calculate the hash code is:  <\/p>\n<pre><code class=\"cpp\">for(i= n-1 ; i > = 0 ; i--){ sum = ( sum * a ) + arr[i]; }  arr[ C , O , D , E ]    i = 3 , sum = E ; i = 2 , sum = Ea + D ; i = 1 , sum = Ea2+ Da + O; i = 0 , sum = Ea3+ Da2+ Oa + C;<\/code><\/pre>\n<p><strong>Hashing Techniques to Resolve Collision<\/strong><\/p>\n<p>When we calculate some hash function or location or address for keys and use that same hash function. That hash function will give the same index, but we cannot store two values at the same place in the hash table. This process is called a collision. To resolve these collisions, we have some techniques:  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/a03\/e26\/6f4\/a03e266f41e05d8b9a766a413c0c6674.jpg\" width=\"482\" height=\"297\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a03\/e26\/6f4\/a03e266f41e05d8b9a766a413c0c6674.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p><strong><em>Separate\u00a0 Chaining<\/em><\/strong><\/p>\n<p>In this type, if two keys hash to the same hash value, then in the bucket array for that particular hash value index, we will create a linked list.<\/p>\n<p>Let&#8217;s consider we have keys 100,105,200, and 205. Hash function is equal to K times mod of 10.<\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                                    <em>Keys = 100 ,105,200,205<\/em><\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                        <em>H(K) = K mod 10<\/em><\/p>\n<p>Since the range of this function is 10, we have a bucket array of elements ranging from 0 to 9. For the first key-value, which is 100, 100 mod 10 is equal to 0. So it will be filled at index 0. At index 0, we will start a linked list with the key of 100. Now for key 105,   <\/p>\n<p><em>                                                                  105 mod 10 = 5<\/em><\/p>\n<p>So now start a linked list with a key of 105 at index 5.Then, for key 200,   <\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0                                                             <em>200 mod 10 = 0<\/em>  <\/p>\n<p>So we will go to the index 0 and add it to the end of the linked list after 100. Now for the key 205,  <\/p>\n<p><em>                                                                  205 mod 10 = 5<\/em>  <\/p>\n<p>We will go to index 5 and add it to the end of the linked list after 105. This is how to separate chaining works.  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/936\/f24\/a4c\/936f24a4c58b97d3b79e947cc059846b.jpg\" width=\"651\" height=\"228\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/936\/f24\/a4c\/936f24a4c58b97d3b79e947cc059846b.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>So we always need two functions for a hash table in it. The first insert operation and the second is the search operation. Let&#8217;s look at the algorithm of each function.<\/p>\n<p><strong><em>Insert<\/em><\/strong>   <\/p>\n<p>This algorithm is fairly simple. If we say insert and we have an algorithm \u2018insert item&#8217; . And we have a (key, element) pair which we want to insert. So, we will go to the index, which is equal to the key. Then at that index, we will have a linked list. This is going to be an array of linked list.So to this linked list, we will insert at the end the key-element pair.  <\/p>\n<p><strong><em>Search<\/em><\/strong>  <\/p>\n<p>If we want to search for a key-element pair, the linked list we search for the element will be equal to the linked present in the array of the index key. So call this linked as C and store the array of a key in it. Now C is a linked list in which we want to search.  <\/p>\n<p><strong><em>Linear Probing<\/em><\/strong>  <\/p>\n<p>In this, when a collision occurs, that is two distinct keys are mapped to the same hash value. In such a case, the colliding element will be positioned in the later circularly available table cell.<\/p>\n<p>To understand the working of linear probing, let&#8217;s consider that our hash function is:<\/p>\n<p><em>                                                                  H(x) = x mod 10<\/em>  <\/p>\n<p>And keys are:  <\/p>\n<p><em>                                                          Keys = (18,41,22,32,44,59,79)<\/em>  <\/p>\n<p>Now hash values will be:  <\/p>\n<p><em>                                                          Hash Values = ( 8, 1,2,2,4,9,9)<\/em>  <\/p>\n<p>As the range is 10, the bucket array will have indexes from 0 to 9. We will place each key in the index, which is equal to their hash value. For the key value 32, its index value is the same as key-value 22. Index 2 has been already filled with key 22, so I will check its next index. As next index 3 is empty or free, so key 32 will be placed here. The index for key 79 is 9, but it has already been filled with key 59 because its index is also 9. So, we will go to the next circularly available table cell, which is 0. As index 0 is free, so we will place key 79 here:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/601\/c20\/97f\/601c2097f9fb84168b26b6d9e068406a.jpeg\" width=\"644\" height=\"71\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/601\/c20\/97f\/601c2097f9fb84168b26b6d9e068406a.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now let&#8217;s see the pseudocode for inserting an element. Firstly we will calculate the hash code or hash value of the key and store that value in variable \u2018H\u2019. The key could be either placed at index H or could be placed at an index somewhere different from H provided that H is not empty. So let&#8217;s keep the incrementing variable i equal to 0.  <\/p>\n<p><strong><em>Quadratic Probing<\/em><\/strong>  <\/p>\n<p>In linear probing, a lot of elements start clustering. That is, elements will start to be stored in groups or in a group of consecutive filled cells. This is not good because when we want to add an element to a cluster , we have to probe through many indexes to finally add that element. So it is not very time efficient. The solution to this problem is quadratic probing. In quadratic probing, we have to check which indexes to check when we want to add an element. We iteratively check the index of the hash value of the key plus square of i mod N.The expression for quadratic probing is:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f0e\/709\/295\/f0e709295524ee309dd1b426d81a25f8.png\" width=\"914\" height=\"42\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f0e\/709\/295\/f0e709295524ee309dd1b426d81a25f8.png\"\/><figcaption><\/figcaption><\/figure>\n<p>Suppose we have a hash function:  <\/p>\n<p><em>                                                                     H(x) = x mod 10<\/em>  <\/p>\n<p>And keys are:  <\/p>\n<p><em>                                                                   Keys = ( 2, 12 , 22 )<\/em>  <\/p>\n<p>Hash value will be:  <\/p>\n<p><em>                                                                      Hash = ( 2,2,2 )<\/em><\/p>\n<p>Now we will create an array having indexes 0 to 9.Firstly, key 2 will be placed at index value 2 in the array. Key 12 has index value 2, but index 2 has already filled with key 2.So to place key 12, the index value will be:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/928\/99d\/fe1\/92899dfe157451bf309c7608689370d4.png\" width=\"1011\" height=\"43\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/928\/99d\/fe1\/92899dfe157451bf309c7608689370d4.png\"\/><figcaption><\/figcaption><\/figure>\n<p>Now key 22 has index value 2, but it has been already filled, so we will find their index values as:  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/35a\/da5\/290\/35ada5290934f8e2df08d82764a383b7.png\" width=\"1024\" height=\"49\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/35a\/da5\/290\/35ada5290934f8e2df08d82764a383b7.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/ed2\/b9e\/b35\/ed2b9eb35366798bcbc47072aa3af5ce.jpeg\" width=\"647\" height=\"64\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ed2\/b9e\/b35\/ed2b9eb35366798bcbc47072aa3af5ce.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p><strong><em>Double Hashing<\/em><\/strong>  <\/p>\n<p>In double hashing, we check iteratively indexes of the hash value of K plus\u00a0 j into the hash value of 2K.  <\/p>\n<p><em>                                                      Double Hashing = Hash1(K) + j Hash 2(K)<\/em>  <\/p>\n<p>We have two hash functions in double hashing. In the above expression, \u2018j\u2019 is the iterative element starting at 0.  <\/p>\n<p>The values of both hash functions will be:  <\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/718\/6b8\/549\/7186b8549eb19b64dcc5ecc049000607.jpg\" width=\"420\" height=\"149\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/718\/6b8\/549\/7186b8549eb19b64dcc5ecc049000607.jpg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<p>Now we will create a bucket array from 0 to 12 index value because the maximum range of N is 13. Now we will insert these hash values into the bucket array.<\/p>\n<p>For adding key value 18:<\/p>\n<p><em>                                                                         5 + (0*3) = 5<\/em>  <\/p>\n<p>So 18 will go to the index value 5.<\/p>\n<p>For key value 41:<\/p>\n<p><em>                                                                          2+ (0*1)=2<\/em>  <\/p>\n<p> Similarly for keys 22 and 44:<\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                                                          <em>9+ (0*6) = 9<\/em><\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                               <em>5+(0*5) = 5<\/em><\/p>\n<p>Keys 22 will go to index value 9 but key 44 has index value 5 which is not empty. So now we will take:<\/p>\n<p><em>                                                                        5+(1*5) = 10<\/em>    <br \/>So the index value for key 44 will be 10.  <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/826\/d3e\/b75\/826d3eb75a6516f2f1d31b7092dafd3e.jpeg\" width=\"641\" height=\"58\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/826\/d3e\/b75\/826d3eb75a6516f2f1d31b7092dafd3e.jpeg\" data-blurred=\"true\"\/><figcaption><\/figcaption><\/figure>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/563664\/\"> https:\/\/habr.com\/ru\/articles\/563664\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>It is an efficient searching technique. Searching is a widespread operation on any data structure. Hashing is used to search specific records from a large domain of records. If we can efficiently search a record out of\u00a0 many records, we easily perform different operations on that data. Hashing is storing and retrieving data from the database in the order of O(1) time. We can also call it the mapping technique because we try to map smaller values into larger values by using hashing.<\/p>\n<p>Following are the significant terminologies related to hashing<\/p>\n<p><strong>Search Key<\/strong><\/p>\n<p>In the database, we usually perform searching with the help of some keys. These keys are called search keys. If we take the student data, then we search by some registration number. This registration number is a search key. We have to put the search keys in hash tables.<\/p>\n<p><strong>Hash Table<\/strong><\/p>\n<p>It is a data structure that provides us the methodology to store data properly. A hash table is shown below. It is similar to an array. And we have indexes in it also like an array.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><strong>Hash Function<\/strong>  <\/p>\n<p>When we perform searching, inserting, or deleting some data from it, we don\u2019t need to scan the whole table. With the help of a hash function, we will perform it with the order of O(1) time. There are different hash functions such as:<\/p>\n<ul>\n<li>\n<p>K mod 10<\/p>\n<\/li>\n<li>\n<p>K mod n<\/p>\n<\/li>\n<li>\n<p>Mid Square<\/p>\n<\/li>\n<li>\n<p>Folding Method   <\/p>\n<\/li>\n<\/ul>\n<p>\u2018K mod 10\u2019 and \u2018K mod n\u2019 are the most widely used methods.\u00a0<\/p>\n<p>Suppose we have a number 24 and hash function \u2018K mod 10\u2019.With the help of the hash function, we will map 24 in the hash table. For this purpose, we can put K is equal to 24 so:<\/p>\n<p><em>                                                                       24 mod 10 = 4<\/em>  <\/p>\n<p>So we can place 24 at index 4 in the hash table. Then for 52 number   <\/p>\n<p><em>                                                                       52 mod 10 = 2<\/em>  <\/p>\n<p>52 will go to index 2 location. Next for number 91  <\/p>\n<p><em>                                                                       91 mod 10 = 1<\/em>  <\/p>\n<p>So, 91 will be placed at index 1 in the table. Then finally for 67  <\/p>\n<p><em>                                                                       67 mod 10 = 7<\/em>  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>A hash table uses two components:  <\/p>\n<ul>\n<li>\n<p>Hash function<\/p>\n<\/li>\n<li>\n<p>Bucket Array<\/p>\n<\/li>\n<\/ul>\n<p>For an element key pair, the hash function calculates some value based on a key. A hash function is a function with a key as an input parameter. A hash function will give us two parts:  <\/p>\n<p><strong>Hash Codes<\/strong>  <\/p>\n<p>In this, we assign an integer to the key. It is going to map the key to some integer.  <\/p>\n<p><strong>Compression Map<\/strong>  <\/p>\n<p>It will convert the integer, or rather it will map the integer which we have received from the hash code to an integer in the range 0 to n-1. Once we have the hash function of the key, we would first receive an integer, and then map that integer to 0 to n-1. So the outcome of the hash code or the outcome of the hash function will be an integer in the range 0 to the n-1. This integer depends on the key of the input element.<\/p>\n<p>In the bucket array, we are going to store the element in an array of hash functions of the key. So once we will receive an integer in the range 0 to n minus 1.So, we will store the element in an array of not just the key but the array of hash function of the key. So, once we do this, the keys no longer have to be integers. Also, we don\u2019t need to know the range of keys because we are going to map it into a range which is provided by us.<\/p>\n<p><strong>Hash Code<\/strong>  <\/p>\n<p>Hash code is a function that converts a key to an integer. So it&#8217;s going to convert a key of any type to an integer.<\/p>\n<p>Following are some properties of a good hash code:<\/p>\n<ul>\n<li>\n<p>It will minimize collisions. It means that if we are given two keys that are different, their hash codes should also be different. So if two keys say \u2018K1\u2019 does not equal \u2018K2\u2019.<\/p>\n<\/li>\n<\/ul>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                      <em>K1 \u2260K2<\/em><\/p>\n<p>        It implies that the hash code of key 1 should also not equal to the hash code of key 2.If two keys are a map to the same hash code, then we say a collision has occurred. We don\u2019t want this. We want different hash codes for different keys. So we want to minimize collisions.<\/p>\n<ul>\n<li>\n<p>A good hashcode should be uniform. If we have a key \u2018K1\u2019 and that is equal to key \u2018K2\u2019.<\/p>\n<\/li>\n<\/ul>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                         <em>K1 = K2<\/em><\/p>\n<p>       Then we don\u2019t need different answers for hash code. Because for the same value of the key, if we run our hash code, then we should always get the same value of the hash code. So if both keys are equal, then the hash code of Key 1 has to equal the hash code of Key 2.<\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                  <em>hash(K1) = hash(K2)<\/em><\/p>\n<p><strong>Hash Code Map Example<\/strong>  <\/p>\n<p><strong><em>Memory Address<\/em><\/strong>  <\/p>\n<p>In this, we are going to interpret the memory address of the key as the hash code. So we are going to take the memory address of the key as the hash code of the key.<\/p>\n<p>Let&#8217;s take an example of it. We have a key 1, and this is at a memory address of 5000. Then we have key 2, and this is at memory address 5010.<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><em>                                                                  Hash(K1) = 5000<\/em><\/p>\n<p><em>                                                                 Hash(K2) =\u00a0 5010<\/em><\/p>\n<p>It can be seen that the key, whatever the data type it may be, has arrived at an integer that maps to that data.<\/p>\n<p><em>Disadvantage<\/em><\/p>\n<p>The disadvantage of this hash code is that this is not uniform.<\/p>\n<p><strong><em>Integer Cast<\/em><\/strong>  <\/p>\n<p>It is a method of mapping to an integer. In this, whatever the data type of the key may be, typecast it to an integer. So if we have a string and we typecast a character of that string, it is going to return an ASCII value to us. And thereby, we will get an integer.<\/p>\n<p><em>Disadvantage<\/em><\/p>\n<p>Its disadvantage is that for data types like double or float, we encounter a loss of data. And a lot of collisions will occur in this method.<\/p>\n<p><strong><em>Component Sum<\/em><\/strong>  <\/p>\n<p>It is a type of hash code in which the partition bits of the key into fixed-length components. Suppose we have a float or a double that\u2019s going to be 64 bits for us. We will partition them into a fixed bit component. So we will partition these 64 bits into two 32 bits. Then we will add these two 32 bits to get a 32-bit hash code after ignoring overflow.  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>Suppose we use a string case. And We have a key that is equal to the string \u2018NAME\u2019. So, in this case, we will not directly typecast this to an integer. We will divide this into four 32 bit segments. Then we will add these values. For each of these values, we take ASCII values of each of these characters. Then we will get the final hash code by adding each of these values.<\/p>\n<p><em>                                                                    Key = \u2018NAME\u2019<\/em>  <\/p>\n<p><em>                                                   ASC(N) + ASC(A) + ASC(M) + ASC(E)<\/em> <\/p>\n<p><em>                                                               Hash Code (Key)\u00a0 =\u00a0 X<\/em>   <\/p>\n<p>Disadvantage<\/p>\n<p>Its disadvantage is that a lot of collisions can occur with different arrangements of various segments.  <\/p>\n<p><strong><em>Polynomial Accumulation<\/em><\/strong>  <\/p>\n<p>In this, firstly, we divide a key into different segments like component sum. But in polynomial accumulation, we just take some variables or integers or some non-zero constant.<\/p>\n<p>Suppose we have a key that is equal to a string \u2018CODE\u2019. We will divide this key into 32-bit segments. Then we will take the ASCII value of each of the string characters. Then we will take the sum of ASCII of each character into non-zero constant ( a ).<\/p>\n<p><em>                                                                    Key = \u2018CODE\u2019<\/em><\/p>\n<p><em>                                  ( ASC(C) x a0 )+( ASC(O) x a1)\u00a0 + (ASC(D) x a2)\u00a0 + (ASC(E) x a3)<\/em><\/p>\n<p><em>                                                                 Hash Code (Key, a)<\/em><\/p>\n<p>In this, if we change the arrangement of letters, the hash code is also going to change. For the same keys, we will get the same hash code. For the different keys, we will get different hash codes. Now let&#8217;s take a look at the program of hash code. Let&#8217;s say that key is going to be an array. Elements of this array will contain 32-bit segments which we have divided our key into. At position 0, we will have ASCII of \u2018C\u2019. At position 1,2, and 3, we will have ASCII of \u2018O\u2019,\u2019D\u2019, and \u2018E\u2019. Now program to calculate the hash code is:  <\/p>\n<pre><code class=\"cpp\">for(i= n-1 ; i > = 0 ; i--){ sum = ( sum * a ) + arr[i]; }  arr[ C , O , D , E ]    i = 3 , sum = E ; i = 2 , sum = Ea + D ; i = 1 , sum = Ea2+ Da + O; i = 0 , sum = Ea3+ Da2+ Oa + C;<\/code><\/pre>\n<p><strong>Hashing Techniques to Resolve Collision<\/strong><\/p>\n<p>When we calculate some hash function or location or address for keys and use that same hash function. That hash function will give the same index, but we cannot store two values at the same place in the hash table. This process is called a collision. To resolve these collisions, we have some techniques:  <\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p><strong><em>Separate\u00a0 Chaining<\/em><\/strong><\/p>\n<p>In this type, if two keys hash to the same hash value, then in the bucket array for that particular hash value index, we will create a linked list.<\/p>\n<p>Let&#8217;s consider we have keys 100,105,200, and 205. Hash function is equal to K times mod of 10.<\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                                    <em>Keys = 100 ,105,200,205<\/em><\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0                        <em>H(K) = K mod 10<\/em><\/p>\n<p>Since the range of this function is 10, we have a bucket array of elements ranging from 0 to 9. For the first key-value, which is 100, 100 mod 10 is equal to 0. So it will be filled at index 0. At index 0, we will start a linked list with the key of 100. Now for key 105,   <\/p>\n<p><em>                                                                  105 mod 10 = 5<\/em><\/p>\n<p>So now start a linked list with a key of 105 at index 5.Then, for key 200,   <\/p>\n<p>\u00a0\u00a0\u00a0\u00a0\u00a0                                                             <em>200 mod 10 = 0<\/em>  <\/p>\n<p>So we will go to the index 0 and add it to the end of the linked list after 100. Now for the key 205,  <\/p>\n<p><em>                                                                  205 mod 10 = 5<\/em>  <\/p>\n<p>We will go to index 5 and add it to the end of the linked list after 105. This is how to separate chaining works.  <\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>So we always need two functions for a hash table in it. The first insert operation and the second is the search operation. Let&#8217;s look at the algorithm of each function.<\/p>\n<p><strong><em>Insert<\/em><\/strong>   <\/p>\n<p>Th<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-415773","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/415773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=415773"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/415773\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=415773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=415773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=415773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}