DEV Community: Chimwemwe Liwonde

What If a Hash Table Could Check Just Two Positions? Understanding Cuckoo Hashing 🐦

Chimwemwe Liwonde — Mon, 09 Nov 2026 04:22:34 +0000

Imagine looking for a name in a directory containing one million entries, but instead of searching through thousands of records, you only need to check two locations.

Sounds interesting, right?

This is one of the fascinating ideas behind a data structure called Cuckoo Hashing.

While studying Algorithms and Complexity, I came across this concept, and I thought it was worth sharing with fellow developers.

Let's break it down, from the problem it solves to how it works, without making the mathematics unnecessarily complicated.

1. First, let's understand the problem

Imagine you're building a university system that stores thousands of student IDs.

Your system needs to perform three operations:

Insert: Add a student ID.
Lookup: Check whether a student ID exists.
Delete: Remove a student ID.

One way of storing these IDs would be to use a linked list.

The problem?

If we have 100,000 student IDs and the one we're searching for happens to be at the end, we might need to examine all 100,000 entries.

That's a worst-case time complexity of O(n).

Can we do better?

Absolutely. Enter hashing.

2. Hashing: Giving every item an address

Instead of searching through every item, what if we could calculate where an item should be stored?

That's what a hash function does.

A hash function takes an item, called a key, and maps it to a position in a table.

For example, suppose we have a table with 10 positions, numbered 0 to 9.

We define:

h(x) = x mod 10

The mod operator returns the remainder after division.

Consider these student IDs:

Student ID	Calculation	Position
123	123 mod 10	3
245	245 mod 10	5
318	318 mod 10	8
133	133 mod 10	3

Notice something?

Both 123 and 133 map to position 3.

This is called a hash collision.

Two different keys want to occupy the same location.

So how do we solve this?

3. Traditional solution: Hashing with chaining

A common solution is chaining.

Instead of storing only one item at a table position, we attach a linked list to that position.

For example:

Position 3 → 123 → 133 → 253

All three IDs have the same hash value, so they share a bucket.

This works, but it introduces a problem.

When searching for an item, we might need to traverse the linked list.

Under suitable assumptions, hashing with chaining achieves O(1) expected lookup time.

However, in the worst case, if many items collide, a search can still take O(n) time.

Now imagine a different approach.

What if we eliminated those linked lists and allowed every item only two possible positions?

That's where things become interesting.

4. Meet Cuckoo Hashing 🐦

Cuckoo hashing was introduced by researchers Rasmus Pagh and Flemming Friche Rodler in 2001.

The name comes from the behaviour of cuckoo birds, which are known for laying their eggs in other birds' nests. In some species, the cuckoo chick pushes other eggs out.

Cuckoo hashing uses a similar idea: when a new item needs an occupied position, it can displace the item already there.

But the displaced item isn't discarded.

Instead, it moves to its alternative position.

Here's the key difference.

Traditional hashing normally assigns each key one hash location.

Cuckoo hashing gives each key two possible locations, calculated using two hash functions:

h1(x) — First possible position
h2(x) — Second possible position

Each position can hold at most one item.

This gives us a powerful property:

To find an item, we only need to check two positions.

Regardless of whether our table contains 100 items or one million, the number of candidate positions checked remains at most two.

That's the foundation of worst-case O(1) lookup time, assuming hash calculations and key comparisons take constant time.

5. Let's see how cuckoo hashing works

Suppose we have these items and their two possible positions:

Item	First position	Second position
A	1	3
B	3	5
X	1	7

Initially, our table looks like this:

Position	Item
1	A
3	B
5	Empty
7	Empty

Now, let's insert a new item: X.

Its first choice is position 1.

But position 1 already contains A.

What happens next?

Step 1: X displaces A

X moves into position 1, pushing A out.

Position 1 now contains X.

But where should A go?

Step 2: A moves to its alternative position

A has two possible positions: 1 and 3.

Since X now occupies position 1, A attempts to move to position 3.

Unfortunately, position 3 already contains B!

So A displaces B.

Step 3: B searches for its alternative position

B can occupy position 3 or position 5.

Since A now occupies position 3, B moves to position 5.

