Introduction to Hashing in Data Structure:

Hashing is a popular technique in computer science that involves mapping large data sets to fixed-
length values. It is a process of converting a data set of variable size into a data set of a fixed size. The
ability to perform efficient lookup operations makes hashing an essential concept in data structures.

What is Hashing?

A hashing algorithm is used to convert an input (such as a string or integer) into a fixed-size output
(referred to as a hash code or hash value). The data is then stored and retrieved using this hash value
as an index in an array or hash table. The hash function must be deterministic, which guarantees that
it will always yield the same result for a given input.

Hashing is commonly used to create a unique identifier for a piece of data, which can be used to
quickly look up that data in a large dataset. For example, a web browser may use hashing to store
website passwords securely. When a user enters their password, the browser converts it into a hash
value and compares it to the stored hash value to authenticate the user.

What is a hash Key?

In the context of hashing, a hash key (also known as a hash value or hash code) is a fixed-size
numerical or alphanumeric representation generated by a hashing algorithm. It is derived from the
input data, such as a text string or a file, through a process known as hashing.

Hashing involves applying a specific mathematical function to the input data, which produces a
unique hash key that is typically of fixed length, regardless of the size of the input. The resulting hash
key is essentially a digital fingerprint of the original data.

The hash key serves several purposes. It is commonly used for data integrity checks, as even a small
change in the input data will produce a significantly different hash key. Hash keys are also used for
efficient data retrieval and storage in hash tables or data structures, as they allow quick look-up and
comparison operations.

How Hashing Works?

The process of hashing can be broken down into three steps:

o Input: The data to be hashed is input into the hashing algorithm.

o Hash Function: The hashing algorithm takes the input data and applies a mathematical
function to generate a fixed-size hash value. The hash function should be designed so that
different input values produce different hash values, and small changes in the input produce
large changes in the output.

o Output: The hash value is returned, which is used as an index to store or retrieve data in a
data structure.
Hashing Algorithms:

There are numerous hashing algorithms, each with distinct advantages and disadvantages. The most
popular algorithms include the following:

o MD5: A widely used hashing algorithm that produces a 128-bit hash value.

o SHA-1: A popular hashing algorithm that produces a 160-bit hash value.

o SHA-256: A more secure hashing algorithm that produces a 256-bit hash value.

Hash Tables

A hash table is a data structure that offers efficient data retrieval through the use of a hash function.
It is primarily used to implement associative arrays, sets, and other collections where quick access to
data via a key is necessary.

Key Components of a Hash Table:

1. Keys: Unique identifiers for the data, used to retrieve or store values in the hash table.

2. Values: Data associated with a key, which is stored in the hash table.
3. Hash Function: A function that converts a key into an index (or hash value) in the hash table.
This index determines where the value corresponding to the key is stored.

4. Buckets or Slots: The array positions where values are stored in the table. Each bucket can
store one or more values, depending on how collisions are handled.

Hash Table Operations:

1. Insertion: Inserting a key-value pair into the hash table involves applying the hash function to
the key to determine the appropriate index. The value is then stored at that index.
2. Search: To retrieve a value associated with a specific key, the hash function is applied to the
key, and the index is checked to find the corresponding value.
 3. Deletion: To delete a key-value pair, the key is hashed to find the index, and the value at that
index is removed.

4. Updating: Updating the value for an existing key involves searching for the key, then
replacing the old value with the new one.

Hash Function:

Hash Function: A hash function is a type of mathematical operation that takes an input (or key) and
outputs a fixed-size result known as a hash code or hash value. The hash function must always yield
the same hash code for the same input in order to be deterministic. Additionally, the hash function
should produce a unique hash code for each input, which is known as the hash property.

The hash function plays a crucial role in determining the efficiency of a hash table. A good hash
function should:

 Distribute keys uniformly across the hash table to minimize collisions.

 Be fast to compute.

 Ensure that similar keys do not hash to the same index.

A typical hash function for a key k is:

hash(k)=k % TABLE_SIZE

where TABLE_SIZE is the number of slots in the hash table.

Properties of good hash functions:

A good hash function is crucial for the efficiency of a hash table, as it directly affects the distribution
of keys and the handling of collisions. The properties of a good hash function ensure that the hash
table performs well under typical operations such as insertion, search, and deletion.

Here are the key properties of a good hash function:

1. Uniform Distribution (Minimizing Collisions)

 A good hash function should distribute keys uniformly across the hash table.

 This means that the hash values (indices) for different keys should be spread out as evenly as
possible across the table to minimize the occurrence of collisions (when two different keys
map to the same index).

 A uniform distribution reduces the chances that many keys will cluster together, which can
slow down performance.

2. Deterministic

 The hash function must be deterministic, meaning that for a given key, it always produces
the same hash value.

 This ensures that a key will always be placed in the same index of the hash table every time it
is accessed or inserted.

3. Efficient to Compute

 A good hash function should be computationally efficient.

  It should produce the hash value in constant time O(1)O(1)O(1), which ensures that the
performance of hash table operations remains fast even as the table grows.

4. Low Probability of Collisions

 A collision occurs when two different keys hash to the same index. A good hash function
minimizes the probability of collisions.

 While collisions are inevitable (because there are an infinite number of possible keys and a
finite number of slots), a good hash function minimizes the likelihood by spreading the keys
evenly across the table.

 In general, using a larger hash table (i.e., increasing the number of slots) can reduce the
