SearchāŒ˜ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Java

Basic Operations in Hash Table

Explore the core operations of hash tables including insertion, search, and deletion using Java. Understand how keys are processed through hashing to access array positions, and learn about the time and space complexity of each operation. Gain insight into the simplified implementation and its limitations related to collisions and deletion handling.

We'll cover the following...

After understanding what a hash table is and how a hash function works, the next step is to study the three fundamental operations that make hash tables useful in practice: insertion, search, and deletion. These operations allow data to be stored, retrieved, and removed efficiently using a key.

In a hash table, each operation begins in the same way: the key is passed through the hash function to compute an index in the underlying array. Once that index is known, the table can access the corresponding location directly.

Hash table structure

To understand how insertion, search, and deletion work, it is helpful to first look at the internal structure of a simple hash table. In this lesson, the hash table is implemented using a single array called table. Each position in this array represents one slot in the hash table and can store either null or a (key, value) pair.

The class also includes a helper method called hash(), which uses Java's built-in hashCode() method on a key and then uses the modulo operator to convert the result into a valid array index.

Java 25
public class HashTable {
    private int size;
    // Single array to store key-value pairs
    private Object[][] table;
    public HashTable(int size) {
        // Total number of slots in the table
        this.size = size;
        this.table = new Object[size][2];   // Each slot holds [key, value]
    }
    public HashTable() {
        this(10);   // Default size of 10
    }
    private int hash(String key) {
        // Compute an index using Java's built-in hashCode method
        return Math.abs(key.hashCode()) % size;
    }
}
A hash table class

Each index in table represents one slot in the hash table. When a key is inserted, searched for, or deleted, the hash function determines which slot should be used. This simple structure provides the foundation for the three basic operations of hash tables.

The insertion operation

The insertion operation adds a new key-value pair to the hash table.

When a key is inserted, the hash function computes the index where the pair should be stored. The key and value are then placed at that position in the underlying arrays.

If the key already exists in the table, insertion usually updates its associated value instead of creating a duplicate entry. This ensures that each key appears at most once in the table.

Steps for insertion

The insertion process can be described as the following sequence of steps:

  1. Compute the hash of the key to determine the index.

  2. If the target location is empty, store the new key-value pair there.

  3. Otherwise, if the target location is not empty:

    1. If the same key is already present, update its value.

    2. If a different key is already present at that index, a collision has occurred.

Let's look at the following interactive visualizer for a better understanding of insertion in hash tables.

Java implementation

The following method implements the insertion operation in the hash table class:

Java 25
public void insert(String key, int value) {
    // Compute the index for the key
    int index = hash(key);
    // If the slot is empty, insert the new key-value pair
    if (table[index][0] == null) {
        table[index][0] = key;
        table[index][1] = value;
        return;
    }
    // If the key already exists, update its value
    if (table[index][0].equals(key)) {
        table[index][1] = value;
        return;
    }
    // A different key is already stored at this index
    throw new RuntimeException("Collision detected - collision handling required");
}
Insertion in hash tables

This method first computes the array index using the hash function. If that location is empty, the key and value are stored there. If the same key is already present, the old value is replaced by the new one. If the location contains a different key, the insertion throws a RuntimeException because this simplified implementation does not yet handle collisions. Collisions will be discussed later in the chapter.

Time complexity

The insertion operation involves several steps.

  • Computing the hash value of the key takes O(k)O(k), where kk is the length of the key.

  • Reducing the hash value to a valid index using the modulo operation takes O(1)O(1).

  • Accessing the array at that index also takes ...