B.Tech • Chapter 4

Hashing: Tuples, Sets, & Dictionaries

B.Tech level module on Hashing.

6 note blocks4 exam topics

🎯 Exam Focus Areas

Evaluate time complexity of related algorithms.Understand memory management and background architecture.Analyze code snippets for bugs or inefficiencies.Explain theoretical concepts with real-world technical examples.

Dictionaries and Sets are implemented using Hash Tables. They provide O(1) average time complexity for lookups, insertions, and deletions, making them arguably the most important data structures in Python.

Advanced Engineering Concepts

A hash table uses a hash function to compute an index into an array of buckets. In Python, dictionaries are ordered (as of Python 3.7) by keeping a separate dense array for insertion order and a sparse array for the hash table. Hash collisions are resolved using open addressing with quadratic probing. Tuples are immutable and therefore hashable, meaning they can be used as dictionary keys, whereas lists cannot.

1Understand the Big O time and space complexities involved.
2Ensure memory leaks and race conditions are mitigated.
3Adhere to PEP 8 standards for clean, readable code.
4Utilize unit testing to verify algorithmic correctness.

Code Implementation

# Dictionary implementation and Hashing
my_dict = {"id": 101, "name": "Engineer"}

# Tuples as keys
route_distances = {
    ("Delhi", "Mumbai"): 1400,
    ("Bangalore", "Chennai"): 350
}

print(hash(("Delhi", "Mumbai")))
# print(hash(["Delhi", "Mumbai"])) # This will raise TypeError: unhashable type: 'list'

📝 Quick Revision Points

1Review the CPython implementation details.
2Practice the code snippets until syntax is committed to memory.
3Test edge cases and exception handling.
4Understand trade-offs between different data structures.

← PreviousDeep Dive: Strings, Lists, & Arrays Next →Functions, Generators, & Decorators

Loading notes...

# Dictionary implementation and Hashing my_dict = {"id": 101, "name": "Engineer"} # Tuples as keys route_distances = { ("Delhi", "Mumbai"): 1400, ("Bangalore", "Chennai"): 350 } print(hash(("Delhi", "Mumbai"))) # print(hash(["Delhi", "Mumbai"])) # This will raise TypeError: unhashable type: 'list'