probability of collisions.

5. Avoids Clustering

 Clustering occurs when a large number of keys hash to adjacent or nearby slots. This results
in inefficient use of the hash table, increasing the number of collisions.

 A good hash function should avoid clustering by ensuring that the keys are well distributed
across the entire table, not just a localized area.

6. Sensitivity to Changes in Input

 A good hash function should be sensitive to small changes in the input key. A small
modification to the input (such as changing one character in a string) should result in a
significantly different hash value.

 This ensures that even similar keys don't end up with the same hash, which could otherwise
increase the likelihood of collisions.

7. Works Well with the Key Type

 The hash function should be tailored to the type of keys being used. For example:

o For integers, a simple modulo operation (key % table_size) may suffice.

o For strings, more complex hash functions that take each character into account and
combine them in some way (e.g., using polynomial hashing) are needed.

 The hash function should take advantage of the properties of the key type to minimize
collisions and ensure a uniform distribution.

8. Minimizes Hash Table Resizing

 A good hash function helps minimize the need for rehashing (resizing the hash table) by
reducing the load factor and ensuring that keys are evenly distributed across the table.

 Frequent resizing can be costly in terms of time and memory usage, so a good hash function
can reduce the frequency of rehashing.

9. Efficient for the Table Size

 The hash function should work well with the size of the hash table, which is typically a prime
number or close to a power of 2.
  Using table sizes that are powers of two can sometimes cause issues with certain hash
functions due to the binary representation of numbers. Prime numbers are often used to
reduce these issues and distribute the hash values better.

Example of a Good Hash Function for Strings (Polynomial Hashing):

For strings, one popular approach to creating a good hash function is polynomial hashing, which
computes the hash as follows:

hash(s)=(s0×b0+s1×b1+s2×b2+⋯+sn−1×bn−1) % p

Where:

 s0,s1,…,sn−1 are the ASCII values (or other character encoding) of the string characters.

 bis a constant base (often chosen to be a small prime number, such as 31 or 37).

 p is a large prime number used to prevent overflow and reduce collisions.

This method ensures that the hash value is sensitive to changes in each character of the string and
helps distribute values more uniformly.

Summary of Good Hash Function Properties:

 Uniform distribution of keys.

 Deterministic behavior for consistent results.

 Efficient computation to maintain fast operations.

 Low collision probability to prevent clustering.

 Sensitivity to input changes to avoid hash value duplication.

 Tailored to work with the key type for optimal performance.

 Reduces the need for rehashing and resizing.

DIFFERENT HASH FUNCTIONS

1. Division Method (Modulo Method)

This is one of the simplest and most widely used hash functions. The key is divided by the table size,
and the remainder of that division is used as the hash value (index).

Formula:

hash(key)=key% TABLE_SIZE

Where:

 key is the value that we want to hash.

 TABLE_SIZE is the number of slots in the hash table.

Example:

Let’s assume a table size of 10, and we want to hash the keys 25, 36, and 42.

 For key 25: 25% 10=5

  For key 36: 36% 10=6

 For key 42: 42% 10=2

 Result: The keys 25, 36, and 42 are mapped to indices 5, 6, and 2, respectively.

Pros:

 Simple to implement and understand.

 Fast computation.

Cons:

 If the table size is not chosen properly (especially not a prime number), it may lead to poor
distribution of keys and clustering.

2. Multiplicative Method
This method multiplies the key by a constant A takes the fractional part of the product, and then
scales it by the table size. The resulting value is then used as the hash index.

Formula:

hash(key)=⌊TABLE_SIZE×(key× A %1)⌋

Where:

 A is a constant chosen such that 0< A <1, often A=0.6180339887A =

0.6180339887A=0.6180339887 (related to the golden ratio).

 The fractional part of key × A is taken, which helps distribute the keys better.

Example:

Let’s assume a table size of 10, and A=0.6180339887

For key 25:

25×0.6180339887=15.4508497175

The fractional part is 0.4508497175. Now, multiply it by the table size (10):

10×0.4508497175=4.508497175

Rounding this to the nearest integer gives a hash value of 4.

Result: The key 25 maps to index 4.

Pros:

 Provides better distribution of hash values than the division method, even when the table
size is not a prime number.

Cons:

 Slightly more complex to implement than the division method.

  Needs a good choice of AAA to minimize clustering.

3. Mid-Square Method

In the Mid-Square Method, the key is squared, and then the middle digits of the resulting number
are taken as the hash value. This method helps in spreading out the hash values better.

Formula:

hash(key)=Middle digits of (key2)

Where:

 The key is squared, and a portion of the result (typically the middle digits) is taken as the
hash.

Example:

Let’s hash the key 25. First, square the key:

252=625

Next, extract the middle digits (in this case, "62").

Result: The hash value is 62.

For key 36:

362=1296

Extract the middle digits ("29").

Result: The hash value is 29.

Pros:

 Provides a good distribution of hash values if the key is large.

 Avoids clustering by extracting a portion of the squared value.

Cons:

 The result may be too large for small keys or table sizes, requiring truncation or modulo
operations.

 Works better with larger integers.

4. Folding Method

The Folding Method splits the key into equal-sized chunks, adds the chunks together, and then
possibly applies a modulo operation to fit the result into the table size. This is often used when
dealing with keys that are strings or multi-digit numbers.

