Hash Tables

class HashTable:
    def __init__(self, capacity=8):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def get(self, key):
        for stored_key, value in self._bucket(key):
            if stored_key == key:
                return value
        raise KeyError(key)

    def put(self, key, value):
        bucket = self._bucket(key)
        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[index] = (key, value)  # update, do not duplicate
                return

        if (self.size + 1) / len(self.buckets) > 0.75:
            self._resize(2 * len(self.buckets))
            bucket = self._bucket(key)
        bucket.append((key, value))
        self.size += 1

    def delete(self, key):
        bucket = self._bucket(key)
        for index, (stored_key, value) in enumerate(bucket):
            if stored_key == key:
                bucket.pop(index)
                self.size -= 1
                return value
        raise KeyError(key)

    def _resize(self, capacity):
        entries = [entry for bucket in self.buckets for entry in bucket]
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
        for key, value in entries:
            self.put(key, value)

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;

final class ChainedHashTable<K, V> {
    record Entry<K, V>(K key, V value) {}

    private List<List<Entry<K, V>>> buckets;
    private int size;

    ChainedHashTable(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        buckets = emptyBuckets(capacity);
    }

    private List<List<Entry<K, V>>> emptyBuckets(int capacity) {
        List<List<Entry<K, V>>> result = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) result.add(new ArrayList<>());
        return result;
    }

    private int index(K key) {
        return Math.floorMod(Objects.hashCode(key), buckets.size());
    }

    V get(K key) {
        for (Entry<K, V> entry : buckets.get(index(key))) {
            if (Objects.equals(entry.key(), key)) return entry.value();
        }
        throw new NoSuchElementException(String.valueOf(key));
    }

    void put(K key, V value) {
        List<Entry<K, V>> bucket = buckets.get(index(key));
        for (int i = 0; i < bucket.size(); i++) {
            if (Objects.equals(bucket.get(i).key(), key)) {
                bucket.set(i, new Entry<>(key, value));
                return;
            }
        }
        if ((size + 1.0) / buckets.size() > 0.75) {
            resize(2 * buckets.size());
            bucket = buckets.get(index(key));
        }
        bucket.add(new Entry<>(key, value));
        size++;
    }

    V remove(K key) {
        List<Entry<K, V>> bucket = buckets.get(index(key));
        for (int i = 0; i < bucket.size(); i++) {
            if (Objects.equals(bucket.get(i).key(), key)) {
                V value = bucket.remove(i).value();
                size--;
                return value;
            }
        }
        throw new NoSuchElementException(String.valueOf(key));
    }

    private void resize(int capacity) {
        List<List<Entry<K, V>>> old = buckets;
        buckets = emptyBuckets(capacity);
        size = 0;
        for (List<Entry<K, V>> bucket : old) {
            for (Entry<K, V> entry : bucket) put(entry.key(), entry.value());
        }
    }
}