Course contentsShow
← Computer Science
Lesson 2582 of 2,87257. Concurrency FundamentalsFree lesson

Concurrent Hash Map: Basics

Design considerations for thread-safe hash tables including bucket-level locking strategies.

Concurrent Hash Map: Basics

What you'll learn: How thread-safe hash tables use bucket-level locking to allow multiple threads safe, simultaneous access while maintaining good performance.

The Challenge

A regular hash map isn't thread-safe. If multiple threads read and write simultaneously, you'll get race conditions—corrupted data, lost updates, or worse. The naive solution is wrapping the entire map in a single lock, but that kills concurrency: only one thread can use the map at a time, creating a bottleneck.

Bucket-Level Locking: Divide and Conquer

Think of a hash map like a parking garage with multiple floors (buckets). Instead of one guard controlling the entire garage, put a guard on each floor. Now different cars can park on different floors simultaneously—only threads accessing the same bucket need to wait for each other.

How it works:

  • The hash map divides entries across many buckets (often using the hash code modulo bucket count)
  • Each bucket has its own lock
  • Threads modifying different buckets proceed in parallel
  • Only threads colliding on the same bucket synchronize with that bucket's lock

Design Considerations

Lock granularity: More buckets = more parallelism but more memory overhead for locks. Too few buckets = more contention.

Resizing complexity: When the map grows, you must coordinate rehashing without corrupting ongoing operations—often requiring careful lock acquisition ordering or a global lock momentarily.

Read optimization: Some designs use read-write locks per bucket, allowing multiple concurrent readers when no writes occur.

Load factor: Keeping buckets sparsely populated reduces collisions, improving both speed and concurrency.

Key Takeaway: Bucket-level locking in concurrent hash maps achieves thread safety while enabling parallelism by independently locking only the specific buckets being modified, not the entire structure.