Formula:

1. Split the key into equal-sized parts.

 2. Add up the parts.

3. If necessary, take the sum modulo the table size.

Example:

Let’s hash the key 123456. We divide it into two parts: 123 and 456.

1. Add the parts: 123+456=579

2. Now, take the modulo with the table size (say, 10):

579 % 10=9

Result: The hash value is 9.

For key 987654:

1. Split it into two parts: 987 and 654.

2. Add the parts: 987+654=1641

3. Take modulo 10: 1641 % 10=1

Result: The hash value is 1.

Pros:

 Simple to implement and works well for multi-digit or string keys.

 Reduces the impact of key patterns.

Cons:

 The quality of distribution depends on how the key is split. Poor splitting can lead to
collisions.

 May not be as effective for small integer keys.

Summary of Hash Functions:

Method Formula Pros Cons

hash(key)=key% TABLE_SIZE Can lead to clustering if

Division Simple to
table size isn’t chosen
Method implement and fast
carefully

Better distribution
hash(key)=⌊TABLE_SIZE×(key× A than division More complex to
Multiplicative %1)⌋
method, good even implement, requires good
Method
for non-prime table choice of constant AAA
sizes

May require
Mid-Square hash(key)=Middle digits of (key2) Helps spread out truncation/modulo for
Method hash values small keys, works better
for large integers

Depends on how well the

Folding Split the key into parts, add parts, Good for large keys,
key is split, can result in
Method take modulo easy to implement
collisions if poorly split

Here is a comparison of the four hash functions: Division Method, Multiplicative Method, Mid-
Square Method, and Folding Method. Each method has its strengths and weaknesses depending on
the type of data, table size, and distribution requirements.

Comparison Table

Feature Division Method Multiplicative Method Mid-Square Method Folding Method

Key multiplied by Key squared, and Key split into

Basic Key modulo table
constant A, fractional middle digits taken chunks, summed,
Concept size.
part used. as hash. and modulo taken.

Split key, sum parts,

hash(key)=key% hash(key)=⌊TABLE_SIZE× hash(key)=Middle dig
Formula take modulo table
TABLE_SIZE (key×A%1)⌋ its of (key2)
size.

Slightly more
Ease of complex due to Easy to implement,
Very simple to Requires choosing a
Implem squaring and but requires careful
implement. good constant A.
entation extracting middle splitting of key.
digits.

Slightly more Generally fast, but

Perform Slower, especially for
Fast and efficient. computationally depends on how the
ance large keys.
expensive than division. key is split.
Feature Division Method Multiplicative Method Mid-Square Method Folding Method

Susceptible to Good distribution Can reduce

Collision
clustering if table Better distribution than but may have issues clustering but
Resistan
size is not a prime division method. with very large depends on key
ce
number. numbers. splitting.

Produces better Moderate

May produce poor Good distribution for
Hash distribution, especially distribution quality;
distribution if table large integer keys,
Quality for non-prime table splitting can lead to
size is not optimal. especially for strings.
sizes. collisions.

Cases needing good

Simple cases with Suitable for large
Use distribution, especially Best for multi-digit
small numbers or keys, especially
Cases with non-prime table or string keys.
known patterns. integers or strings.
sizes.

Can produce very

Poor performance Needs a well-chosen Poor splitting could
Commo large numbers,
with certain table constant A to avoid poor result in poor
n Issues requiring
sizes. distribution. distribution.
truncation/modulo.

Key 25 and A=0.618

Key 25 → Key 123456 → split
Key 25 and table size →25×0.618=15.45,
Example 252=625,middle into 123 and 456,
10 → 25 % 10=5. fractional part is 0.45 →
digits 62. sum 579, % 10 → 9.
10×0.45=4.

Key Points of Comparison

1. Simplicity:

o Division Method is the easiest to implement, requiring only a modulo operation.

o Multiplicative Method is slightly more complex because it involves multiplying by a

constant and handling the fractional part.

o Mid-Square Method is more complex as it involves squaring the key and extracting
middle digits.

o Folding Method is relatively simple but requires good key splitting to prevent
collisions.

2. Performance:

o Division Method is the fastest, as it only involves a modulo operation.

o Multiplicative Method is slower than division, but still quite efficient.

o Mid-Square Method is slower because it requires squaring the key, which can be
computationally expensive for large values.

o Folding Method is generally fast, but performance depends on how the key is split.
 3. Collision Resistance:

o Division Method is prone to clustering and collisions, especially if the table size is
not chosen properly (not a prime number).

o Multiplicative Method provides better distribution than the division method and
works well even with non-prime table sizes.

o Mid-Square Method can provide good distribution, but very large numbers can
cause issues with overflow or truncation.

o Folding Method helps avoid clustering but depends on how the key is split. Poor
splitting can lead to collisions.

4. Hash Quality:

o Division Method may not distribute the hash values evenly if the table size is poorly
chosen.

o Multiplicative Method usually provides good distribution, especially for large keys or
non-prime table sizes.

o Mid-Square Method typically produces a good distribution of hash values, especially

for large keys or strings.

o Folding Method has moderate distribution quality, but its effectiveness depends on
how the key is divided.

5. Use Cases:

o Division Method is ideal for small data sets with simple keys or when a quick and
efficient hash is needed.

