Chaining (Separate Chaining) 🎯

Welcome to our deep dive into the fascinating world of Chaining (Separate Chaining)! In this lesson, we'll explore this essential data structure, understand its real-world applications, and dive into some practical examples. Let's get started! 📝

What is Chaining (Separate Chaining)? 💡

Chaining (Separate Chaining) is a technique used in hash tables to handle collisions (when multiple keys hash to the same index). Instead of rehashing or linear probing, we create an array of linked lists (or arrays of hash tables). Each element in the array is a link to a linked list, and each node in the linked list contains a key-value pair. This approach allows us to handle an arbitrary number of collisions without knowing the maximum number of collisions beforehand.

Key Components 📝

Hash Table: A data structure used to implement the Chaining technique, consisting of an array of linked lists.
Hashing Function: A function that maps keys to indices in the hash table.
Linked List: A linear data structure where each node contains a key-value pair and a reference to the next node.
Collision: When multiple keys hash to the same index in the hash table.

Real-world Applications 📝

Efficient Lookup: Chaining (Separate Chaining) offers fast lookup times due to constant average and worst-case complexity for common operations like insertion and retrieval.
Handling Large Data Sets: Chaining can effectively handle large data sets with an arbitrary number of collisions, making it suitable for applications like databases, dictionaries, and sets.

Implementing Chaining (Separate Chaining) 💡

Python Example 📝

python

class HashTable:
    def __init__(self, size=10):
        self.table = [None]*size

    def hash_function(self, key):
        # Simple hash function - could be improved
        total = 0
        for char in key:
            total += ord(char)
        return total % len(self.table)

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            self.table[index].append((key, value))

    def get(self, key):
        index = self.hash_function(key)
        if self.table[index] is not None:
            for pair in self.table[index]:
                if pair[0] == key:
                    return pair[1]
        return None

# Example usage
ht = HashTable()
ht.insert('apple', 1)
ht.insert('banana', 2)
ht.insert('grape', 3)
print(ht.get('apple'))  # Output: 1

JavaScript Example 📝

javascript

class HashTable {
  constructor(size = 10) {
    this.table = Array(size).fill(null);
  }

  hashFunction(key) {
    // Simple hash function - could be improved
    let total = 0;
    for (let char of key) {
      total += char.charCodeAt(0);
    }
    return total % this.table.length;
  }

  insert(key, value) {
    const index = this.hashFunction(key);
    if (this.table[index] === null) {
      this.table[index] = [[key, value]];
    } else {
      this.table[index].push([key, value]);
    }
  }

  get(key) {
    const index = this.hashFunction(key);
    if (this.table[index] !== null) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    return null;
  }
}

// Example usage
const ht = new HashTable();
ht.insert('apple', 1);
ht.insert('banana', 2);
ht.insert('grape', 3);
console.log(ht.get('apple'));  // Output: 1

Quiz 💡

Conclusion ✅

Chaining (Separate Chaining) is a powerful data structure that helps us handle collisions efficiently in hash tables. By understanding its components and implementation, we can build fast and scalable data structures for real-world applications. Happy coding! 🚀