HashMap Structure: Arrays of Buckets
You'll learn how HashMap uses an array of buckets to store and quickly retrieve key-value pairs.
The Core Idea
A HashMap isn't just a simple list of entries. Internally, it maintains an array where each position is called a bucket. When you put a key-value pair into the map, Java computes the key's hashCode(), then uses that hash to determine which bucket should hold the entry. This structure allows HashMap to jump directly to the right bucket instead of searching through all entries sequentially.
Visualizing Buckets
Think of a HashMap like a filing cabinet with numbered drawers (buckets). Each drawer can hold multiple documents (entries). When you need to file a document, you calculate which drawer number it belongs to based on its label (hash code), then place it in that drawer. Later, when retrieving it, you calculate the same drawer number and look only in that drawer—not all of them.
How the Array Works
The underlying array typically starts with a capacity like 16 buckets. Each bucket can be empty, hold one entry, or (in case of hash collisions) hold multiple entries that happened to hash to the same bucket index. The calculation looks something like:
bucket_index = hashCode(key) % array_length
This modulo operation maps the hash code to a valid array index. Since the array has fixed size at any moment, multiple different keys might map to the same bucket—hence the need for collision handling within buckets.
Why This Matters
This bucket-based structure is what gives HashMap its O(1) average lookup time. Instead of checking all entries, you check only the bucket corresponding to the hash code.
Key Takeaway: HashMap organizes entries into an array of buckets, using hash codes to determine bucket placement, enabling fast direct access instead of linear searching.