Data Structures and Algorithms: Open Addressing

Welcome to our deep dive into Open Addressing, a collision resolution strategy used in Hash Tables! 🎯 This lesson is perfect for both beginners and intermediates. Let's get started!

Understanding Open Addressing

Open Addressing is a method used when the hash function generates a collision (two keys have the same hash value). It allows us to store the keys at different positions in the array (Hash Table).

There are three main types of Open Addressing: Linear Probing, Quadratic Probing, and Double Hashing.

Linear Probing

💡 Pro Tip: Linear Probing is the simplest form of Open Addressing.

In Linear Probing, when a collision occurs, we move to the next empty index. If that index is occupied, we keep moving indexes until we find an empty one.

Here's a simple example:

python

def linearProbing(arr, key, size):
    hash = key % size
    while arr[hash] is not None:
        hash = (hash + 1) % size
    arr[hash] = key

In this example, arr is our Hash Table, key is the value we're trying to insert, and size is the size of our Hash Table.

Quick Quiz

Question 1 of 1

What is the key difference between a normal array and a Hash Table using Linear Probing?

Quadratic Probing

💡 Pro Tip: Quadratic Probing helps to reduce clustering.

Quadratic Probing works similarly to Linear Probing, but instead of moving to the next index, we move to an index that is i^2, i^2 + i, or i^2 + 1 steps away. This helps to reduce clustering (keys bunching up in the same area).

Here's a simple example:

python

def quadraticProbing(arr, key, size):
    hash = key % size
    index = hash
    i = 1
    while arr[index] is not None:
        index = (hash + i * i) % size
        i += 1
    arr[index] = key

In this example, arr is our Hash Table, key is the value we're trying to insert, and size is the size of our Hash Table.

Quick Quiz

Question 1 of 1

What is clustering in the context of Quadratic Probing?

Double Hashing

💡 Pro Tip: Double Hashing helps to avoid clustering and makes the search process faster.

Double Hashing uses two hash functions: one for inserting and one for searching. The insertion hash function is similar to Quadratic Probing, while the search hash function is designed to search efficiently.

Here's a simple example:

python

def doubleHashing(arr, key, size, a, b):
    insertHash = key % size
    searchHash = key % size
    index = insertHash
    while arr[index] is not None:
        index = (index + a * (key % b)) % size
    arr[index] = key

    def search(key):
        index = key % size
        while arr[index] is not None and arr[index] != key:
            index = (index + a * (key % b)) % size
        return arr[index] if arr[index] else None

In this example, arr is our Hash Table, key is the value we're trying to insert or search, size is the size of our Hash Table, a and b are constants used in the hash functions.

Quick Quiz

Question 1 of 1

What are the two main functions in Double Hashing?

Choosing the Right Probing Technique

📝 Note: The choice of probing technique depends on the specific requirements of your project.

Each probing technique has its advantages and disadvantages. Linear Probing is simple but can lead to clustering. Quadratic Probing helps to reduce clustering but can lead to long search times. Double Hashing helps to avoid clustering and makes the search process faster.

Choose the technique that best fits your project's needs!

Happy coding! 💡🚀