{"id":1850,"date":"2019-01-01T12:00:00","date_gmt":"2019-01-01T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/cuckoo-hashing\/"},"modified":"2026-07-05T03:20:24","modified_gmt":"2026-07-05T01:20:24","slug":"cuckoo-hashing","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/cuckoo-hashing\/","title":{"rendered":"How Cuckoo Hashing Works"},"content":{"rendered":"

The Cuckoo hashing algorithm allows for lookup of items at constant time, O(1). We would cover the following in this article:<\/p>\n

    \n
  1. How Cuckoo Hashing Works<\/a><\/li>\n
  2. The Cuckoo Hashing Algorithm<\/a><\/li>\n
  3. The Cuckoo Graph<\/a><\/li>\n
  4. Cycles in the Cuckoo Graph<\/a><\/li>\n
  5. Watch the Video<\/a><\/li>\n<\/ol>\n

    \"\"
    \n1. How the Cuckoo Hashing Works<\/strong><\/p>\n

    In cuckoo hashing, we maintain two hash position (and hash functions) h1 and h2.\u00a0 So if we need to store a key x, we would compute one of two postions h1(x) and h2(x).<\/p>\n

    This means that to retrieve an item, we simply need to lookup just two positions in the table. This is shown in Table 1.0.<\/p>\n

    \"\"
    Figure 1.0: Cuckoo hash table. The arrow directions shown the alternative location of each of the items in the table. If a new item is to be inserted into position occupied by A, then A is ejected and moved to its second alternative position. Insertion in position of H would lead to a cycle and would require to rehash the entire table.<\/figcaption><\/figure>\n

     <\/p>\n

    To insert an Item, we first try to insert the item into position h1(x). If the position is empty, we insert the item. But if it happens that the position if occupied, we throw out the existing key in that location and insert x. (This is the behaviour of the Cuckoo). Assuming the ejected key is y, then y is place in the alternative position which is h2(y). If also this position is occupied by a key z, the y repeats the same treatment: throws out z to make room. This process continues until a given threshold is reached.<\/p>\n

    In situation like this, if cycles are encountered, then we choose new has functions h1() and h2 and rehash or rebuild the entire table.<\/p>\n

     <\/p>\n

    2. The Cuckoo Hashing Algorithm<\/strong><\/p>\n

    The cuckoo hashing algorithm is given in Listing 1.0. The variable pos is used to maintain the current position where we are currently trying to insert an item.<\/p>\n

    <\/p>\n

    \n
    Procedure<\/span> insert (x)\n   if<\/span>(T<\/span>[h1(x) =<\/span> x or T<\/span>[h2(x) =<\/span> x \n\t   then<\/span> return\n   else<\/span>\n\t pos gets h1(x)\n\t Loop<\/span> n times {\n\t\tif<\/span> T<\/span>[pos] =<\/span> NULL<\/span>\n\t\t   then<\/span> T<\/span>[pos] gets x;\n\t\t   return\n\t\telse<\/span>\n\t\t   swap x and T<\/span>[pos]\n\t\t   if<\/span> pos =<\/span> h1(x) then<\/span> post gets h2(x) else<\/span> post gets h1(x)\n\t   rehash()<\/span>; insert(x)\nEnd<\/span>\n<\/pre>\n<\/div>\n
    Listing 1.0: Cuckoo Hashing Algorithm<\/p>\n
     <\/p>\n
    3. The Cuckoo Graph<\/strong><\/p>\n
    A cuckoo graph is formed from the movement of the keys between alternative positions in the hash table. This can be created from Figure 1.0. In the figure, the direction of the arrow on each of the edges indicate that the element can move along the edge to its alternative position<\/p>\n
    When inserting an item x, the insertion algorithm will only visit positions to which there is a path in the cuckoo graph from either of the two positions h1(x) and h2(x). In the event of a loop, then we go ahead to rehash.<\/p>\n
    Analysis of the cuckoo graph shows that insertion takes constant time in the absence\u00a0 of a rehashing.<\/p>\n
     <\/p>\n
    4. Cycles in Cuckoo\u00a0<\/strong>Graph<\/b><\/p>\n
    Assuming we want to insert a key Z. We would examine the\u00a0 two possible position h1(Z) and h2(Z) which are called buckets. Let’s also assume that h1(Z) hashes to W. Then then:<\/p>\n
      \n
    • W is moved to position of H<\/li>\n
    • H is moved to position of of H and this becomes a cycle which would require rehashing the table<\/li>\n<\/ul>\n
      If however h1(Z) hashes to the position of W and W moves to the position of A. Then a can move to position of B and B moves to an empty slot. In this case, there is not cycles.<\/p>\n
      5. Demo on the Cuckoo Hashing<\/strong>
      \n