Division Modulo Method is the simplest method of hashing. In this method, we divide the element with the size of the hash table and use the remainder as the index of the element in the hash table.

**Example 1:**

Size of Hash Table (m) = 1000 (0 - 999)

Suppose we want to calculate the index of element x, where x = 123789456

index =123789456 mod 1000

= 456

we store the element x at position 456 in the hash table.

**Example 2:**

m = 8 (0 - 7) ⇒ 2^{3}x = 10100101 *(In Binary)*

index = 10100101 mod 2^{3} ⇒ 101 ⇒ 5

**Example 3:**

m = 2^{k}x = 101001011011101101 *(In Binary)*

Index will be the k L.S.B (Least Significant Bits).

if k = 4, then the index will be 1101

## Problem with Division Modulo Method

There is one problem with this method, even if the element contains 1 lac bits, it will use only k least significant bit for the index.

**Example 4:**

m = 2^{4}x = 1010111011101010000010......101101 *(In Binary)*

Index = 1101

In example 3 and example 4 calculated index value is the same (4 LSB). Due to this, **collision **will occur.

## What is Collision

Collision in hashing is when two or more elements are fighting for the same slot in the hash table. In simple terms, we can say that If the hash function returns the same index for more than one element then the collision will occur.

## Solution to the problem

- Don't pick hash table size (m) exactly the power of 2, because if m = 2
^{k}then*HashFunction(m) = k LSB*always. - Pick hash table size (m) prime number, and make sure the value is not close to 2
^{k}.