Basic Concept of HashMap

What You Need First Before diving in, make sure you understand the basics of arrays and sequential storage.

A common mix-up among newcomers is treating a hash table as identical to the everyday idea of a key-value Map. They are not the same.

Java makes the distinction clear. Map is simply an interface that declares a small set of operations without implementing them:

interface Map<K, V> {
    V get(K key);
    void put(K key, V value);
    V remove(K key);
    // ...
}

The interface only specifies the contract for key-value operations. Concrete structures such as HashMap fulfill that contract using their own internal design. Other classes, including TreeMap and LinkedHashMap, also implement the same interface.

You can therefore say that the get, put, and remove methods of a HashMap run in O(1) time, yet you cannot claim the same for the methods of the Map interface itself. Swap in TreeMap, which is backed by a binary tree, and those identical method signatures become O(log n).

The distinction matters especially for readers working in languages that do not emphasize interfaces as sharply as Java does. It is easy to hear “key-value operations” and assume insert, delete, lookup, and update must always be O(1). That assumption is incorrect; the cost depends entirely on how the chosen data structure realizes those operations.

In this chapter we will construct a hash table from scratch, examine why its core operations can be O(1), and study two classic techniques for handling collisions.

How a Hash Table Operates Think of a hash table as an array that has been given extra power.

An ordinary array retrieves an element by a non-negative integer index in O(1) time. A hash table lets you retrieve a value by an arbitrary key (a number, a string, or many other types) in the same O(1) time.

The mechanism is straightforward. Under the hood the table is still an array (call it table). A hash function converts the key into a valid index inside that array. Once the index is known, insertion, deletion, lookup, and update proceed almost exactly as they would on a plain array:

# Simplified hash-table logic
class MyHashMap:

    def __init__(self):
        self.table = [None] * 1000

    # insert or overwrite – expected O(1)
    def put(self, key, value):
        index = self.hash(key)
        self.table[index] = value

    # retrieve – expected O(1)
    def get(self, key):
        index = self.hash(key)
        return self.table[index]

    # delete – expected O(1)
    def remove(self, key):
        index = self.hash(key)
        self.table[index] = None

    # must itself be O(1) so the methods above stay O(1)
    def hash(self, key):
        # ...
        pass

Real implementations contain many additional details—design of the hash function and resolution of collisions among them—but once the core idea is clear the remaining work is mostly careful coding.

Core Ideas and Principles

Keys Are Unique; Values Need Not Be A hash table never stores two identical keys, yet values may be duplicated freely.

Compare this with an ordinary array: every index is unique—you cannot have two elements at position 0—while the values stored at those indices can be anything. Hash tables follow the same rule.

The Hash Function A hash function maps an input of arbitrary length (the key) onto a fixed-length output (an array index).

Every core operation relies on this function. If the function itself is slower than O(1), the entire table degrades to the same slower bound, so its performance is critical.

It must also be deterministic: the same key must always produce the same index. Otherwise the table becomes unusable.

Converting a Non-Integer Key into an Integer Languages differ in the concrete technique. In Java every object supplies an int hashCode() method. Unless you override it, the default implementation essentially returns the object’s memory address—an integer that is unique for the lifetime of that object. Calling hashCode() therefore turns any key into an integer.

(The approach has limitations we will address shortly, yet it gives us a uniform way to obtain an integer from any object.)

Guaranteeing a Valid Index hashCode() returns an int that may be negative, while array indices must be non-negative.

A naïve absolute-value conversion fails:

int h = key.hashCode();
if (h < 0) h = -h;

The smallest int is –2^31. Negating it overflows and remains negative in Java (and can produce undefined behavior in other languages). The overflow arises from two’s-complement representation: a 32-bit int uses its highest bit as the sign bit.

A reliable fix clears that sign bit with a bitwise mask:

int h = key.hashCode();
// clear the sign bit so the result is guaranteed non-negative
// bitwise operations are also faster than arithmetic
h = h & 0x7fffffff;
// 0x7fffffff is 0111…1111 in binary
// AND with any int forces the highest bit to 0

(The details of two’s complement can be looked up independently.)

After the value is non-negative it is still typically far larger than the length of the table. The familiar modulo operation folds it into a legal index, exactly as we do with circular buffers:

int hash(K key) {
    int h = key.hashCode();
    h = h & 0x7fffffff;          // non-negative
    return h % table.length;     // legal index
}

Production libraries often replace the remainder with pure bitwise arithmetic for speed; for understanding the concept the modulo form is sufficient. Curious readers can inspect the source of Java’s HashMap.

Hash Collisions Different keys can easily produce the same index. That event is called a collision.

Collisions Cannot Be Eliminated Because a hash function maps an unbounded key space onto a finite set of indices, collisions are inevitable. The situation is analogous to projecting a three-dimensional object onto a two-dimensional shadow: information is lost and a perfect one-to-one mapping is impossible. The only practical response is to handle collisions algorithmically.

Two Classic Resolutions Separate chaining and linear probing (a form of open addressing) are the most common solutions. Conceptually they expand the table either vertically or horizontally.

Separate chaining stores a linked list in every slot of the underlying array. All key-value pairs that hash to the same index are placed in that list.

Linear probing, when a computed index is already occupied, simply examines the next index (and the one after that, and so on) until an empty slot is found.

(The precise insertion order of a few keys produces a characteristic layout in the array; the idea is what matters here.) Later chapters will implement both techniques step by step.

