Two-Way Python Dictionary: Building a Bidirectional Map with Equal Efficiency

Last update on April 10 2025 12:54:31 (UTC/GMT +8 hours)

87. Bidirectional Dictionary

Write a Python program to implement a bidirectional dictionary (BiDict) class that maintains one-to-one mappings and allows lookup in both directions with equal efficiency. Ensure that when a key-value pair is added, any existing entries with the same key or value are removed.

Solution:

Python Code:

# Define a class for a bidirectional dictionary (BiDict) that supports one-to-one mappings.
class BiDict:
    """
    A bidirectional dictionary that maintains one-to-one mappings
    and allows lookup in both directions with equal efficiency.
    """
    # Initialize the BiDict with two dictionaries: forward (key -> value) and backward (value -> key).
    def __init__(self):
        self.forward = {}  # Stores the mapping from keys to values.
        self.backward = {}  # Stores the mapping from values to keys.
    
    # Define the behavior for setting a key-value pair using the `[]` operator.
    def __setitem__(self, key, value):
        """Set a key-value pair, removing any existing entries with the same key or value."""
        # If the key already exists, remove its current mapping from both forward and backward dictionaries.
        if key in self.forward:
            old_value = self.forward[key]
            del self.backward[old_value]  # Remove the old value from the backward mapping.
            del self.forward[key]  # Remove the old key from the forward mapping.
        
        # If the value already exists, remove its current mapping from both forward and backward dictionaries.
        if value in self.backward:
            old_key = self.backward[value]
            del self.forward[old_key]  # Remove the old key from the forward mapping.
            del self.backward[value]  # Remove the old value from the backward mapping.
        
        # Add the new key-value pair to both forward and backward dictionaries.
        self.forward[key] = value
        self.backward[value] = key
    
    # Define the behavior for getting the value associated with a key using the `[]` operator.
    def __getitem__(self, key):
        """Get the value for a key."""
        return self.forward[key]  # Retrieve the value from the forward dictionary.
    
    # Define a method to get the key associated with a value.
    def get_key(self, value):
        """Get the key for a value."""
        return self.backward[value]  # Retrieve the key from the backward dictionary.
    
    # Define the behavior for deleting a key-value pair using the `del` operator.
    def __delitem__(self, key):
        """Remove a key-value pair by key."""
        value = self.forward[key]  # Get the value associated with the key.
        del self.forward[key]  # Remove the key from the forward dictionary.
        del self.backward[value]  # Remove the value from the backward dictionary.
    
    # Define the behavior for checking if a key exists in the BiDict.
    def __contains__(self, key):
        """Check if a key exists."""
        return key in self.forward  # Check if the key is in the forward dictionary.
    
    # Define the behavior for getting the number of key-value pairs in the BiDict.
    def __len__(self):
        """Get the number of pairs."""
        return len(self.forward)  # Return the length of the forward dictionary.
    
    # Define the string representation of the BiDict for debugging or printing.
    def __repr__(self):
        """String representation."""
        return f"BiDict({self.forward})"  # Represent the BiDict using its forward dictionary.

# Example usage of BiDict

# Create an instance of BiDict.
bidict = BiDict()

# Set key-value pairs in the bidirectional dictionary.
bidict['one'] = 1
bidict['two'] = 2
bidict['three'] = 3

# Forward lookup: Retrieve the value associated with the key 'one'.
print(bidict['one'])  # Output: 1

# Backward lookup: Retrieve the key associated with the value 2.
print(bidict.get_key(2))  # Output: 'two'

# Test the one-to-one constraint by assigning a new key to an existing value.
# This should remove the previous mapping ('one': 1) because the value 1 is reused.
bidict['four'] = 1

# Check if the key 'one' still exists in the BiDict after the reassignment.
print('one' in bidict)  # Output: False

# Perform a backward lookup to confirm the new mapping for the value 1.
print(bidict.get_key(1))  # Output: 'four'

Output:

1
two
False
Four

Explanation of Each Line:

Class Definition : Defines a BiDict class to implement a bidirectional dictionary with one-to-one mappings.
Docstring : Provides a description of the class and its functionality.
Initialization : Initializes the BiDict with two dictionaries: forward for key-to-value mappings and backward for value-to-key mappings.
Set Item Behavior : Implements the __setitem__ method to set key-value pairs while ensuring one-to-one constraints by removing conflicting mappings.
Remove Existing Key Mapping : Deletes the old value from the backward dictionary and the old key from the forward dictionary if the key already exists.
Remove Existing Value Mapping : Deletes the old key from the forward dictionary and the old value from the backward dictionary if the value already exists.
Add New Mapping : Adds the new key-value pair to both forward and backward dictionaries.
Get Item Behavior : Implements the __getitem__ method to retrieve the value associated with a key from the forward dictionary.
Backward Lookup : Implements the get_key method to retrieve the key associated with a value from the backward dictionary.
Delete Item Behavior : Implements the __delitem__ method to delete a key-value pair by removing it from both forward and backward dictionaries.
Key Existence Check : Implements the __contains__ method to check if a key exists in the forward dictionary.
Length Calculation : Implements the __len__ method to return the number of key-value pairs in the forward dictionary.
String Representation : Implements the __repr__ method to provide a string representation of the BiDict using its forward dictionary.
Example Usage : Demonstrates how to use the BiDict class with example data.
Set Key-Value Pairs : Adds key-value pairs to the BiDict.
Forward Lookup : Retrieves the value associated with a key using the [] operator.
Backward Lookup : Retrieves the key associated with a value using the get_key method.
Test One-to-One Constraint : Assigns a new key to an existing value to test the one-to-one constraint.
Check Key Existence : Verifies if a key still exists after reassigning its value.
Confirm New Mapping : Performs a backward lookup to confirm the updated mapping for the reassigned value.

Explanation - Bidirectional Dictionary

Concept: Implement a dictionary that maintains one-to-one mappings and allows lookups in both directions.
Challenge: Maintain the one-to-one constraint while providing efficient bidirectional access.
Key Skills:

Data structure design
Constraint enforcement
Dual-direction lookup implementation

Applications:

Mapping between IDs and names
Translation between different coding systems
Maintaining reversible transformations
Two-way lookups in caching systems

Benefits:

Equal efficiency for forward and backward lookups
Automatic enforcement of one-to-one relationships
Simplified code for bidirectional mapping needs

For more Practice: Solve these Related Problems:

Write a Python program to implement a bidirectional dictionary that allows many-to-many mappings.
Write a Python function to track reverse lookups in a bidirectional dictionary and prevent duplicate key-value pairs.
Write a Python class that extends a bidirectional dictionary to support case-insensitive lookups.
Write a Python program to store bidirectional mappings while supporting fast bulk updates.

Python Code Editor:

Previous: Dictionary Merging with Custom Conflict Resolution.
Next: Dictionary-based LRU Cache.