DSA Hash Maps in Python
A hash map is a structure that stores each value under a key for direct lookup. Python's dict is a hash map.
Store and look up
A dict writes a value under each key. A lookup reads the value from its key.
scores = {"Ana": 7, "Ben": 9, "Cid": 8}
print(scores["Ben"])
print("Ana" in scores)Add and update
Writing an existing key replaces its value. Writing a new key adds an entry.
prices = {"pen": 2, "book": 5}
prices["book"] = 6
prices["ruler"] = 3
for key in sorted(prices):
print(key, prices[key])A missing key
The get method returns a default for a missing key. No error is raised.
stock = {"pens": 12, "books": 4}
print(stock.get("pens", 0))
print(stock.get("rulers", 0))Example
text = "the market opened early and the market square filled with traders and the square echoed with voices"
freq = {}
for word in text.split():
freq[word] = freq.get(word, 0) + 1
for word in sorted(freq):
print(word, freq[word])
print("distinct words:", len(freq))
print("total words:", sum(freq.values()))Key points
- A dict stores each value under a key for direct lookup.
- A hash is a number computed from a key.
- A bucket is one storage slot chosen by the hash.
- A lookup goes to one bucket instead of scanning every key.
- Keys must be unchangeable values such as strings or numbers.
- A dict keeps its keys in the order they were inserted.
In this example, the loop splits the text into single words. Each word raises its own count in the map. The print loop sorts the keys for a stable order. The table shows every word beside its count. The last two lines print the distinct and total counts.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Why does a dict lookup stay fast as the map grows?