Master Hash Tables - O(1) Magic

class HashTable {
    constructor(capacity = 8) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = Array.from({ length: capacity }, () => []);
    }

    _hash(key) {
        // DJB2 hash function
        let hash = 5381;
        for (let i = 0; i < String(key).length; i++) {
            hash = ((hash &lt;&lt; 5) + hash) + String(key).charCodeAt(i);
        }
        return Math.abs(hash) % this.capacity;
    }

    insert(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        // Update existing key
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value;
                return;
            }
        }

        // Insert new key
        bucket.push([key, value]);
        this.size++;

        // Check load factor and resize if needed
        if (this.size / this.capacity > 0.75) {
            this._resize();
        }
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (const [k, v] of bucket) {
            if (k === key) return v;
        }
        throw new Error("Key '" + key + "' not found");
    }

    delete(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                const value = bucket[i][1];
                bucket.splice(i, 1);
                this.size--;
                return value;
            }
        }
        throw new Error("Key '" + key + "' not found");
    }

    _resize() {
        const oldBuckets = this.buckets;
        this.capacity *= 2;
        this.buckets = Array.from({ length: this.capacity }, () => []);
        this.size = 0;

        for (const bucket of oldBuckets) {
            for (const [key, value] of bucket) {
                this.insert(key, value);
            }
        }
    }
}

// Usage
const ht = new HashTable();
ht.insert("name", "Alice");
ht.insert("age", 25);
ht.insert("city", "NYC");
console.log(ht.get("name")); // Output: Alice

package main

type Entry struct {
    Key   string
    Value interface{}
}

type HashTable struct {
    capacity int
    size     int
    buckets  [][]Entry
}

func NewHashTable(capacity int) *HashTable {
    buckets := make([][]Entry, capacity)
    for i := range buckets {
        buckets[i] = make([]Entry, 0)
    }
    return &HashTable{
        capacity: capacity,
        size:     0,
        buckets:  buckets,
    }
}

func (ht *HashTable) hash(key string) int {
    hash := uint64(5381)
    for i := 0; i < len(key); i++ {
        hash = ((hash &lt;&lt; 5) + hash) + uint64(key[i])
    }
    return int(hash % uint64(ht.capacity))
}

func (ht *HashTable) Insert(key string, value interface{}) {
    index := ht.hash(key)
    bucket := ht.buckets[index]

    // Update existing key
    for i := range bucket {
        if bucket[i].Key == key {
            bucket[i].Value = value
            return
        }
    }

    // Insert new key
    ht.buckets[index] = append(bucket, Entry{key, value})
    ht.size++

    // Check load factor
    if float64(ht.size)/float64(ht.capacity) > 0.75 {
        ht.resize()
    }
}

func (ht *HashTable) Get(key string) (interface{}, bool) {
    index := ht.hash(key)
    bucket := ht.buckets[index]

    for _, entry := range bucket {
        if entry.Key == key {
            return entry.Value, true
        }
    }
    return nil, false
}

// Usage
func main() {
    ht := NewHashTable(8)
    ht.Insert("name", "Alice")
    ht.Insert("age", 25)
    ht.Insert("city", "NYC")

    if value, ok := ht.Get("name"); ok {
        fmt.Println(value) // Output: Alice
    }
}

import java.util.ArrayList;
import java.util.List;

class Entry {
    String key;
    Object value;

    Entry(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}

class HashTable {
    private int capacity;
    private int size;
    private List<List<Entry>> buckets;