o Multiplicative Method is suitable for larger data sets or when the table size is not a
prime number, and you need better distribution.

o Mid-Square Method works well for large integer keys or strings where the key is
squared and middle digits are extracted.

o Folding Method is particularly effective for string keys or multi-digit numbers, as it

splits the key and reduces collisions by adding the parts together.

Summary

 Division Method: Best for simplicity and speed with small datasets, but suffers from poor
distribution if the table size isn't optimal.

 Multiplicative Method: Offers a better hash distribution, especially with non-prime table
sizes, at the cost of slightly more complexity.

 Mid-Square Method: Effective for larger keys and provides better distribution, but can be
slow for large keys.

 Folding Method: Works well for multi-digit or string keys but depends heavily on how the
key is split, which may impact collision resistance.
Collision in Hashing

A collision occurs in a hash table when two different keys produce the same hash value (i.e., they
map to the same index). Since hash tables rely on unique indices to store and retrieve data
efficiently, handling collisions is crucial to maintain their performance and reliability.

Causes of Collisions

1. Limited Table Size: If the hash table has fewer slots than the total number of keys, collisions
are inevitable.

2. Poor Hash Function: A hash function that doesn't distribute keys uniformly increases the
likelihood of collisions.

3. Key Characteristics: If keys have patterns or clusters (e.g., sequential numbers), they may
hash to the same value more often.

Collision Resolution Techniques

1. Open Addressing

Open addressing resolves collisions by finding another empty slot within the table when a collision
occurs. Several strategies exist:

 Linear Probing:

o Start at the collided index and search sequentially for the next empty slot.

o Formula: hash(key , i)=(hash(key)+ i ) %TABLE_SIZE

o Example:

 Keys: 10, 20, 30

 Table size: 7

 Hash function: key % 7

 Hash(10) = 3, Hash(20) = 6, Hash(30) = 3 (collision).

 Linear probing: Place 30 at index 4 (next empty slot).

o Pros: Simple and easy to implement.

o Cons: Causes clustering (keys cluster together, making collisions more frequent).

 Quadratic Probing:

o Search for empty slots by jumping in quadratic increments.

o Formula: hash(key,i)=(hash(key)+i2)% TABLE_SIZE

o Pros: Reduces clustering.

o Cons: May still fail to find an empty slot if the table is nearly full.
  Double Hashing:

o Use a secondary hash function to determine the jump size.

o Formula: hash(key,i)=(hash(key)+i⋅hash2(key))%TABLE_SIZE

o Pros: Reduces clustering significantly.

o Cons: More complex than linear or quadratic probing.

2. Chaining

In chaining, each slot in the hash table holds a linked list (or another data structure) of all keys that
hash to the same value. When a collision occurs, the new key is simply added to the list at that slot.

 Example:

o Keys: 10, 20, 30

o Table size: 7

o Hash function: key % 7

o Hash(10) = 3, Hash(20) = 6, Hash(30) = 3 (collision).

o Solution: At index 3, store a linked list with keys [10, 30].

 Pros:

o Simple to implement.

o Allows the hash table to store more keys than there are slots.

 Cons:

o Performance degrades if many keys hash to the same slot, as linked lists grow longer.

o Uses extra memory for the linked list.

3. Bucketing

Similar to chaining, but instead of linked lists, each slot contains a fixed-size bucket (array) to store
multiple keys. If the bucket is full, other resolution techniques (like chaining) can be used.

 Pros: Easy to implement and manage for small numbers of collisions.

 Cons: Limited bucket size can still lead to issues.

4. Separate Hash Tables (Rehashing)

When a collision occurs, use a different hash function or a second hash table to resolve it.

 Pros:

o Minimizes clustering.
 o Provides better performance for highly colliding keys.

 Cons:

o Requires additional computation and memory.

Comparison of Collision Resolution Methods

Ease of
Method Space Usage Performance Clustering
Implementation

Linear High (primary

Efficient Good for low load factor Simple
Probing clustering)

Quadratic
Efficient Better than linear probing Moderate Moderate
Probing

Double Excellent if hash functions

Efficient Complex Minimal
Hashing are well-chosen

Extra memory for Good, depends on chain

Chaining Simple None
chains length

Preallocated
Bucketing Depends on bucket size Simple None
memory

Choosing a Resolution Method

1. Chaining is preferred when:

o Memory is not a constraint.

o Keys may not be evenly distributed.

2. Open Addressing methods (Linear, Quadratic, or Double Hashing) are better when:

o Memory usage is critical.

o You want to avoid extra memory for pointers (as in chaining).

3. Double Hashing is suitable when:

o A highly uniform distribution is needed.

o The application can afford the complexity.

4. Bucketing is good for:

o Systems where memory allocation is limited to arrays.

Collision Resolution by Open Addressing

Open addressing is a collision resolution technique where, instead of chaining keys in linked lists or
separate structures, collisions are resolved by probing the hash table itself to find the next available
slot. When a collision occurs, the algorithm looks for an empty slot using a specific probing sequence.

Key Concepts of Open Addressing

1. Single Array:

o All keys are stored in the hash table itself; no separate data structures like linked lists
are used.

2. Probing:

o A systematic way to find the next available slot. Common probing techniques
include:

 Linear Probing

 Quadratic Probing

 Double Hashing

3. Load Factor:

o Defined as α=α=number of key/stable size

o As α approaches 1, collisions increase, making open addressing slower.

4. Deletion:

o Deleting a key directly creates gaps, disrupting the search sequence. Special markers,
like "DELETED", are used to maintain search consistency.

Linear Probing with Example

In linear probing, when a collision occurs, the algorithm searches for the next available slot
sequentially (one position at a time) until an empty slot is found.

Hash Function Formula

hash(key,i)=(hash(key)+i)%TABLE_SIZE

Where:

 hash(key)): Primary hash function.

 iii: Number of probes (starting from 000).

Example

 Keys to Insert: 10,22,31,44,15,28

  Table Size: 7

 Hash Function: key% 7

Step-by-Step Insertion:

1. Insert 10:

o 10% 7=3

o Index 3 is empty. Insert 10 at index 3.

Hash Table:
[ - , - , - , 10 , - , - , - ]

2. Insert 22:

o 22% 7=1

o Index 1 is empty. Insert 22 at index 1.

Hash Table:
[ - , 22 , - , 10 , - , - , - ]

3. Insert 31:

o 31% 7=3

o Index 3 is occupied (collision).

o Probe: (3+1)% 7=4

o Index 4 is empty. Insert 31 at index 4.

Hash Table:
[ - , 22 , - , 10 , 31 , - , - ]

4. Insert 44:

o 44%7=2

o Index 2 is empty. Insert 44 at index 2.

Hash Table:
[ - , 22 , 44 , 10 , 31 , - , - ]

5. Insert 15:

o 15% 7=1

o Index 1 is occupied (collision).

o Probe: (1+1)% 7=2 .

o Index 2 is occupied (collision).

o Probe: (1+2)% 7=3

o Index 3 is occupied (collision).

 o Probe: (1+3)% 7=4 .

o Index 4 is occupied (collision).

o Probe: (1+4)% 7=5.

o Index 5 is empty. Insert 15 at index 5.

Hash Table:
[ - , 22 , 44 , 10 , 31 , 15 , - ]

6. Insert 28:

o 28% 7=0

o Index 0 is empty. Insert 28 at index 0.

Final Hash Table:

[ 28 , 22 , 44 , 10 , 31 , 15 , - ]

Search Example

 To search for 15:

1. 15% 7=1

2. Check index 1. 22≠15 (collision).

3. Probe: (1+1)% 7=2 . 44≠15 (collision).

4. Probe: (1+2)% 7=3. 10≠15 (collision).

5. Probe: (1+3)% 7=4. 31≠15 (collision).

6. Probe: (1+4)% 7=5. 15=15 . Found!

Advantages of Linear Probing

1. Simple to implement.

2. Efficient for low load factors (α<0.5\alpha < 0.5α<0.5).

Disadvantages of Linear Probing

1. Primary Clustering: Consecutive occupied slots increase collision probability.

2. Performance Degrades as the table becomes full.

Quadratic Probing with Example

In quadratic probing, when a collision occurs, the algorithm searches for an empty slot by jumping
quadratically in the hash table. This reduces clustering compared to linear probing.

Hash Function Formula

hash(key,i)=(hash(key)+i2)% TABLE_SIZE

Where:

 hash(key): Primary hash function.

 iii: Number of probes (starting from 000).

Example

 Keys to Insert: 10,22,31,44,15,28

 Table Size: 777

 Hash Function: key % 7

Step-by-Step Insertion:

1. Insert 10:

o 10% 7=3

o Index 3 is empty. Insert 10 at index 3.

Hash Table:
[ - , - , - , 10 , - , - , - ]

2. Insert 22:

o 22% 7=1

o Index 1 is empty. Insert 22 at index 1.

Hash Table:
[ - , 22 , - , 10 , - , - , - ]

3. Insert 31:

o 31% 7=3

o Index 3 is occupied (collision).

o Probe:
(3+12)% 7=4.
Index 4 is empty. Insert 31 at index 4.

Hash Table:
[ - , 22 , - , 10 , 31 , - , - ]
 4. Insert 44:

o 44% 7=2

o Index 2 is empty. Insert 44at index 2.

Hash Table:
[ - , 22 , 44 , 10 , 31 , - , - ]

5. Insert 15:

o 15%7=1

o Index 1 is occupied (collision).

o Probe:
(1+12)% 7=2.
Index 2 is occupied (collision).
(1+22)% 7=5.
Index 5 is empty. Insert 15 at index 5.

Hash Table:
[ - , 22 , 44 , 10 , 31 , 15 , - ]

6. Insert 28:

o 28% 7=0

o Index 0 is empty. Insert 28 at index 0.

Final Hash Table:

[ 28 , 22 , 44 , 10 , 31 , 15 , - ]

Search Example

To search for 15:

1. Compute the hash value: 15% 7=1.

2. Check index 1. 22≠15 (collision).

3. Probe using quadratic probing:

o (1+12)% 7=2. 44≠15 (collision).

o (1+22)% 7=5. 15=15= 15. Found!

Key Points

 Probing Sequence: Quadratic probing skips indices further apart as iii increases, reducing
clustering.

 Key Distribution: Quadratic probing reduces primary clustering but suffers from secondary
clustering (keys with the same hash value follow the same sequence).
Advantages of Quadratic Probing

1. Reduces Clustering: Quadratic jumps reduce the chances of consecutive occupied slots.

