kv-store

A small in-memory key-value store, built from scratch in Java — no java.util.HashMap under the hood, no framework. LRU eviction + per-key TTL on top of a hand-written hash table.

Why

Built to close a specific gap: knowing that HashMap/ArrayList/HashSet exist isn't the same as knowing how they work. This project forces that understanding by implementing the pieces directly.

Design

• CustomHashMap<K, V> — separate chaining for collisions, dynamic resize (doubles + rehashes) once load factor passes 0.75, same bit-spreading trick (h ^ (h >>> 16)) java.util.HashMap uses before masking into a bucket index.
• Node<K, V> — doubles as a CustomHashMap value and as a doubly-linked-list node, so KVStore gets O(1) "move to front" without a second lookup.
• KVStore<K, V> — wires the map + linked list together for O(1) get/put/delete. Capacity overflow evicts the LRU tail. TTL is lazy (checked on read) and active (a background daemon thread sweeps expired entries every second, so dead keys don't sit in memory forever if nobody reads them). A ReentrantLock guards all mutation for thread safety.

Run it

javac -d out $(find src -name "*.java")
java -cp out com.sayandip.kvstore.Main          # demo
java -cp out com.sayandip.kvstore.KVStoreSelfTest  # test suite (16 checks, no JUnit needed)

Talking points for interviews

• Load factor / resize trade-off: why 0.75, what happens if you resize too eagerly vs too rarely.
• Chaining vs open addressing for collision resolution, and why chaining was the simpler correct choice here.
• Why Node is shared between the hash map and the linked list instead of two separate structures (avoids a second map lookup on every LRU reorder).
• Lazy vs active expiry — same idea Redis uses, and the honest cost of the current O(n) sweep vs a min-heap-by-expiry version.
• Where a ReentrantLock around the whole store is fine at this scale and where it'd become the bottleneck (would need striped locking to scale).

Possible next steps

• Thin TCP or HTTP layer so it's a running service, not just a library.
• Replace the sweep with a min-heap keyed by expiry time.
• Striped locking instead of one lock for the whole store.