What is a hash set?

A hash set is a hash table stripped down to answer just one narrower question, “have I seen this specific item before,” rather than storing a full value alongside each key, which makes it the natural structure for HNSW‘s search process to use when tracking which vectors have already been visited during a single search.

How does a hash set actually differ from the fuller hash table covered elsewhere in this glossary?

A hash table, covered elsewhere in this glossary, stores a complete value alongside each key, letting a lookup retrieve that stored value given its key. A hash set drops the “value” half of that pairing entirely and keeps only the keys themselves, since its whole purpose is answering a simple yes-or-no question — is this specific item present in the set or not — rather than retrieving any associated data. Under the hood, a hash set typically relies on the exact same hashing mechanism a hash table uses to achieve its fast, close-to-instant lookups, just applied to a simpler membership-only question rather than a full key-to-value mapping.

Why does HNSW’s search process specifically need this kind of fast membership check?

While navigating HNSW‘s graph, covered throughout this site’s coverage of how the algorithm searches step by step, the search repeatedly moves from one vector to its neighbors, and it needs to quickly determine whether each neighbor has already been examined earlier in the same search before spending further effort investigating it again. Checking this “already visited” status using a linear scan, covered elsewhere in this glossary, through every previously-visited vector would grow steadily more expensive as a search progresses and visits more vectors, whereas a hash set answers this exact same “have I seen this before” question in close to constant time regardless of how many vectors have already been visited, which keeps this bookkeeping overhead from becoming a meaningful drag on the search’s overall speed.

Why does avoiding redundant re-visits of the same vector actually matter for how efficiently a search runs?

Without tracking visited vectors, a greedy search process, covered elsewhere in this glossary, risks wastefully re-examining the same vector multiple times as it explores different paths through the graph that happen to pass through it more than once, spending real computational effort on distance calculations that produce no new useful information the search hasn’t already obtained. A hash set eliminates this waste directly, letting the search immediately recognize and skip any vector it’s already examined, ensuring that every distance calculation the search performs is actually contributing new information toward finding the query’s true nearest neighbors rather than needlessly repeating work already done.

A hash set’s simple, fast membership tracking is a small but meaningful piece of what keeps HNSW’s search efficient, preventing wasted effort on vectors already explored earlier in the same search. From here, the pages on hash table and on how HNSW searches a graph step by step tie this supporting structure back to the broader search process it quietly keeps efficient.