2. Simple to Implement: Slightly more complex than linear probing but still straightforward.

Disadvantages of Quadratic Probing

1. Table Size Requirement: Works best when the table size is a prime number to ensure all slots
can be probed.

2. Secondary Clustering: Keys with the same hash value follow the same sequence.

3. Performance Degrades for High Load Factor: Like linear probing, performance decreases as
the table becomes full.

Comparison to Linear Probing

Feature Linear Probing Quadratic Probing

Clustering Primary clustering occurs Secondary clustering only

Ease of Implementation Very simple Slightly more complex

Probing Sequence Sequential Quadratic gaps

Performance Degrades faster More robust under collisions

Double Hashing with Example

In double hashing, a second hash function is used to calculate the probe step size. This reduces
clustering and ensures a better spread of keys across the table.

Hash Function Formula

hash(key,i)=(hash1(key)+i⋅hash2(key))% TABLE_SIZE

Where:

 hash1(key): Primary hash function.

 hash2(key): Secondary hash function.

 iii: Number of probes (starting from 000).

Example

 Keys to Insert: 10,22,31,44,15,28

  Table Size: 7

 Hash Functions:

o hash1(key)=key% 7

o hash2(key)=1+(key % (TABLE_SIZE−1))

Step-by-Step Insertion:

1. Insert 10:

o hash1(10)=10% 7=3

o Index 3 is empty. Insert 10 at index 3.

Hash Table:
[ - , - , - , 10 , - , - , - ]

2. Insert 22:

o hash1(22)=22% 7=1.

o Index 1 is empty. Insert 22 at index 1.

Hash Table:
[ - , 22 , - , 10 , - , - , - ]

3. Insert 31:

o hash1(31)=31% 7=3.

o Index 3 is occupied (collision).

o Compute hash2(31)=1+(31% 6)=1+1=2

o Probe using double hashing:

 (3+1⋅2) % 7=5.

 Index 5 is empty. Insert 31 at index 5.

Hash Table:
[ - , 22 , - , 10 , - , 31 , - ]

4. Insert 44:

o hash1(44)=44% 7=2.

o Index 2 is empty. Insert 44 at index 2.

Hash Table:
[ - , 22 , 44 , 10 , - , 31 , - ]

5. Insert 15:

o hash1(15)=15% 7=1.

o Index 1 is occupied (collision).

 o Compute hash2(15)=1+(15% 6)=1+3=4.

o Probe using double hashing:

 (1+1⋅4) % 7=5. Index 5 is occupied (collision).

 (1+2⋅4) %7=2. Index 2 is occupied (collision).

 (1+3⋅4) % 7=6. Index 6 is empty. Insert 15 at index 6.

Hash Table:
[ - , 22 , 44 , 10 , - , 31 , 15 ]

6. Insert 28:

o hash1(28)=28% 7=0

o Index 0 is empty. Insert 28 at index 0.

Final Hash Table:

[ 28 , 22 , 44 , 10 , - , 31 , 15 ]

Search Example

To search for 15:

1. Compute the hash value: hash1(15)=1.

2. Check index 1. 22≠15 (collision).

3. Compute hash2(15)=4.

4. Probe:

o (1+1⋅4) % 7=5. 31≠15 (collision).

o (1+2⋅4) % 7=2. 44≠15(collision).

o (1+3⋅4)mod 7=6. 15=15. Found!

Key Points

 Probing Sequence: Double hashing skips indices at variable intervals, reducing both primary
and secondary clustering.

 Key Distribution: Double hashing achieves a more uniform distribution than linear or
quadratic probing.

Advantages of Double Hashing

1. Minimal Clustering: Reduces both primary and secondary clustering significantly.

2. Efficient Key Distribution: Provides a uniform spread of keys for well-chosen hash functions.
 3. Suitable for High Load Factors: Performs well even at higher load factors compared to other
open addressing techniques.

Disadvantages of Double Hashing

1. Complexity: Requires two hash functions, making it slightly more computationally expensive.

2. Key Dependence: Performance depends heavily on the choice of the second hash function.

3. Table Size: Works best when the table size is a prime number.

Comparison to Linear and Quadratic Probing

Feature Linear Probing Quadratic Probing Double Hashing

Clustering Primary clustering Secondary clustering Minimal clustering

Ease of Implementation Very simple Slightly more complex Most complex

Probing Sequence Sequential Quadratic gaps Based on second hash

Performance Degrades faster Moderate Best at higher load factors

Chaining for Collision Resolution

Chaining is a collision resolution method where each index in the hash table stores a linked list (or
another data structure like a dynamic array) to hold all keys that hash to the same index. This allows
multiple keys to occupy the same index without probing for other slots.

How It Works

1. Hash Function:

o Compute the index for a key using a hash function: index=hash(key) % TABLE_SIZE

2. Insertion:

o If the index is empty, insert the key as the first element.

o If the index is already occupied, append the key to the linked list at that index.

3. Search:

o Compute the hash index for the key.

o Traverse the linked list at that index to find the key.

4. Deletion:

o Compute the hash index for the key.

o Traverse the linked list to find and delete the key.

Example

 Keys to Insert: 10,22,31,44,15,28

 Table Size: 7

 Hash Function: key % 7

Step-by-Step Process

1. Insert 10:

o 10% 7=3.