Resizing and the Load Factor Both collision strategies eventually degrade performance if collisions become frequent.

With separate chaining you may have to walk a list of length K, costing O(K). With linear probing you may have to examine a run of K consecutive slots, again O(K). When K grows, the table’s expected constant-time behavior disappears.

Collisions proliferate for two reasons:

A poorly distributed hash function that piles many keys onto the same few indices.

The table simply becoming too full.

The first problem is largely solved by the carefully engineered hash functions supplied by language standard libraries. The second is under our control and leads to the notion of load factor.

Load Factor Load factor quantifies fullness: it is simply the number of stored pairs divided by the length of the underlying array (size / table.length). A higher load factor means more collisions and slower operations.

A chaining table can have an arbitrarily large load factor because its lists may grow without bound; a linear-probing table cannot exceed 1. Java’s HashMap defaults to 0.75—an empirically good compromise that is rarely changed.

When the number of elements reaches the load-factor threshold the table expands, exactly as a dynamic array does: a larger array is allocated and every existing pair is re-hashed into it. Size stays constant while capacity grows, so the load factor drops.

Why Traversal Order Is Unreliable A well-known rule of thumb states that you must never rely on the order in which a hash table yields its keys. The reason follows directly from the implementation.

Traversal is simply a walk over the underlying array:

// Pseudocode – collect every key
KVNode[] table = new KVNode[1000];
List<KeyType> keys = new ArrayList<>();

for (int i = 0; i < table.length; i++) {
    KVNode node = table[i];
    if (node != null) {
        keys.add(node.key);
    }
}

Two facts destroy any stable order. First, the hash function scatters keys essentially at random across the array, so there is no sequential layout comparable to an ordinary array or list. Second, whenever the table resizes, every key is re-hashed against the new length; the same key may therefore land in a completely different slot. Consequently a key that appears first in one traversal may appear last after a few insertions or deletions.

Understanding the mechanism makes the rule obvious; no rote memorization is required.

Why Modification During Iteration Is Risky “Not recommended” is more accurate than “forbidden.” Different libraries handle the situation differently, so the documentation must be consulted.

From first principles the danger is clear: iteration walks the underlying array. An insertion or deletion that triggers a resize replaces that array entirely. What should the ongoing loop observe? Should the newly inserted or deleted elements appear? The same problem exists for any data structure, but resizing makes it especially acute for hash tables.

If the operation is truly necessary, verify the precise semantics in the language documentation first.

Keys Must Be Immutable Only immutable types may safely serve as hash-table keys. This requirement is fundamental.

An immutable object’s state cannot change after construction (Java’s String and Integer are classic examples). Mutable objects such as ArrayList or LinkedList can be altered at any time.

Consequently a String may be used as a key, while an ArrayList should not:

// safe
Map<String, AnyOtherType> map1 = new HashMap<>();
Map<Integer, AnyOtherType> map2 = new HashMap<>();

// syntactically legal, practically dangerous
Map<ArrayList<Integer>, AnyOtherType> map3 = new HashMap<>();

The hazards appear immediately in ArrayList’s hashCode implementation:

public int hashCode() {
    int h = 0;
    for (int i = 0; i < elementData.length; i++) {
        h = 31 * h + elementData[i];
    }
}

Every call walks the entire list, turning every table operation into O(n). Far worse, the hash code depends on the list’s contents. Mutating the list (or any of its elements) changes the hash code. A pair previously stored under that list can no longer be found; it is effectively lost and may also leak memory because the list remains reachable from the table.

A concrete demonstration:

public class Test {
    public static void main(String[] args) {
        Map<ArrayList<Integer>, Integer> map = new HashMap<>();
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(1);
        arr.add(2);
        map.put(arr, 999);
        System.out.println(map.containsKey(arr)); // true
        System.out.println(map.get(arr));         // 999

        arr.add(3);
        // the mapping has vanished
        System.out.println(map.containsKey(arr)); // false
        System.out.println(map.get(arr));         // null
        // the entry still occupies a slot, yet is unreachable
        // and prevents garbage collection of arr
    }
}

Restoring the original contents may make the entry reappear, and a full scan of the underlying array would still locate it, yet such behavior is unacceptable in real code. Mutable keys are simply unpredictable.

Immutable keys such as String avoid the problem. Although String’s hashCode also examines every character, the result is computed once and cached, restoring O(1) average cost.

The same principle applies in other languages; consult the documentation of the particular hash-table implementation to learn how it derives hash codes.

Summary and Review Questions The pieces above describe the internal workings of a hash table. The following questions consolidate the material.

Why are insert, delete, lookup and update said to be O(1)?
Because the table ultimately manipulates an array. The dominant costs are the hash-function evaluation and collision handling. When both are O(1), the four operations remain O(1).

Why does traversal order change?
Resizing alters the length of the underlying array; every key is therefore re-hashed to a potentially different index.

Are the four operations always O(1)?
No. They are O(1) only when the hash function is O(1) and collisions are resolved efficiently. An unsuitable key type (for example an ArrayList) immediately degrades every operation to linear time.

Why must keys be immutable?
All operations depend on a stable hash-derived index. If a key’s hash code can change, previously stored pairs become unreachable, producing serious bugs and possible memory leaks.

A solid grasp of the standard-library sources for your language is the best guarantee of writing efficient code.

The next chapters will implement minimal hash tables that use separate chaining and linear probing, reinforcing every concept introduced here.