    public HashTable(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    private int hash(String key) {
        long hash = 5381;
        for (int i = 0; i < key.length(); i++) {
            hash = ((hash &lt;&lt; 5) + hash) + key.charAt(i);
        }
        return (int)(Math.abs(hash) % capacity);
    }

    public void insert(String key, Object value) {
        int index = hash(key);
        List<Entry> bucket = buckets.get(index);

        // Update existing key
        for (Entry entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        // Insert new key
        bucket.add(new Entry(key, value));
        size++;

        // Check load factor and resize if needed
        if ((double)size / capacity > 0.75) {
            resize();
        }
    }

    public Object get(String key) {
        int index = hash(key);
        List<Entry> bucket = buckets.get(index);

        for (Entry entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        throw new IllegalArgumentException("Key not found: " + key);
    }

    private void resize() {
        List<List<Entry>> oldBuckets = buckets;
        capacity *= 2;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
        size = 0;

        for (List<Entry> bucket : oldBuckets) {
            for (Entry entry : bucket) {
                insert(entry.key, entry.value);
            }
        }
    }
}

// Usage
HashTable ht = new HashTable(8);
ht.insert("name", "Alice");
ht.insert("age", 25);
ht.insert("city", "NYC");
System.out.println(ht.get("name")); // Output: Alice

#include <vector>
#include <string>
#include <utility>

template<typename V>
class HashTable {
private:
    int capacity;
    int size;
    std::vector<std::vector<std::pair<std::string, V>>> buckets;

    int hash(const std::string& key) {
        unsigned long h = 5381;
        for (char c : key) {
            h = ((h << 5) + h) + c;
        }
        return h % capacity;
    }

    void resize() {
        auto oldBuckets = buckets;
        capacity *= 2;
        buckets = std::vector<std::vector<std::pair<std::string, V>>>(capacity);
        size = 0;

        for (const auto& bucket : oldBuckets) {
            for (const auto& [key, value] : bucket) {
                insert(key, value);
            }
        }
    }

public:
    HashTable(int cap = 8) : capacity(cap), size(0) {
        buckets.resize(capacity);
    }

    void insert(const std::string& key, const V& value) {
        int index = hash(key);
        auto& bucket = buckets[index];

        // Update existing key
        for (auto& [k, v] : bucket) {
            if (k == key) {
                v = value;
                return;
            }
        }

        // Insert new key
        bucket.push_back({key, value});
        size++;

        // Check load factor
        if (static_cast<double>(size) / capacity > 0.75) {
            resize();
        }
    }

    V get(const std::string& key) {
        int index = hash(key);
        const auto& bucket = buckets[index];

        for (const auto& [k, v] : bucket) {
            if (k == key) return v;
        }
        throw std::runtime_error("Key not found");
    }
};

// Usage
HashTable<std::string> ht(8);
ht.insert("name", "Alice");
ht.insert("age", "25");
ht.insert("city", "NYC");
std::cout << ht.get("name") << std::endl; // Output: Alice

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

struct HashTable<V> {
    capacity: usize,
    size: usize,
    buckets: Vec<Vec<(String, V)>>,
}

impl<V: Clone> HashTable<V> {
    fn new(capacity: usize) -> Self {
        HashTable {
            capacity,
            size: 0,
            buckets: vec![Vec::new(); capacity],
        }
    }

    fn hash(&self, key: &str) -> usize {
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        (hasher.finish() as usize) % self.capacity
    }

    fn insert(&mut self, key: String, value: V) {
        let index = self.hash(&key);

        // Update existing key
        for (k, v) in &mut self.buckets[index] {
            if k == &key {
                *v = value;
                return;
            }
        }

        // Insert new key
        self.buckets[index].push((key, value));
        self.size += 1;

        // Check load factor and resize if needed
        if (self.size as f64 / self.capacity as f64) > 0.75 {
            self.resize();
        }
    }

    fn get(&self, key: &str) -> Option<&V> {
        let index = self.hash(key);

        for (k, v) in &self.buckets[index] {
            if k == key {
                return Some(v);
            }
        }
        None
    }

    fn resize(&mut self) {
        let old_buckets = std::mem::take(&mut self.buckets);
        self.capacity *= 2;
        self.buckets = vec![Vec::new(); self.capacity];
        self.size = 0;

        for bucket in old_buckets {
            for (key, value) in bucket {
                self.insert(key, value);
            }
        }
    }
}

// Usage
fn main() {
    let mut ht = HashTable::new(8);
    ht.insert("name".to_string(), "Alice");
    ht.insert("age".to_string(), "25");
    ht.insert("city".to_string(), "NYC");

    if let Some(name) = ht.get("name") {
        println!("{}", name); // Output: Alice
    }
}