Luckily, position 5 is empty.

The insertion succeeds!

Our table now looks like this:

Position	Item
1	X
3	A
5	B
7	Empty

Notice what happened.

We inserted X without creating any linked lists. Every position still contains at most one item.

And each item remains in one of its two valid locations.

One small detail: position 7 was also available for X. The particular insertion algorithm we are illustrating starts at the first hash location and performs displacement. An optimised implementation could check both positions first and avoid unnecessary displacement.

6. What happens when displacement never ends?

You might have spotted a potential problem.

What if every displaced item tries to move somewhere that is already occupied?

Suppose three items can only occupy the same two positions.

There is simply not enough space for all three.

The algorithm could repeatedly displace items without finding an empty position.

This leads us to an important concept: cycles.

Cuckoo hashing can be analysed using a graph where:

Every table position is a vertex.
Every item is an edge connecting its two possible positions.

Displacement follows connections in this graph.

Cycles can create insertion difficulties. More precisely, a cycle does not automatically mean insertion must fail, but certain graph structures make it impossible to place every item.

The solution: Rehashing

If the insertion algorithm exceeds its allowed number of displacement attempts, it can rebuild the table using newly selected hash functions.

This process is called rehashing.

The new hash functions give items different candidate positions, potentially resolving the problem.

Rehashing is expensive because multiple items may need to be repositioned.

Fortunately, when the table has sufficient spare capacity and the hash functions satisfy suitable randomness assumptions, rehashing happens infrequently enough to preserve efficient expected performance.

7. The mathematics: How fast is cuckoo hashing?

This is arguably the most interesting part.

Let's examine its performance.

Operation	Time complexity
Lookup	O(1) worst-case
Delete	O(1) worst-case
Insert	O(1) expected, amortised
Space	O(n)

Let's understand these claims.

Lookup: O(1) worst-case

We compute two hash values and inspect at most two locations.

The number of checks doesn't grow with the number of stored items.

Deletion: O(1) worst-case

We check the same two positions. If the item exists, we remove it.

No linked-list traversal is required.

Insertion: O(1) expected, amortised

Insertion is more complicated because displacement may involve several items.

Occasionally, rehashing might require O(n) work.

However, under the theoretical model used in the analysis, the expected total insertion cost over a sequence of operations is proportional to the number of operations.

That gives us constant expected amortised insertion time.

The distinction matters:

Expected O(1) does not mean every insertion completes in O(1).

The guarantee concerns the expected cost averaged over the random choices and amortised across operations.

There is another important condition: spare space.

The basic theoretical construction can use approximately 2(1 + ε)n table slots for at most n items, where ε is any fixed positive constant.

In other words, efficient cuckoo hashing doesn't come for free. It trades extra storage capacity for predictable lookup performance.

8. A clever improvement: The stash

There is one more interesting improvement I learned about.

What if, instead of rebuilding the entire table every time an insertion encounters a problematic structure, we provide a small extra storage area?

This is called a stash.

Items that cannot be placed in their normal candidate positions can temporarily be stored there.

Researchers Kirsch, Mitzenmacher and Wieder showed that, under fully random hash-function assumptions, a stash of size s can reduce the failure probability from:

O(1/n)

to:

O(1/n^(s+1))

That's a powerful improvement from adding only a small, constant-sized amount of auxiliary storage.

It does mean a lookup must also check the stash, but if its capacity is constant, lookup still takes O(1) worst-case time.

9. When is cuckoo hashing useful?

Cuckoo hashing is especially interesting in systems where predictable lookup performance matters.

Potential applications include:

High-performance networking and routing tables
Hash-based indexes
In-memory dictionaries
Systems with latency-sensitive membership checks

Of course, it isn't automatically the best choice for every application.

Insertions can be more complicated than in ordinary hash tables, and the structure requires careful hash-function design and capacity management.

The best data structure always depends on the workload and the performance guarantees we need.

10. What I learned

The biggest lesson for me wasn't simply that cuckoo hashing can achieve constant-time lookups.

It was understanding how changing the rules of where data can be stored changes the guarantees we can provide.

Traditional chaining says:

"If two items collide, keep them together in a bucket."

