Home › DSA › Foundations

Hash Table and Set

Hash Tables and Sets are powerful data structures used for fast data storage and retrieval. Both utilize hashing to map data to unique indexes, allowing for quick access. Sets, often implemented using hash tables, are collections that store unique elements with no particular order.

Key Characteristics

Hash Table:
- Stores key-value pairs, allowing fast lookups, insertions, and deletions by key.
- Collisions are resolved through methods like chaining (linked lists) or open addressing (probing).
Set:
- Stores unique values with no specific order.
- Designed for quick checks of existence (contains) without duplicates.

Basic Operations on Hash Table

java

import java.util.Hashtable;

public class Solution {

  public static void main(String[] args) {
    // Create a Hashtable
    Hashtable<Integer, String> hashtable = new Hashtable<>();

    // Insert key-value pairs into the hashtable (O(1) on average)
    hashtable.put(1, "Apple");
    hashtable.put(2, "Banana");
    hashtable.put(3, "Cherry");
    System.out.println("Hashtable after insertions: " + hashtable);

    // Access an element by key (O(1) on average)
    if (hashtable.containsKey(2)) {
      System.out.println("Value for key 2: " + hashtable.get(2));
    }

    // Search for an element (O(1) on average)
    if (hashtable.containsValue("Banana")) {
      System.out.println("Hashtable contains 'Banana'");
    } else {
      System.out.println("Hashtable does not contain 'Banana'");
    }

    // Delete an element by key (O(1) on average)
    hashtable.remove(3);
    System.out.println("Hashtable after deleting key 3: " + hashtable);
  }
}

Basic Operations on Hash Set

java

import java.util.HashSet;

public class Solution {
    public static void main(String[] args) {
        // Create a HashSet
        HashSet<String> hashSet = new HashSet<>();

        // Insert elements into the hash set (O(1) on average)
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Cherry");
        System.out.println("HashSet after insertions: " + hashSet);

        // Search for an element (O(1) on average)
        if (hashSet.contains("Banana")) {
            System.out.println("HashSet contains 'Banana'");
        } else {
            System.out.println("HashSet does not contain 'Banana'");
        }

        // Delete an element (O(1) on average)
        hashSet.remove("Cherry");
        System.out.println("HashSet after deletion of 'Cherry': " + hashSet);

        // Iterate over elements (O(n))
        System.out.println("Iterating over HashSet:");
        for (String item : hashSet) {
            System.out.println(item);
        }
    }
}

Complexity Analysis

Time Complexity Analysis for Hash Table and Set Operations

Operation	Hash Table	Set	Explanation
Insertion	Average , Worst	Average , Worst	Hashes the key and stores the value at the calculated index.
Deletion	Average , Worst	Average , Worst	Finds and removes the key by hashing and locating the index.
Search (contains)	Average , Worst	Average , Worst	Checks for the existence of a key by hashing it.
Access by Key	Average , Worst	N/A	Direct lookup of a value using its unique key.

Average : For both hash tables and sets, operations are generally constant time due to hashing.
Worst Case : When hash collisions occur, operations degrade to as elements are stored in lists, requiring linear time to access.

Space Complexity for Hash Table and Set

The space complexity for both hash tables and sets is , where n is the number of elements. Each element has an associated hash and bucket, so the space required grows linearly with the number of entries.

Space Complexity: , as each entry in a hash table or set requires a unique bucket and additional space for the hash function’s metadata.

🤖 Don't fully get this? Learn it with Claude

Stuck on Hash Table and Set? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Hash Table and Set** (DSA) and want to truly understand it. Explain Hash Table and Set from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Hash Table and Set** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Hash Table and Set** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Hash Table and Set** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Linked List Stack and Queue →