{"id":1856,"date":"2019-01-02T12:00:00","date_gmt":"2019-01-02T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/universal-hashing\/"},"modified":"2026-07-05T03:20:43","modified_gmt":"2026-07-05T01:20:43","slug":"universal-hashing","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/universal-hashing\/","title":{"rendered":"Universal Hashing \u2013 An Clear Explanation"},"content":{"rendered":"<p><strong>We would cover the following topics on Universal Hashing<\/strong><\/p>\n<ul>\n<li><a href=\"#t1\">Introduction to Universal Hashing<\/a><\/li>\n<li><a href=\"#t2\">What is Universal Hashing<\/a><\/li>\n<li><a href=\"#t3\">How Universal hashing Works<\/a><\/li>\n<li><a href=\"#t4\">The Theorem and Proof<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t1\">1. Introduction to Universal Hashing<\/strong><\/h5>\n<p>If we have a fixed hash function such that all keys uses this single hash function, then we may be unfortunate that the keys selected may be such that they all hash to the same slot in the hash table. And this would result in an average search time of\u00a0\u0398(n). We want to avoid this happening or at least limit its possibility.<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t2\">2. What is\u00a0 Universal Hashing?<\/strong><\/h5>\n<p>Universal Hashing is a way to avoid the situation presented above. In Universal Hashing the hash function is selected randomly independent of the keys that are to be stored.<\/p>\n<p>In universal hashing, at the beginning of the execution, we choose a hash function randomly from a carefully designed family of functions. This guarantees that no single input would result in the worst-case situation. Since the hash functions are random, the behavior would be different for for each execution which would yield average case performance on each input.<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t3\">3. How Universal Hashing Works<\/strong><\/h5>\n<p>Let\u00a0<span class=\"code char\">\u210b\u00a0<\/span> be a finite set of has functions that map a given universe U of keys into the range {0, 1, 2, . . . ,m-1}. This set of functions is said to be universal if for each pair of distinct keys k, l\u00a0\u2208 U, the number of has functions h\u00a0\u2208\u00a0<span class=\"code char\">\u210b<\/span>\u00a0 for which h(k) = h(l) is at most |<span class=\"code char\">\u210b<\/span>|\/m<\/p>\n<p>This means that with a hash function randomly chosen from the set\u00a0 <span class=\"code char\">\u210b<\/span>, the possibility of collision between two distinct keys k and l is at most the chance of 1\/m of of a collision occurring if h(k) and h(l) were chosen randomly and independently from the set {0, 1, 2, . . . ,m-1}<\/p>\n<p>&nbsp;<\/p>\n<h5><strong id=\"t4\">4. The Theorem and Proof<\/strong><\/h5>\n<p><strong>Theorem<\/strong>: Assuming that a hash function h is chosen randomly from a universal hash family of hash functions.\u00a0 And then used to has n keys into a hash table T which is of size m. Also assuming chaining is used\u00a0 to handle collisions. If the key k is not in the table, then the expected length E[n<sub>h(k)<\/sub>] of the linked list that k hashes into is at most equal to n\/m. If the key is present in the table, then the expected length E(n<sub>h(k)<\/sub>] of the list containing the key is at most 1 +\u00a0\u03b1<\/p>\n<p><strong>Proof<\/strong>: For each given pair of keys k and l which are distinct, we then define an indicator random variable X<sub>kl<\/sub> to use to count the number of times k and l hashes to the same slot.<\/p>\n<p style=\"text-align: center;\">X<sub>kl<\/sub> = I[h(k) = h(l)}<\/p>\n<p>Since by by definition for universal family of has functions, a single pair of keys can only collide with probability of at most 1\/m we now have<\/p>\n<p style=\"text-align: center;\">P<sub>r<\/sub>{h(k) = h(l)}\u00a0\u2264 1\/m<\/p>\n<p>We can there for conclude that :<\/p>\n<p style=\"text-align: center;\">E[X<sub>kl<\/sub>]\u00a0\u2264 1\/m<\/p>\n<p>Sure you have learnt about Universal Hashing but we recommend you read about Open Addressing and Linear Probing.<\/p>\n<p>&nbsp;<\/p>\n<h5><strong>Check these Data Structure and Algorithms Tutorials<\/strong><\/h5>\n<ul>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/skip-lists-and-how-they-work\/\">Skip Lists and How They Work<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/perfect-hashing\/\">Perfect Hashing \u2013 How it Works<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hashing\/\">Linear Probing, Quadratic Probing and Double Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hashing-with-open-addressing\/\">Hashing With Open Addressing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/universal-hashing\/\">Universal Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/search-time-under-simple-uniform-hashing\/\">Search Time Under Simple Uniform Hashing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/hash-tables-hashing-with-chaining\/\">Hash Tables \u2013 Hashing With Chaining<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/introduction-to-hash-tables-and-direct-addressing\/\">Introduction to Hash Tables and Direct Addressing<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/recurrences-in-divide-and-conquer-algorithm\/\">Recurrences in Divide and Conquer Algorithm<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/how-bloom-filters-work\/\">How Bloom Filters Work<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/cuckoo-hashing\/\">How Cuckoo Hashing Works<\/a><\/strong><\/li>\n<li><strong><a href=\"https:\/\/kindsonthegenius.com\/tempsite\/introduction-to-avl-trees-with-examples\/\">Introduction to AVL Trees (With Examples)<\/a><\/strong><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>We would cover the following topics on Universal Hashing Introduction to Universal Hashing What is Universal Hashing How Universal hashing Works The Theorem and Proof &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-1856","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1856","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=1856"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions"}],"predecessor-version":[{"id":2025,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions\/2025"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}