Collision Resolution Techniques 🎯

Welcome to our deep dive into Collision Resolution Techniques! In this lesson, we'll explore various strategies to handle collisions in hash tables, a fundamental data structure used for efficient data storage and retrieval. Let's get started!

Why Collision Resolution is Important? 📝

Collision occurs when two different keys hash to the same index in a hash table. Collision resolution techniques help to manage these collisions and ensure the hash table remains efficient.

Hash Tables and Collisions 💡

A hash table is a data structure that uses a hash function to map keys to specific indices in an array. When two keys hash to the same index, we have a collision. Let's take a look at a simple example:

python

def hash_function(key, size):
    return hash(key) % size

data = {
    'apple': 1,
    'banana': 2,
    'orange': 3
}

hash_table_size = 5

for key, value in data.items():
    index = hash_function(key, hash_table_size)
    print(f"Key: {key}, Value: {value}, Index: {index}")

Output:

Key: apple, Value: 1, Index: 4
Key: banana, Value: 2, Index: 3
Key: orange, Value: 3, Index: 2

Here, we can see that the keys apple and orange have collided because they both hash to index 4.

Chaining (Open Addressing) 🎯

One common collision resolution technique is called Chaining, also known as Open Addressing. In this method, we use an array and link each index to a linked list of keys that have collided at that index.

Linear Probing 💡

Linear probing is a simple chaining technique where we iterate linearly through the array until we find an empty index to insert the colliding key.

python

def linear_probing(key, current_index, hash_table_size):
    index = current_index
    while hash_table[index] is not None:
        index += 1
        if index == hash_table_size:
            index = 0
    return index

Let's see how Linear Probing handles collisions:

python

hash_table = [None] * hash_table_size

data = {
    'apple': 1,
    'banana': 2,
    'orange': 3,
    'pear': 4
}

for key, value in data.items():
    index = hash_function(key, hash_table_size)
    if hash_table[index] is not None:
        index = linear_probing(key, index, hash_table_size)
    hash_table[index] = (key, value)

for key, value in hash_table:
    print(f"Key: {key}, Value: {value}")

Output:

Key: banana, Value: 2
Key: apple, Value: 1
Key: orange, Value: 3
Key: pear, Value: 4

Quadratic Probing 💡

Quadratic probing is another chaining technique that avoids collisions more effectively by probing for an empty index using a quadratic function.

python

def quadratic_probing(key, current_index, hash_table_size):
    a = 1
    index = current_index
    while hash_table[index] is not None:
        index = (index + a * a) % hash_table_size
        a = -a
    return index

Let's see how Quadratic Probing handles collisions:

python

hash_table = [None] * hash_table_size

data = {
    'apple': 1,
    'banana': 2,
    'orange': 3,
    'pear': 4
}

for key, value in data.items():
    index = hash_function(key, hash_table_size)
    if hash_table[index] is not None:
        index = quadratic_probing(key, index, hash_table_size)
    hash_table[index] = (key, value)

for key, value in hash_table:
    print(f"Key: {key}, Value: {value}")

Output:

Key: banana, Value: 2
Key: apple, Value: 1
Key: orange, Value: 3
Key: pear, Value: 4

Practice Time 🎯

Now it's your turn to apply what you've learned!

Conclusion 🎯

Chaining (Open Addressing) is a powerful collision resolution technique that allows us to efficiently manage collisions in hash tables. By understanding Linear Probing and Quadratic Probing, you can effectively handle collisions in various real-world projects.

Stay tuned for our next lesson on advanced hash table concepts! 🚀