Cuckoo hashing says:

"Give each item an alternative location. If necessary, move the existing occupant."

That small change leads to a completely different way of managing collisions.

It also introduces a deeper lesson in algorithms: sometimes we deliberately accept unpredictable work in one operation to obtain stronger guarantees for another.

Cuckoo hashing is a beautiful example of the relationship between data structures, randomness, probability and algorithmic performance.

I'm currently exploring these concepts as part of my Algorithms and Complexity studies, and I've decided to share more of what I'm learning as I go.

Because one of the best ways to understand something deeply is to try teaching it to someone else.

Over to you 👇

If you were building a system where lookup speed was critical, would you choose cuckoo hashing over traditional hashing with chaining?

What trade-offs would influence your decision?

I'd love to hear your thoughts.

Further reading

Pagh, R., & Rodler, F. F. (2001). Cuckoo Hashing. European Symposium on Algorithms.
Mitzenmacher, M., & Upfal, E. Probability and Computing.
COMP53215 Algorithms and Complexity — Data Structures lecture notes, Tom Friedetzky.

Suggested DEV tags: #algorithms #datastructures #computerscience #beginners

Have you ever accidentally leaked an API key? 🙋‍♂️ It takes bots exactly 300 milliseconds to steal it and drain your bank account. I wrote a complete beginner's guide to surviving "The $5,000 Typo" so it never happens to you. Read it here! 👇

Chimwemwe Liwonde — Sun, 15 Mar 2026 15:31:45 +0000

The $5,000 Typo: How Beginners Are Handing Their API Keys to Hackers

Chimwemwe Liwonde ・ Mar 15

#devops #beginners #tutorial #security

Waking up to a $5,400 OpenAI bill because you pushed to GitHub is every developer's worst nightmare. 💀 Bots steal exposed keys in just 300 milliseconds. Here is my guide to securing your code and how to execute the "Oh Crap" protocol. 👇

Chimwemwe Liwonde — Sun, 15 Mar 2026 15:30:13 +0000

The $5,000 Typo: How Beginners Are Handing Their API Keys to Hackers

Chimwemwe Liwonde ・ Mar 15

#devops #beginners #tutorial #security

Did you just push your code to GitHub? 🚨 If you leaked an API key, hackers will steal it in 300 milliseconds. Before you get a surprise $5,000 bill, read these 4 unbreakable rules for API security (and why React apps are a death trap). 👇

Chimwemwe Liwonde — Sun, 15 Mar 2026 15:28:25 +0000

The $5,000 Typo: How Beginners Are Handing Their API Keys to Hackers

Chimwemwe Liwonde ・ Mar 15

#devops #beginners #tutorial #security

The $5,000 Typo: How Beginners Are Handing Their API Keys to Hackers

Chimwemwe Liwonde — Sun, 15 Mar 2026 11:48:16 +0000

You built your first AI app. You pushed the code to GitHub. While you sleep, a bot steals your API key and drains your bank account. As a developer, here is how I protect my code from what I call "The 300-Millisecond Trap."

As a developer, there is no better feeling than getting an API to finally work. But imagine this scenario:

It’s 2:00 AM. You just finished building your first AI project, a cool little resume builder using the OpenAI API. You are exhausted but proud. You type git add .
, git commit -m "first commit", and git push. You close your laptop and go to sleep.

You wake up the next morning to an email from OpenAI:
"Billing Alert: Your usage has exceeded $5,400.00."

Your heart drops. What happened? Nobody even knows your website exists yet.

Welcome to The 300-Millisecond Trap.

What Exactly Is an API Key? (And Why Do Hackers Want It?)

When I first started working with APIs, I used to see lines like this everywhere:
OPENAI_API_KEY="sk-proj-xxxxxxxxxxxxxxxx"

I quickly learned that an API key is basically a secret password for your application. When your app connects to OpenAI, Stripe, or AWS, the API key tells the service: "This request is coming from an authorized user, bill their credit card."

Like many developers, I host my code on GitHub. It’s great for building a portfolio. But here’s the catch I wish someone had told me on day one: If your repository is public, everything inside it is visible to the entire internet.

The 300-Millisecond Trap

