Swift has a powerful built-in Dictionary, but learning how it works behind the scenes helps you understand data better. This article explains how to build your own Dictionary using three methods:
- Chained Hash Map (uses linked lists)
- Double Hashed Map (uses open slots and two hash functions)
- Robin Hood Hash Map (makes lookup times more even)
- Chained Hash Map (Linked List Method)
What it does
Stores key-value pairs
Each bucket (array slot) can hold multiple items using a linked list
If two keys land in the same bucket, they go into a list
How it works
A hash function gives the index for the key
If that spot is empty, add the item
If it already has items, add to the list
If the number of items becomes too big (over 70%), the table grows bigger
Pros
Easy to understand and use
Good for adding and deleting items
Cons
- Can use more memory
- Slower if too many items end up in one bucket
Note
_In Java's HashMap, if a linked list in a bucket grows longer than 8 entries, it automatically converts that list into a balanced tree (Red-Black Tree) to improve lookup speed. You can add similar logic to your Swift implementation for better performance.
_
2. Double Hashed Map (Open Addressing with Two Hashes)
What it does
Avoids using lists
Instead, it uses a second hash to find the next free slot when a collision happens
How it works
First hash gives the starting spot
Second hash tells how far to move if it’s already full
Keeps checking slots until it finds an empty one
Resizes when the table gets too full
Pros
Uses less memory than chaining
Spreads out items better than just linear search
Cons
Harder to remove items
Slower when the table is almost full
3. Robin Hood Hash Map (Fair Probing)
What it does
Keeps all items as close to their ideal spot as possible
If a new item has been waiting longer than another one, it “steals” the spot
How it works
Each item tracks how far it has probed
If a new item has probed more than the existing item, they switch places
Keeps lookup times more even
Pros
Balanced and fair
Makes lookups faster even in crowded tables
Cons
More complex to write
Removing items is not covered here
Extra: Turning Long Lists into Trees
Just like Java's HashMap, we can improve ChainedHashMap by changing long linked lists into trees (like Red-Black Trees) when they grow too big (more than 8 items).
Why it's useful
Makes worst-case lookups faster (O(log n) instead of O(n))
Keeps performance smooth
Summary Table
Final Thoughts
Making your own Dictionary helps you understand how real ones like Swift's Dictionary work.
By building these three types, you learn about:
Handling collisions
Balancing speed and memory
Writing smarter data structures
Top comments (0)