HashMap vs HashSet (Conceptual)

Both HashMap and HashSet are built on top of hash tables. Conceptually:

  • A hash map stores key → value mappings.
  • A hash set stores only keys (membership).

In many implementations, a hash set is literally a thin wrapper around a hash map where every key maps to the same dummy value.

HashMap: Key → Value

Hash maps are used when you need to:

  • Associate extra information with a key:
    • Frequency counts.
    • Metadata such as indices, timestamps, or aggregated stats.
    • Pointers to other objects.
  • Support operations like:
    • put(key, value)
    • get(key)
    • containsKey(key)
    • remove(key)

Examples:

  • Word frequency in a document.
  • Caching computation results keyed by input.
  • Storing user profiles keyed by user ID.

HashSet: Membership Only

Hash sets are used when you only care about:

  • Whether an element exists or not.
  • Possibly iterating over unique elements.

Operations:

  • add(x)
  • contains(x)
  • remove(x)

Internally, a set can be modeled as a map of:

  • key → true (or a fixed dummy object).

Examples:

  • Checking if an element has appeared before (e.g. detecting duplicates).
  • Tracking visited nodes in graph traversal.
  • Storing unique tags, IDs, or strings.

When to Use Which

Use a HashMap when:

  • You care about associating data with keys.
  • You need to retrieve values based on keys.

Use a HashSet when:

  • You only need to know if something is in the set.
  • You don’t need to store any extra data per element.

In interviews, you can often start with:

  • “We’ll use a hash set to track visited items.”
  • “We’ll use a hash map to count frequencies / map keys to indices.”

The underlying performance characteristics are very similar; the difference is mostly about what data you conceptually store on top of the hash table.

Example: Map vs Set in Code (Java)

Java
// Using a HashSet to check membership
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
    if (seen.contains(x)) {
        // duplicate found
    }
    seen.add(x);
}

// Using a HashMap to count frequencies
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) {
    count.put(x, count.getOrDefault(x, 0) + 1);
}

These snippets highlight the conceptual difference: set for membership, map for key → value.