When you are a beginner, tutorials tell you to get an API key and paste it into your code to make it work. What they forget to tell you is that GitHub is crawling with malicious bots.

Hackers don't sit at their computers manually reading your code. They run automated scripts that scan every single public GitHub commit globally.

The moment you push a file containing sk-proj-... (the standard OpenAI key format), the bot steals it.
Time elapsed: ~300 milliseconds.

Within seconds, that bot is using your credit card to run thousands of complex AI tasks, generate spam, or sell your API access on the dark web.

Even lazy hackers can just go to Google and type: site:github.com "OPENAI_API_KEY".

As a developer working here in Malawi, I know firsthand that a surprise $5,000 USD bill isn't just a mistake with exchange rates, it is an absolute financial catastrophe that could end a career before it starts.

The Beginner's Guide to API Survival

If you are building anything with APIs in 2026, you must follow these 4 unbreakable rules. I use these on every single project I build.

Rule 1: The .env File is Your Best Friend
Never, ever paste your API key directly into your app.js or index.html file.
Instead, create a file called .env in the root of your project.

# Inside your .env file
OPENAI_API_KEY="sk-proj-your-secret-key-here"

In your code, you access it like this (in Node.js):
const apiKey = process.env.OPENAI_API_KEY;

Rule 2: The Invisible Shield (.gitignore)

Rule 1 is useless if you push the .env file to GitHub! This is the #1 mistake beginners make.

Before you run git add ., you must create a file named .gitignore.
Inside that file, simply type:

.env

Now, Git will pretend the .env file doesn't exist. It will stay safe on your local computer, and hackers will never see it.

Rule 3: The "Frontend" Death Trap

When I first learned React, I thought my .envfiles were safe. I was wrong.

Never call the OpenAI API directly from your React, Vue, or Vanilla JS frontend. If your API key is in your frontend code, anyone can open Google Chrome, right-click, hit "Inspect Element," and steal your key from the "Network" tab. .env files will not protect you here if the code runs in the user's browser!

How I Fix This: I Always build a "Server-Side Proxy." My React frontend should send a request to my backend (Node.js/Python/PHP). My backend (which securely holds the hidden key) talks to OpenAI, and sends the result back to the frontend.

Rule 4: The Ultimate Safety Net (Hard Limits)
Even experienced developers leak keys accidentally. To prevent a typo from ruining your life, go to your OpenAI Billing Dashboard right now.

Set a Hard Limit of $10 or $20 a month. If a hacker steals your key, the API will simply shut off once it hits $20. You lose a little money, but you save your bank account.

The "Oh Crap" Protocol

What if you are reading this and realize you pushed your key to GitHub 5 minutes ago?
Do NOT just delete the key from the code and push again.
Git keeps a history of all your changes. The hacker can just look at your previous commit history and find it.

As a developer, here is what you must do immediately:

Log into platform.openai.com (or whichever service you leaked).
Go to API Keys.
Find the leaked key and click Revoke Key or Delete.

Once the key is revoked, it becomes a useless string of text. The hacker gets nothing. Generate a new key and start fresh.

Final Thought:
Security isn't just for senior engineers. It starts on day one. Treat your API keys like your bank PIN, set your billing limits, and let's keep building safely.

Have you ever accidentally leaked an API key? (Don't worry, we've all done it). Let me know your horror stories in the comments below! 👇

P.S. I am currently open for freelance development projects. If your team needs help building secure, scalable apps, let's connect!

[Boost]

Chimwemwe Liwonde — Sun, 22 Feb 2026 21:55:54 +0000

The Developer’s Roadmap to Revenue: 4 Software Business Models Explained (With Real Numbers)

Chimwemwe Liwonde ・ Feb 22

#ai #career #startup #discuss

The Developer’s Roadmap to Revenue: 4 Software Business Models Explained (With Real Numbers)

Chimwemwe Liwonde — Sun, 22 Feb 2026 12:04:37 +0000

Everyone wants to build the next Facebook, but that is the hardest path. This guide breaks down the 4 ways developers actually make money in 2026, ranked from "Start Here" to "Billionaire Status."

Let’s be honest: Knowing how to write code and knowing how to make money are two very different skills.

