Hash Table Introduction

A hash table (also known as a hashing map, hash mapping, or dictionary) is a data structure that stores data in key-value pairs. It achieves fast search, insertion, and deletion operations by computing a hash value for each key to determine its corresponding storage location.

Typically, a hash table consists of an array and a hash function. The hash function maps keys to index positions within the array; this index represents the storage location where that specific key resides in the hash table. Due to differences in the design and implementation of hash functions, hash collisions may occur (i.e., different keys map to the same index position). Resolving these situations requires a collision resolution strategy, with common approaches including chaining and open addressing.

The primary advantage of a hash table is that, on average, the time complexity for search, insertion, and deletion operations is O(1), meaning they are completed in constant time. Consequently, it exhibits high efficiency when processing large datasets. However, under worst-case scenarios, severe hash collisions can degrade performance, causing the time complexity to degenerate into linear time complexity O(n). Therefore, the design and implementation of a hash table must consider strategies to minimize or avoid hash collisions as much as possible.

HashTable Code Implementation

::: code-tabs
@tab Java

import java.util.ArrayList;
class HashTable{
    class HashEntry{
        String key;
        int value;
        HashEntry next;
        
        public HashEntry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private ArrayList<HashEntry> bucket;
    private int slots;
    private int size;
    
    public HashTable(){
        bucket = new ArrayList<>(); // Initialize empty list of entries
        slots = 5;                  // Initial capacity
        size = 0;                  
        
        for (int i = 0; i < slots; i++) {
            bucket.add(null);       // Fill array with nulls initially
        }
    }
    
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    
    private int getIndex(String key){
        int hashCode = key.hashCode();
        int index = hashCode % slots; // Handle negative hash codes implicitly via modulo behavior in Java (though technically requires adjustment for strict mathematical correctness, this is standard library usage)
        return index;                
    }
    
    public int delete(String key){
        int b_Index = getIndex(key);
        HashEntry head = bucket.get(b_Index);
        HashEntry prev = null;
        
        while (head != null){
            if (head.key.equals(key)) { // Found the target entry
                break;
            }
            prev = head;
            head = head.next;          // Traverse linked list nodes in this bucket
        }
    
        if (head == null)             // Key not found, return 0 to indicate failure or no value
            return 0;
        
        size--;                       // Decrement the total count of elements
        
        if (prev != null){            // If there is a previous node in the chain
            prev.next = head.next;    // Bypass current entry
        } else {                      // If this was the first element in the bucket
            bucket.set(b_Index, head.next); // Replace entire bucket content with next node
        }
        
        return head.value;           // Return value of deleted key
    }
    
    public int get(String key){
        int b_Index = getIndex(key);
        HashEntry head = bucket.get(b_Index);
        
        while (head != null){         // Traverse linked list to find the matching key
            if (head.key.equals(key)) {
                return head.value;   // Return value upon finding match
            }
            head = head.next;
        }
        return 0;                     // Key not found, return default 0
    }
    
    public void insert(String key, int value){	
        int b_Index = getIndex(key);
        HashEntry head = bucket.get(b_Index);
        
        while (head != null){         // Check if key already exists in the chain
            if (head.key.equals(key)){
                head.value = value;  // Update existing value
                return;              // Stop insertion process
            }
            head = head.next;
        }
        
        size++;                      // Increment total count of elements
        
        HashEntry new_slot = new HashEntry(key, value);
        new_slot.next = head;        // Insert at the beginning (chaining)
        bucket.set(b_Index, new_slot);
    
        if ((1.0 * size) / slots >= 0.6){ // Check load factor threshold for resizing
            ArrayList<HashEntry> temp = bucket;   // Save current state
            
            bucket = new ArrayList<>();           // Create a fresh list
            slots = 2 * slots;                    // Double the capacity (resize)
            size = 0;                            
            
            for (int i = 0; i < slots; i++) {    // Re-initialize buckets with nulls
                bucket.add(null);
            }
            
            for (HashEntry head_Node : temp){     // Iterate over old entries to rehash them
                while (head_Node != null) {       // Traverse each linked list in the old table
                    insert(head_Node.key, head_Node.value); // Re-insert into new structure
                    head_Node = head_Node.next;      // Move to next node
                }
            }
        }
    }
}

:::