How is a hash set usually implemented on top of a hash map engine, and what does an entry store?
answer
- one table, two public faces
- what would the value column hold?
- membership is a lookup that found something
- a single shared placeholder per entry
- difference is a constant, not a class
basics
~20 sA hash set is normally the same hash table with the value half unused: each entry holds the key and its cached hash, and a membership test is an ordinary lookup reporting found or not found.
solid answer
~40 sTwo designs share one engine. The wrapper approach stores every key against a single shared placeholder value, so a membership test is just a lookup that checks whether anything was found. The deliberate approach parameterises the storage so the value column is never allocated at all, saving one slot per entry. Either way the set inherits the engine's hash function, collision handling, growth policy and slot-order iteration, so it is unordered for exactly the reason the map is. Asymptotics are identical — expected constant-time lookup and insert, linear worst case when everything lands in one bucket — and the honest differences are a constant factor of memory and a narrower operation set, since insertion returns only whether the key was new.
go deeper
Be ready to say that a hash set is the same hash table with the value side unused, and that a membership test is a lookup. Recall that both give expected constant-time insert and lookup.
Explain the two implementations — a wrapper storing one shared placeholder versus an engine with the value column elided — and say what each costs per entry and per empty slot.
Show why sharing the engine matters in production: one hash function, one growth policy, one set of pathologies to tune, and set iteration order that can shift the moment the table grows.
Own the API-versus-storage call. Whether the set wraps the map or both sit on a shared engine decides what you can change later without breaking either surface, and who maintains the collision and growth logic.
## One engine, two public faces A hash table is a machine for turning a key into a slot: compute a hash, derive an index, resolve collisions, grow when it gets crowded. Nothing in that machine cares whether a payload is attached to the key. That is the whole reason a set and a map are almost never separate structures in production code — the set is the map engine with the payload column ignored, elided, or filled with one shared placeholder. Concretely, an entry in a general-purpose engine tends to carry three things: | Field | Why it exists | Needed by a set? | |---|---|---| | the key | equality checks after a slot hit | yes | | the cached hash (or a few bits of it) | cheap rejection before comparing keys; cheap resizing | yes | | the value | the map's payload | no | A set needs the first two and not the third. That is the entire difference. ## The two implementations **Set as a wrapper.** The set object holds a map internally. Insert stores the key against one placeholder object shared by every entry — a single allocation for the whole table, not one per element. Membership testing performs a lookup and reports whether anything came back. Removal delegates. This is the cheapest possible implementation to write and to maintain: zero new collision logic, zero new growth logic, and every bug fix in the engine lands in both containers at once. Its cost is that the storage still contains a value slot per entry, holding the same reference over and over. **Set as a configuration of the engine.** The table is written so the value storage is a separate array (or a compile-time-selected field) that a set instantiation simply does not allocate. Now the placeholder disappears and so does its slot. In a flat, array-of-slots layout this saves more than it looks like: the value width is paid for every slot in the capacity, including the empty ones, so at a load factor of 0.7 you were paying about 1.4 unused value words for every element actually stored. Both designs are legitimate, and both exist in the wild: Java's hash set is literally a hash map holding one shared placeholder value, while Python's set is a separate implementation built on the same open-addressed ideas rather than wrapping the dictionary. ## What the set inherits — including the annoying parts Because the engine is shared, everything about the engine shows through: - **Costs.** Expected constant-time insert, lookup and removal; linear worst case when many keys collide. A set is not asymptotically faster than a map. It stores less per entry; it does not do less work per operation. - **Iteration order.** Elements come back in slot order, which is a product of the hash values, the capacity, and the history of resizes. That is not insertion order and it is not sorted order, and it can change after growth, because growth remaps keys to new slots. Code that relies on the order it happened to observe is relying on an implementation detail. - **Hash quality.** A set built on a masked engine has the same sensitivity to badly distributed hashes as the map does. If a key type's hash concentrates its entropy in bits the index step throws away, the set degenerates exactly like the map. - **Mutation hazards.** Mutating a key after insertion so that its hash changes strands the entry: it sits in a slot the new hash no longer selects, so membership tests report absence while iteration still yields it. Identical hazard, identical cause. ## Where the API genuinely diverges The operation set is narrower, and the differences are informative. A map's insert can return the previous value; a set's insert has no value to return, so it returns whether the key was new — which is exactly what deduplication code wants. A map supports lookup-or-default and compute-if-absent; a set's equivalent is a single boolean. Bulk operations differ too: union, intersection and difference are natural on sets and awkward on maps, precisely because there is no payload to reconcile when the same key appears on both sides. ## What an interviewer is checking The question looks like trivia and is not. Candidates who answer "a set is a map with dummy values" and stop have memorised a sentence. The signal is in what follows: that both containers share one growth policy and one collision strategy, that the memory saving of a purpose-built set is a slot per capacity rather than per element, that neither container promises an iteration order, and that the choice between wrapping and parameterising is a maintenance decision — one engine to tune and fix, versus one container that pays for a column it never reads.
- If both are the same engine, where does a purpose-built set actually save memory?It drops the value storage entirely. A wrapper still reserves a value slot for every entry, all pointing at one shared placeholder; in a flat layout that width is reserved for every slot in the capacity, empty ones included. So the saving is roughly one machine word per slot, not per element — noticeable on a large table of small keys, negligible on a small one.
- Why does iteration over such a set come back in an order nobody chose?Iteration walks storage, not history. An element's position is determined by its hash, the current capacity and how collisions were resolved when it arrived, so the visible order is an artefact of the layout. Growth reassigns slots and can reorder everything. Treat it as unspecified: if you need an order, sort the elements or use a structure that maintains one.
- Does storing a placeholder value let the set skip caching each key's hash?No, and dropping the cached hash is a false economy. The cached hash lets a lookup reject a mismatched slot by comparing one machine word before doing any key comparison, which matters when keys are strings or composite objects. It also lets a resize place every entry without calling the hash function again. Sets keep it for the same reasons maps do.
A guest list and a coat-check register are the same ledger; the set version simply leaves the ticket-number column blank.
saying these in an interview costs you the question
- Says a set is asymptotically faster because it stores less
- Claims a hash set guarantees sorted or insertion order
- Thinks a set needs its own collision-resolution scheme
- Assumes a membership test avoids computing a hash
- Believes duplicates are rejected by scanning all elements