![\"Introduction](\"https:\/\/www.kindsonthegenius.com\/wp-content\/uploads\/2020\/09\/Linear-Probing-Quadratic-Probing-and-Double-Hashing-300x217.jpg\")
<\/p>\n
1. Linear Probing<\/strong><\/h5>\nWe start with a normal has function h that maps the universe of keys U into slots in the hash table T such that<\/p>\n
h’ : U\u00a0\u2192 {0, 1, 2, . . . , m-1}<\/p>\n
h’ is a normal hash function which we would call the auxiliary hash function.\u00a0 Now if we use linear probing, we would have a hash function like this:<\/p>\n
h(k, i) = (h'(k) + i ) mod m<\/p>\n
for m = 0, 1, 2, . . .,m-1<\/p>\n
Given a particular key k, the first step is to examine T[h'(k)]\u00a0 which is the\u00a0 slot given by the auxiliary hash function. Next, we examine slot T[h'(k) +1], then we examine T[h'(k) +2] and so on up to the last slot which is T[m-1]. The wrap around back to the beginning of the table to position T[0], T[1] and so on until T[h'(k) -1].\u00a0 This is presented in the table below:<\/p>\n
\n- T[h'(k)]<\/li>\n
- T[h'(k) + 1]<\/li>\n
- T[h'(k) + 2]<\/li>\n
- …<\/li>\n
- …<\/li>\n
- T[m-1]<\/li>\n
- T[0]<\/li>\n
- T[1]<\/li>\n
- …<\/li>\n
- …<\/li>\n
- T[h'(k) – 1]<\/li>\n<\/ul>\n
It is therefore guaranteed that there will be m distinct probe sequences since the initial probe determines the whole probe sequence.<\/p>\n
Linear Probing have the advantage of being easy to implement but has one draw back. And that is a problem known as primary clustering. This is a situation where long runs of positions build up. This in turn leads to increased average search time.<\/p>\n
<\/p>\n
2. Quadratic Probing<\/strong><\/h5>\nQuadratic Probing is similar to linear probing but in quadratic probing the hash function used is of the form:<\/p>\n
h(k, i) = (h'(k) +\u00a0 c1<\/sub>i\u00a0 + c2<\/sub>i2<\/sup>) mod m<\/p>\nwhere h’ is the auxiliary hash function and c1<\/sub> and c2<\/sub> are called positive auxiliary constants.<\/p>\ni = 0, 1, 2, . . . , m-1<\/p>\n
Just as with linear probing, the initial probe position is T[h'(k)]; Subsequent positions probed are not linear but are offset by\u00a0 an amount that depends on the quadratic nature of the probe number i.<\/p>\n
The method of quadratic probing is found to be better than linear probing. However, to ensure that the full hash table is covered, the values of c1<\/sub>, and c2<\/sub> are constrained. It may happen that two keys produce the same probe sequence such that:<\/p>\nh(k1<\/sub>, i) = h(k2<\/sub>, i)<\/p>\nTherefore, this leads to a kind of clustering called secondary clustering. Just as in linear probing, the initial probe position determines the entire probe sequence.<\/p>\n
<\/p>\n
3. Double Hashing<\/strong><\/h5>\nDouble Hashing is considered to be the best method of hashing for open addressing compared to linear and quadratic probing. In this case, two auxiliary functions h1<\/sub> and h2<\/sub> are used.\u00a0 Hash function for double hashing take the form:<\/p>\nh(k, i) = (h1<\/sub>(k) + ih2<\/sub>(k)) mod m<\/p>\nh1<\/sub> and h2<\/sub> are the auxiliary functions.<\/p>\nJust like before, the initial probe position is T[h1<\/sub>(k)]. Subsequent hash positions are offset from previous position by the amount h2<\/sub>(k) modulo m. So we can see that the probe sequence depends on the key in two ways. This is because the initial probe position, the offset or both may vary.<\/p>\nHowever, value of h2<\/sub>(k) need to be relatively prime. for the whole hash table to be searched. One way to achieve this is to let m be a power of 2 and then to design h2<\/sub> such that it will always produce and odd number. Another ways is to let me be a prime number and the to design h2<\/sub> to always returns a positive integer that is less than m.<\/p>\nTake and example<\/p>\n
h1<\/sub>(k) = k mod m<\/p>\nh2<\/sub>(k) = 1 + (k mod m’)<\/p>\nwhere m’ is a little less than m.<\/p>\n
Finally, we would not take some time to do and Analysis of Open Addressing with Linear Probing in the next lesson.<\/p>\n
<\/p>\n
Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n\n- Skip Lists and How They Work<\/a><\/strong><\/li>\n
- Perfect Hashing \u2013 How it Works<\/a><\/strong><\/li>\n
- Linear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/li>\n
- Hashing With Open Addressing<\/a><\/strong><\/li>\n
- Universal Hashing<\/a><\/strong><\/li>\n
- Search Time Under Simple Uniform Hashing<\/a><\/strong><\/li>\n
- Hash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/li>\n
- Introduction to Hash Tables and Direct Addressing<\/a><\/strong><\/li>\n
- Recurrences in Divide and Conquer Algorithm<\/a><\/strong><\/li>\n
- How Bloom Filters Work<\/a><\/strong><\/li>\n
- How Cuckoo Hashing Works<\/a><\/strong><\/li>\n
- Introduction to AVL Trees (With Examples)<\/a><\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
The three terms that make up the title of this article are the three common techniques used for computing hash sequences. That is what are … <\/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-1851","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851","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=1851"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions"}],"predecessor-version":[{"id":2020,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions\/2020"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
It is therefore guaranteed that there will be m distinct probe sequences since the initial probe determines the whole probe sequence.<\/p>\n
Linear Probing have the advantage of being easy to implement but has one draw back. And that is a problem known as primary clustering. This is a situation where long runs of positions build up. This in turn leads to increased average search time.<\/p>\n
<\/p>\n
2. Quadratic Probing<\/strong><\/h5>\nQuadratic Probing is similar to linear probing but in quadratic probing the hash function used is of the form:<\/p>\n
h(k, i) = (h'(k) +\u00a0 c1<\/sub>i\u00a0 + c2<\/sub>i2<\/sup>) mod m<\/p>\nwhere h’ is the auxiliary hash function and c1<\/sub> and c2<\/sub> are called positive auxiliary constants.<\/p>\ni = 0, 1, 2, . . . , m-1<\/p>\n
Just as with linear probing, the initial probe position is T[h'(k)]; Subsequent positions probed are not linear but are offset by\u00a0 an amount that depends on the quadratic nature of the probe number i.<\/p>\n
The method of quadratic probing is found to be better than linear probing. However, to ensure that the full hash table is covered, the values of c1<\/sub>, and c2<\/sub> are constrained. It may happen that two keys produce the same probe sequence such that:<\/p>\nh(k1<\/sub>, i) = h(k2<\/sub>, i)<\/p>\nTherefore, this leads to a kind of clustering called secondary clustering. Just as in linear probing, the initial probe position determines the entire probe sequence.<\/p>\n
<\/p>\n
3. Double Hashing<\/strong><\/h5>\nDouble Hashing is considered to be the best method of hashing for open addressing compared to linear and quadratic probing. In this case, two auxiliary functions h1<\/sub> and h2<\/sub> are used.\u00a0 Hash function for double hashing take the form:<\/p>\nh(k, i) = (h1<\/sub>(k) + ih2<\/sub>(k)) mod m<\/p>\nh1<\/sub> and h2<\/sub> are the auxiliary functions.<\/p>\nJust like before, the initial probe position is T[h1<\/sub>(k)]. Subsequent hash positions are offset from previous position by the amount h2<\/sub>(k) modulo m. So we can see that the probe sequence depends on the key in two ways. This is because the initial probe position, the offset or both may vary.<\/p>\nHowever, value of h2<\/sub>(k) need to be relatively prime. for the whole hash table to be searched. One way to achieve this is to let m be a power of 2 and then to design h2<\/sub> such that it will always produce and odd number. Another ways is to let me be a prime number and the to design h2<\/sub> to always returns a positive integer that is less than m.<\/p>\nTake and example<\/p>\n
h1<\/sub>(k) = k mod m<\/p>\nh2<\/sub>(k) = 1 + (k mod m’)<\/p>\nwhere m’ is a little less than m.<\/p>\n
Finally, we would not take some time to do and Analysis of Open Addressing with Linear Probing in the next lesson.<\/p>\n
<\/p>\n
Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n\n- Skip Lists and How They Work<\/a><\/strong><\/li>\n
- Perfect Hashing \u2013 How it Works<\/a><\/strong><\/li>\n
- Linear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/li>\n
- Hashing With Open Addressing<\/a><\/strong><\/li>\n
- Universal Hashing<\/a><\/strong><\/li>\n
- Search Time Under Simple Uniform Hashing<\/a><\/strong><\/li>\n
- Hash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/li>\n
- Introduction to Hash Tables and Direct Addressing<\/a><\/strong><\/li>\n
- Recurrences in Divide and Conquer Algorithm<\/a><\/strong><\/li>\n
- How Bloom Filters Work<\/a><\/strong><\/li>\n
- How Cuckoo Hashing Works<\/a><\/strong><\/li>\n
- Introduction to AVL Trees (With Examples)<\/a><\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
The three terms that make up the title of this article are the three common techniques used for computing hash sequences. That is what are … <\/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-1851","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851","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=1851"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions"}],"predecessor-version":[{"id":2020,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions\/2020"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
where h’ is the auxiliary hash function and c1<\/sub> and c2<\/sub> are called positive auxiliary constants.<\/p>\n i = 0, 1, 2, . . . , m-1<\/p>\n Just as with linear probing, the initial probe position is T[h'(k)]; Subsequent positions probed are not linear but are offset by\u00a0 an amount that depends on the quadratic nature of the probe number i.<\/p>\n The method of quadratic probing is found to be better than linear probing. However, to ensure that the full hash table is covered, the values of c1<\/sub>, and c2<\/sub> are constrained. It may happen that two keys produce the same probe sequence such that:<\/p>\n h(k1<\/sub>, i) = h(k2<\/sub>, i)<\/p>\n Therefore, this leads to a kind of clustering called secondary clustering. Just as in linear probing, the initial probe position determines the entire probe sequence.<\/p>\n <\/p>\n Double Hashing is considered to be the best method of hashing for open addressing compared to linear and quadratic probing. In this case, two auxiliary functions h1<\/sub> and h2<\/sub> are used.\u00a0 Hash function for double hashing take the form:<\/p>\n h(k, i) = (h1<\/sub>(k) + ih2<\/sub>(k)) mod m<\/p>\n h1<\/sub> and h2<\/sub> are the auxiliary functions.<\/p>\n Just like before, the initial probe position is T[h1<\/sub>(k)]. Subsequent hash positions are offset from previous position by the amount h2<\/sub>(k) modulo m. So we can see that the probe sequence depends on the key in two ways. This is because the initial probe position, the offset or both may vary.<\/p>\n However, value of h2<\/sub>(k) need to be relatively prime. for the whole hash table to be searched. One way to achieve this is to let m be a power of 2 and then to design h2<\/sub> such that it will always produce and odd number. Another ways is to let me be a prime number and the to design h2<\/sub> to always returns a positive integer that is less than m.<\/p>\n Take and example<\/p>\n h1<\/sub>(k) = k mod m<\/p>\n h2<\/sub>(k) = 1 + (k mod m’)<\/p>\n where m’ is a little less than m.<\/p>\n Finally, we would not take some time to do and Analysis of Open Addressing with Linear Probing in the next lesson.<\/p>\n <\/p>\n The three terms that make up the title of this article are the three common techniques used for computing hash sequences. That is what are … <\/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-1851","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851","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=1851"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions"}],"predecessor-version":[{"id":2020,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1851\/revisions\/2020"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1851"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}3. Double Hashing<\/strong><\/h5>\n
Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n
\n