Can You Build a HashMap from Scratch? A Step‑by‑Step Java Guide

Understanding Hash Tables

HashMap is Java's implementation of a hash table, a data structure that combines a bucket array with a hash (or scatter) function to achieve near‑constant‑time operations.

Essence of a Hash Table

A hash table is a data structure that provides direct access to elements based on a key.

It consists of two essential components:

Bucket array : a series of slots (buckets) where elements are stored.

Hash function : a function that maps a key to an index in the bucket array.

Bucket Array

In a hash table, each bucket can hold a single element or a collection of elements that share the same index after hashing. The key's hash code is typically reduced modulo the array length to obtain the bucket index.

Hash Function Construction

Common methods for constructing hash functions include:

Direct addressing (not practical for large tables).

Digit analysis.

Mid‑square method.

Folding method.

Division (remainder) method – the most widely used.

In Java, Object.hashCode() returns a 32‑bit integer, which is then reduced modulo the bucket array length using the division method.

Hash Collisions

When two different keys map to the same bucket, a collision occurs. Common resolution strategies are:

Chaining (linked‑list per bucket).

Open addressing (linear probing, quadratic probing, double hashing).

Rehashing with multiple hash functions.

Separate overflow area.

For this implementation we choose chaining .

Implementing a Simple HashMap (ThirdHashMap)

The design includes:

Hash function: hashCode() + division method.

Collision resolution: chaining.

Internal Node Class

/**
 * Node class representing a key‑value pair and a link to the next node.
 */
class Node<K, V> {
    private K key;
    private V value;
    private Node<K, V> next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public Node(K key, V value, Node<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Member Variables

final int DEFAULT_CAPACITY = 16;
final float LOAD_FACTOR = 0.75f;
private int size;
Node<K, V>[] buckets;

Constructors

/** No‑arg constructor sets default capacity */
public ThirdHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
    size = 0;
}
/** Constructor with custom capacity */
public ThirdHashMap(int capacity) {
    buckets = new Node[capacity];
    size = 0;
}

Hash Function (getIndex)

private int getIndex(K key, int length) {
    int hashCode = key.hashCode();
    int index = hashCode % length;
    return Math.abs(index);
}

put Method

public void put(K key, V value) {
    if (size >= buckets.length * LOAD_FACTOR) resize();
    putVal(key, value, buckets);
}
private void putVal(K key, V value, Node<K, V>[] table) {
    int index = getIndex(key, table.length);
    Node<K, V> node = table[index];
    if (node == null) {
        table[index] = new Node<>(key, value);
        size++;
        return;
    }
    while (node != null) {
        if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
            node.value = value;
            return;
        }
        node = node.next;
    }
    Node<K, V> newNode = new Node<>(key, value, table[index]);
    table[index] = newNode;
    size++;
}

Resize Method

private void resize() {
    Node<K, V>[] newBuckets = new Node[buckets.length * 2];
    rehash(newBuckets);
    buckets = newBuckets;
}
private void rehash(Node<K, V>[] newBuckets) {
    size = 0;
    for (int i = 0; i < buckets.length; i++) {
        if (buckets[i] == null) continue;
        Node<K, V> node = buckets[i];
        while (node != null) {
            putVal(node.key, node.value, newBuckets);
            node = node.next;
        }
    }
}

get Method

public V get(K key) {
    int index = getIndex(key, buckets.length);
    if (buckets[index] == null) return null;
    Node<K, V> node = buckets[index];
    while (node != null) {
        if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
            return node.value;
        }
        node = node.next;
    }
    return null;
}

Testing

@Test
void test0() {
    ThirdHashMap map = new ThirdHashMap();
    for (int i = 0; i < 100; i++) {
        map.put("刘华强" + i, "你这瓜保熟吗？" + i);
    }
    System.out.println(map.size());
    for (int i = 0; i < 100; i++) {
        System.out.println(map.get("刘华强" + i));
    }
}

@Test
void test1() {
    ThirdHashMap map = new ThirdHashMap();
    map.put("刘华强1", "哥们，你这瓜保熟吗？");
    map.put("刘华强1", "你这瓜熟我肯定要啊！");
    System.out.println(map.get("刘华强1"));
}

Conclusion

With this straightforward implementation you now have a functional HashMap that can be used in interview coding exercises. In real projects you would rely on Java's built‑in java.util.HashMap, which handles thread safety, advanced hash functions, and performance optimizations.