I see so many developers (myself included) get stuck in "Tutorial Hell" or building side projects that never make a dime. Usually, the problem isn't the code—it's the Business Model.

In 2026, with AI capable of writing boilerplate code, your value isn't just syntax; it's solving problems.

I’ve broken down the 4 main software business models. I’ve included real-world examples (so you know who to study) and realistic revenue estimates (so you know what to expect).

Here is your roadmap.

1. The Service Model (Trading Time for Money)

The Concept
This is the simplest model. You have a skill (coding), and a client has a problem. You fix the problem, they pay you. This includes freelancing, consulting, and agency work.

The "Famous" Example: Accenture or Infosys. These are massive companies, but they are essentially just armies of developers selling their time.
The "Solo" Example: A freelancer on Upwork charging $60/hour to fix React bugs.

The Numbers:

Revenue Potential: $50/hour to $200k/year (Solo).
Startup Cost: $0.

The Reality Check:
This is the best place to start because you get paid immediately. However, it is a trap if you stay too long. If you get sick or go on holiday, your income drops to $0. You are the engine; if the engine stops, the car stops.

2. The Productized Service (The "Smart" Service)

The Concept:
This is the secret weapon of 2026. You take a service, but you sell it like a product with a fixed price and fixed scope. No hourly billing. No scope creep.

The "Famous" Example: DesignJoy. A one-man design agency that makes $1M+ per year by selling "Unlimited Design" for a fixed monthly fee.
The "Dev" Example: WP Buffs. They don't just "fix websites"; they sell specific "WordPress Care Plans" for a monthly subscription.

The Numbers:

Revenue Potential: $5k - $50k Monthly Recurring Revenue (MRR).
Margins: High (70-80%).

The Reality Check:
This is my favorite model for solo developers. Because the scope is fixed (e.g., "I will optimize your SQL database"), you can automate 80% of the work with scripts or AI agents. You get the recurring revenue of a product without the headache of building a massive app.

3. The Ecosystem Model (The "Plugin" Play)

The Concept:
Don't build the platform; build on top of the platform. You create a tool that improves an existing giant (like Shopify, WordPress, Salesforce, or Chrome).

The "Famous" Example: Grammarly or Yoast SEO. Grammarly started as a simple browser extension before becoming a unicorn. Yoast built a plugin for WordPress that millions use.
The "Dev" Example: A developer building a "Stock Inventory Sync" app for the Shopify App Store.

The Numbers:

Revenue Potential: $1k - $100k/month.
Marketing Cost: Low (The platform brings you users).

The Reality Check:
This is "Leverage." You don't need to find customers; Shopify or Salesforce already has them. You just need to solve a specific problem they have. The risk? You are playing in someone else's backyard. If they change their rules, your business can die overnight.

4. The Product Model (SaaS / The Dream)

The Concept:
Software as a Service. You build a web application once, and thousands of people pay you a subscription to use it while you sleep.

The "Famous" Example: Netflix, Slack, or Zoom.
The "Solo" Example: Bannerbear (an API for generating images) or Carrd (a simple site builder).

The Numbers:

Revenue Potential: Unlimited (Millions/Billions).
Failure Rate: Extremely High (90%+).

The Reality Check:
This is the hardest path. In 2026, the market is flooded with "AI Wrappers." To win here, you can't just build a "To-Do List app." You need to solve a painful problem better than anyone else. It takes months to build and even longer to get your first 10 customers. But if it works, it creates generational wealth.

Which Path Should You Choose? (My Recommendation)

If you are reading this and wondering where to start, here is the "Staircase Strategy" I recommend to new developers:

Start with Model 1 (Service): Freelance to learn what makes businesses bleed money. Get paid to learn.
Move to Model 2 (Productized Service): Once you solve the same problem 5 times, package it. Stop charging hourly.
Invest in Model 4 (Product): Use the cash from your service to fund the development of your SaaS.

Final Thought:
You don't need to build the next Facebook to be successful. A "boring" Productized Service that helps local businesses manage their inventory can make you more money than a "cool" AI app that nobody pays for.

I’d love to hear from you: Which model fits your current skills best? Let's discuss in the comments. 👇