Differences Between HashMap and HashSet and Hash Table Fundamentals

HashMap and HashSet Differences

HashSet is implemented using HashMap; HashMap stores key‑value pairs while HashSet only stores keys as values are constant.

Internally both use an array of buckets where each bucket holds a linked list (separate chaining) forming a hash table.

HashMap storage process

Call hashCode() on the key to obtain an int hash.

Use the hash as an index; if the bucket is empty, store the Entry (key, value) there.

If the bucket is not empty, traverse the linked list, compare keys with equals() ; replace the value if the key matches.

If no matching key is found, insert a new Entry at the head of the list.

HashSet storage process

Compute the element’s hashCode .

Derive the bucket index from the hash.

If the bucket is empty, store the element directly.

If the bucket already contains elements, compare with equals() ; duplicate elements are rejected.

Summary

Key interview points include using hash tables to solve problems, understanding hash table principles, and collision‑resolution strategies.

Collision resolution

Open hashing (separate chaining) – each bucket holds a linked list.

Closed hashing (open addressing) – probe for the next empty slot.

Hash table resizing

When usage exceeds about 30 % of capacity, the table should be expanded (typically doubled) and all entries rehashed.

Hash function implementation example

public class Solution {
    /**
     * @param key: A string you should hash
     * @param HASH_SIZE: An integer
     * @return: An integer
     */
    public int hashCode(char[] key, int HASH_SIZE) {
        // write your code here
        long ans = 0;
        for (int i = 0; i < key.length; i++) {
            ans = (ans * 33 + (int) (key[i])) % HASH_SIZE;
        }
        return (int) (ans);
    }
}