Hashing

Hashing For Caching

Caching combines a hash map with recency ordering so lookups are fast and eviction is predictable.

Kind

cache

Time

O(1) expected

Space

O(N)

Steps

Input Keys

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Hash Table / State

bucket 0

empty

bucket 1

empty

bucket 2

empty

bucket 3

empty

bucket 4

empty

Step Timeline

Code + Variables

1get(key): move node to front

2put(key): update or insert

3if capacity exceeded, evict tail

4hash map points to list nodes

capacity3

Loading Lab...