o Index 3 is empty. Insert 10 as the first element in a linked list.

Hash Table:
[ - , - , - , [10] , - , - , - ]

2. Insert 22:

o 22% 7=1.

o Index 1 is empty. Insert 22 as the first element in a linked list.

Hash Table:
[ - , [22] , - , [10] , - , - , - ]

3. Insert 31:

o 31% 7=3.

o Index 3 is occupied. Append 31 to the linked list at index 3.

Hash Table:
[ - , [22] , - , [10 → 31] , - , - , - ]

4. Insert 44:

o 44% 7=2.

o Index 2 is empty. Insert 44as the first element in a linked list.

Hash Table:
[ - , [22] , [44] , [10 → 31] , - , - , - ]

5. Insert 15:

o 15% 7=1.

o Index 1 is occupied. Append 15 to the linked list at index 1.

Hash Table:
[ - , [22 → 15] , [44] , [10 → 31] , - , - , - ]

6. Insert 28:

o 28%7=0.
 o Index 0 is empty. Insert 28 as the first element in a linked list.
Final Hash Table:
[ [28] , [22 → 15] , [44] , [10 → 31] , - , - , - ]

Search Example

To search for 15:

1. Compute the hash index: 15%7=1.

2. Check the linked list at index 1: Traverse [22→15][22 → 15][22→15].

3. 15 is found in the linked list.

Advantages of Chaining

1. Handles Collisions Efficiently: Multiple keys can be stored at the same index without needing
to probe.

2. Dynamic Storage: Linked lists (or dynamic arrays) can grow to accommodate more keys.

3. No Clustering: Unlike linear or quadratic probing, chaining doesn't suffer from clustering.

4. High Load Factor: Can handle a load factor greater than 111.

Disadvantages of Chaining

1. Extra Memory Overhead: Linked lists require additional memory for pointers.

2. Potentially Slow Searches: As the number of keys in a bucket grows, search time increases.

3. Poor Cache Performance: Linked lists often result in non-contiguous memory access, which
can slow down performance.

Comparison to Open Addressing

Feature Open Addressing Chaining

Memory Use Fixed-size table Requires additional memory for linked lists.

Collisions Resolves by probing Resolves by adding to a linked list.

Load Factor Limited (<1< 1<1) Can exceed 111.

Clustering Prone to clustering No clustering.

Performance Degrades with load More stable under high loads.

3. Bucketing
In bucketing, each slot in the hash table contains a "bucket" capable of holding multiple keys. This is
similar to chaining, but instead of using a linked list or dynamic structure, the bucket is usually a
fixed-size array.

How It Works

1. Hash Function:

o Compute the index for a key: index=hash(key) % TABLE_SIZE

2. Insertion:

o Insert the key into the bucket at the computed index.

o If the bucket overflows (reaches its fixed capacity), apply overflow handling:

 Use another data structure for additional keys (e.g., linked list or secondary
bucket).

 Rehash the table if too many keys overflow.

3. Search:

o Compute the hash index.

o Search within the bucket for the key.

4. Deletion:

o Compute the hash index.

o Search and remove the key from the bucket.

Example

 Keys to Insert: 10,22,31,44,15,28

 Table Size: 7

 Bucket Size: 2 (each bucket can hold up to 2 keys)

 Hash Function: key %7

Step-by-Step Process

1. Insert 10:

o 10 % 7=3.

o Insert 10 into the bucket at index 3.

Hash Table:
[ -, -, -, [10], -, -, - ]

2. Insert 22:

o 22 % 7=1.
 o Insert 22 into the bucket at index 1.
Hash Table:
[ -, [22], -, [10], -, -, - ]

3. Insert 31:

o 31 % 7=3.

o Insert 31 into the bucket at index 3.

Hash Table:
[ -, [22], -, [10, 31], -, -, - ]

4. Insert 44:

o 44 %7=2.

o Insert 44 into the bucket at index 2.

Hash Table:
[ -, [22], [44], [10, 31], -, -, - ]

5. Insert 15:

o 15 % 7=1.

o Bucket at index 1 has space. Insert 15.

Hash Table:
[ -, [22, 15], [44], [10, 31], -, -, - ]

6. Insert 28:

o 28% 7=0.

o Insert 28 into the bucket at index 0.

Final Hash Table:
[ [28], [22, 15], [44], [10, 31], -, -, - ]

Advantages of Bucketing

1. Efficient Handling of Collisions: Fixed-size buckets reduce memory overhead compared to

chaining.

2. Simple Search and Insert: Searches are confined to small buckets.

3. Reduced External Structures: No need for dynamic memory allocation unless buckets
overflow.

Disadvantages of Bucketing

1. Fixed Bucket Size: Overflow handling can complicate the implementation.

2. Memory Utilization: Buckets must be sized carefully to balance memory usage and
performance.

4. Separate Hash Tables (Rehashing)

In separate hash tables with rehashing, collisions are handled by maintaining a secondary hash table
for each index in the primary hash table.

How It Works

1. Primary Hash Table:

o Compute the hash index using the main hash function: index=hash1(key)
% TABLE_SIZE

2. Secondary Hash Table:

o If a collision occurs at a primary table index, maintain a separate hash table for that
index.

o Use a different hash function (e.g., hash2(key)\text{hash2}(key)hash2(key)) for the

secondary table.

3. Rehashing:

