# Folding Method in Hashing

**Folding Method in ****Hashing****:** It breaks up a key value into precise segments that are added to form a hash value, and look at another technique is to apply a multiplicative hash function to each segment individually before adding. Some folding methods go one step further and reverse every other piece before the addition. This folding method is **independent of distribution**.

**Algorithm:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

- The folding method is used for creating hash functions starts with the item being divided into equal-sized pieces i.e., the last piece may not be of equal size.
- The outcome of adding these bits together is the hash value,
**H(x) = (a + b + c) mod M**, where**M**is the table size, and**mod**stands for modulo. - In other words, the sum of three parts of the preconditioned key is divided by the table size. The remainder is the hash key.

**Explanation:**

**Example 1:** The task is to fold the key **123456789** into a Hash Table of ten spaces (0 through 9).

- It is given that the key, say
**X**is 123456789 and the table size (i.e.,**M**= 10). - Since it can break
**X**into three parts in any order. Let’s divide it evenly. - Therefore, a = 123, b = 456, c = 789.
- Now,
**H(x) = (a + b + c) mod M**i.e., H(123456789) =(123 + 456 + 789) mod 10 = 1368 mod 10 =**8**. - Hence, 123456789 is inserted into the table at address
**8**.

**Example 2:** The task is to fold the key **452378912** into a Hash Table of ten spaces (0 through 9).

- It is given that the key, say
**X**is**452378912**and the table size (i.e.,**M**= 10). - Since it can break
**X**into three parts in any order. Let’s divide it evenly. - Therefore, a = 452, b = 378, c = 912.
- Now,
**H(x) = (a + b + c) mod M**i.e., H(452378912) =(452 + 378 + 912) mod 10 = 1742 mod 10 =**2**. - Hence, 452378912 is inserted into the table at address
**2**.