Java中HashMap & HashSet的size()方法实现原理与时间复杂度问询

Hey! Great question—let's dig into how size() works for HashMap and HashSet in Java, plus its performance characteristics.

Under the hood, HashMap keeps a transient int instance variable called size that tracks the number of key-value pairs currently stored.

Every time you modify the collection in a way that changes the entry count, this size variable gets updated immediately:

• When put() adds a brand new key-value pair (the key didn't exist before), size increments by 1.
• When put() replaces an existing value for an already present key, size stays the same (we're not adding a new entry).
• When remove() successfully deletes an entry, size decrements by 1.
• clear() resets size to 0 directly.

The size() method itself is super straightforward—it just returns this pre-maintained variable. Here's the core code:

public int size() {
    return size;
}

HashSet is essentially a wrapper around a HashMap! It stores all its elements as keys in the underlying HashMap, using a dummy constant Object (named PRESENT) as the value for every entry.

Unsurprisingly, HashSet's size() method simply delegates to the inner HashMap's size() method. The code looks like this:

public int size() {
    return map.size();
}

So its working mechanism is identical to HashMap's—no extra tricks here.

Since size() just returns a precomputed variable without any iteration, calculation, or traversal of the underlying data structure, it runs in O(1) constant time.

A quick side note: In multi-threaded environments without proper synchronization, the value returned by size() might be stale (other threads could be modifying the collection at the same time), but that's a concurrency edge case—not a reflection of the method's inherent time complexity.

内容的提问来源于stack exchange，提问作者leocrimson