o If the primary or secondary hash tables become too full, rehash to a larger table size.

o Keys are redistributed to new tables based on the updated hash functions.

Example

 Keys to Insert: 10,22,31,44,15,28

 Primary Table Size: 7

 Secondary Table Size: 3

 Primary Hash Function: key % 7

 Secondary Hash Function: key % 3

Step-by-Step Process

1. Insert 10:

o 10% 7=3.

o Insert 10 in the primary table at index 3.

Primary Table:
[ -, -, -, [10], -, -, - ]

2. Insert 22:

o 22% 7=1.

o Insert 22 in the primary table at index 1.

Primary Table:
[ -, [22], -, [10], -, -, - ]

3. Insert 31:
 o 31% 7=3.

o Collision at index 3. Create a secondary table for index 3.

o Compute secondary hash: 31% 3=1.

o Insert 31 in the secondary table at index 1.

Primary Table:
[ -, [22], -, [10 → Secondary Table], -, -, - ]
Secondary Table at Index 3:
[ -, [31], - ]

4. Insert 44:

o 44% 7=2.

o Insert 44 in the primary table at index 2.

Primary Table:
[ -, [22], [44], [10 → Secondary Table], -, -, - ]

5. Insert 15:

o 15% 7=1.

o Collision at index 1. Create a secondary table for index 1.

o Compute secondary hash: 15%3=0.

o Insert 15in the secondary table at index 0.

Primary Table:
[ -, [22 → Secondary Table], [44], [10 → Secondary Table], -, -, - ]
Secondary Table at Index 1:
[ [15], -, - ]

6. Insert 28:

o 28% 7=0.

o Insert 28 in the primary table at index 0.

Final Primary Table:
[ [28], [22 → Secondary Table], [44], [10 → Secondary Table], -, -, - ]

Advantages of Separate Hash Tables

1. Independent Collision Resolution: Each index resolves collisions independently.

2. Scalability: Secondary tables can scale independently.

3. No Clustering: Minimal interference between keys.

Disadvantages of Separate Hash Tables

1. Memory Overhead: Requires separate memory for secondary tables.

2. Complexity: Managing multiple tables increases implementation complexity.

 3. Rehashing Cost: Rehashing can be computationally expensive.

Comparison of Collision Resolution Methods

The following table summarizes and compares the collision resolution methods: Linear Probing,
Quadratic Probing, Double Hashing, Chaining, Bucketing, and Separate Hash Tables (Rehashing).

Separate
Linear Quadratic Double
Aspect Chaining Bucketing Hash Tables
Probing Probing Hashing
(Rehashing)

Uses linked Each index

Searches Probes Uses a
lists or Each slot stores maintains its
sequentially quadraticall second hash
Concept dynamic a fixed-size own
for next y to find the function for
structures at array (bucket). secondary
empty slot. next slot. probing.
each index. hash table.

Primary No
Avoids
Clustering Secondary clustering, No clustering,
clustering No clustering,
occurs due Clustering as keys are keys handled
Clustering with a but overflows
to (less severe stored in independentl
secondary may occur.
sequential than linear). separate y.
hash.
search. structures.

Performanc
Better than
Efficient even e depends Efficient for
Fast for low linear Efficient for
with high on the independent
load factors. probing for small buckets;
loads if the number of handling of
Efficiency Performanc high loads overflow
second hash collisions keys but
e decreases but still handling can
function is and the memory-
as table fills. slows as the add overhead.
well-chosen. length of intensive.
table fills.
linked lists.

Additional
Uses fixed Fixed buckets; High memory
Same as Same as memory for
Memory memory; no extra memory usage due to
linear linear linked lists
Usage external needed for multiple hash
probing. probing. or dynamic
structures. overflow. tables.
arrays.

Must remain Must remain

Must remain Can exceed 1
< 1 for < 1 for Can exceed 1,
< 1 for Can exceed due to
Load Factor optimal optimal but limited by
optimal 1. dynamic
performanc performanc bucket size.
performance. tables.
e. e.

Search/Insert O(1) for low O(1) for low O(1) for low O(1) O(1) for small
O(1) average;
Complexity load; O(n) as load; O(n) as load; O(n) if average; loads; O(n)
depends on
O(n) worst- for secondary
 Separate
Linear Quadratic Double
Aspect Chaining Bucketing Hash Tables
Probing Probing Hashing
(Rehashing)

load load rehashing case for long overflow table

increases. increases. fails. chains. handling. overflow.

Reduces Handles
Simple to Reduces
clustering; collisions Handles Efficient for
implement; clustering
efficient with dynamically; collisions with independent
Advantages requires no compared to
well-chosen supports compact key
extra linear
hash high load storage. management.
memory. probing.
functions. factors.

Prone to Still prone to Memory Requires

Needs a good
primary secondary overhead careful bucket
second hash High memory
clustering; clustering; for linked sizing; overflow
Disadvantage function; usage and
performanc requires lists; poor handling
s higher complex
e degrades more cache complicates
computation management.
with high computation performanc implementatio
al overhead.
load. . e. n.

Complex
Similar to
Large Highly applications
Small linear Small datasets
datasets dynamic where high
Best Use datasets probing, but with
requiring datasets or independenc
Case with low better for predictable
minimal when load e between
load factor. larger load.
clustering. factor > 1. keys is
datasets.
required.