DEV Community

Cover image for Making Your Own Dictionary in Swift
Binoy Vijayan
Binoy Vijayan

Posted on • Edited on

Making Your Own Dictionary in Swift

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)
  1. Chained Hash Map (Linked List Method)

ChainedHashMap.swift

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)

DoubleHashedMap.swift

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)

RobinHoodHashMap.swift

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

The complete source code is available here.

Top comments (0)