How is set() implemented in Python?

Implementation of set() in Python

In Python, the set data structure is an unordered collection of unique elements. It is implemented using a hash table, which allows for average-case constant time complexity (O(1)) for operations such as insertions, deletions, and membership tests. Below is an in-depth explanation of how set is implemented in Python.

Key Characteristics

• Unordered: Elements in a set do not maintain any specific order.
• Unique Elements: Sets automatically ensure that there are no duplicate elements.
• Mutable: Elements can be added or removed.
• Hash Table: Internally, sets use a hash table to store elements, which allows for efficient lookups.

Internal Implementation

The core of the set implementation in Python revolves around the use of hash tables. Here’s a breakdown of how sets are implemented:

1. Hash Table

A hash table is used to store the elements of the set. Each element is hashed to a specific index in the table, which allows for O(1) average time complexity for lookups, insertions, and deletions.

2. Hash Function

Each element in the set is passed through a hash function, which computes a hash value. This hash value is used to determine the index in the hash table where the element will be stored.

3. Collision Handling

Collisions (when two different elements hash to the same index) are handled using open addressing with quadratic probing. This means that if a collision occurs, the algorithm looks for the next available slot using a quadratic function of the number of collisions.

4. Dynamic Resizing

The hash table dynamically resizes to maintain efficient operations. When the number of elements exceeds a certain load factor, the table is resized (usually doubled in size), and all existing elements are rehashed and inserted into the new table.

Example Implementation

Here is a simplified example of how a set might be implemented using a hash table in Python:

class MySet:
    def __init__(self):
        self.capacity = 8  # Initial capacity of the hash table
        self.size = 0
        self.table = [None] * self.capacity

    def _hash(self, key):
        return hash(key) % self.capacity

    def _rehash(self):
        old_table = self.table
        self.capacity *= 2
        self.table = [None] * self.capacity
        self.size = 0
        for item in old_table:
            if item is not None:
                self.add(item)

    def add(self, key):
        if self.size >= self.capacity // 2:
            self._rehash()

        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index] == key:
                return  # Key already exists, no need to add
            index = (index + 1) % self.capacity  # Quadratic probing

        self.table[index] = key
        self.size += 1

    def remove(self, key):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index] == key:
                self.table[index] = None
                self.size -= 1
                return
            index = (index + 1) % self.capacity  # Quadratic probing

        raise KeyError(f"Key not found: {key}")

    def contains(self, key):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index] == key:
                return True
            index = (index + 1) % self.capacity  # Quadratic probing

        return False

    def __str__(self):
        return "{" + ", ".join(str(item) for item in self.table if item is not None) + "}"

# Example usage
my_set = MySet()
my_set.add(1)
my_set.add(2)
my_set.add(3)
print(my_set)  # Output: {1, 2, 3}
print(my_set.contains(2))  # Output: True
my_set.remove(2)
print(my_set)  # Output: {1, 3}
print(my_set.contains(2))  # Output: False

Summary

• Hash Table: The underlying data structure for Python sets is a hash table, which ensures efficient O(1) average time complexity for operations.
• Unique Elements: Sets automatically handle duplicates, ensuring all elements are unique.
• Collision Handling: Uses open addressing with quadratic probing to resolve hash collisions.
• Dynamic Resizing: The hash table dynamically resizes to maintain efficient performance as the number of elements grows.

Understanding how sets are implemented can help you appreciate their performance characteristics and use them effectively in your Python programs. For more in-depth knowledge and practical examples on Python data structures and other programming concepts, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.