Hash Tables II

Advanced Collision Resolution Techniques

Hash Table Performance Optimization

Open Addressing HashMap

public class OpenAddressingHashMap {
    private static class Entry {
        K key;
        V value;
        boolean isDeleted;
        
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.isDeleted = false;
        }
    }
    
    private Entry[] table;
    private int size;
    private final double loadFactor;
    private static final int DEFAULT_CAPACITY = 16;
    
    @SuppressWarnings("unchecked")
    public OpenAddressingHashMap() {
        this.table = new Entry[DEFAULT_CAPACITY];
        this.size = 0;
        this.loadFactor = 0.75;
    }
    
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        
        if ((double) size / table.length >= loadFactor) {
            resize();
        }
        
        int index = findPosition(key);
        
        if (table[index] == null || table[index].isDeleted) {
            table[index] = new Entry<>(key, value);
            size++;
        } else {
            table[index].value = value;
        }
    }
    
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        
        int index = findPosition(key);
        
        if (table[index] != null && !table[index].isDeleted) {
            return table[index].value;
        }
        
        return null;
    }
    
    public boolean remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        
        int index = findPosition(key);
        
        if (table[index] != null && !table[index].isDeleted) {
            table[index].isDeleted = true;
            size--;
            return true;
        }
        
        return false;
    }
    
    private int findPosition(K key) {
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % table.length;
        int probe = 1;
        
        while (table[index] != null && 
               !table[index].isDeleted && 
               !table[index].key.equals(key)) {
            index = (index + probe) % table.length;
            probe += 2; // Quadratic probing
        }
        
        return index;
    }
    
    @SuppressWarnings("unchecked")
    private void resize() {
        Entry[] oldTable = table;
        table = new Entry[oldTable.length * 2];
        size = 0;
        
        for (Entry entry : oldTable) {
            if (entry != null && !entry.isDeleted) {
                put(entry.key, entry.value);
            }
        }
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

Guided Practice

For additional hands-on practice and advanced exercises on hash tables, check out our comprehensive guided project:

• Guided Project: Advanced Hash Tables

LRU Cache Implementation

public class LRUCache {
    private static class Node {
        K key;
        V value;
        Node prev;
        Node next;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final Map> cache;
    private Node head;
    private Node tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }
    
    public V get(K key) {
        Node node = cache.get(key);
        if (node == null) {
            return null;
        }
        
        // Move to front (most recently used)
        moveToHead(node);
        return node.value;
    }
    
    public void put(K key, V value) {
        Node node = cache.get(key);
        
        if (node != null) {
            // Update existing
            node.value = value;
            moveToHead(node);
        } else {
            // Add new
            Node newNode = new Node<>(key, value);
            cache.put(key, newNode);
            addToFront(newNode);
            
            // Handle capacity
            if (cache.size() > capacity) {
                // Remove least recently used
                Node lru = tail.prev;
                removeNode(lru);
                cache.remove(lru.key);
            }
        }
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToFront(node);
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}