The main purpose of a cache system is to provide faster access to data stored in cache with limited capacity. Therefore, we can summarize the basic requirements of a cache system as followings:
- When the max size of the cache is reached, remove the least recently used key.
- Whenever a key is fetched or updated, it becomes the most recently used.
- Both
get
andput
operations complete in O(1) time complexity (meaning that no matter how large the cache is, it takes the same amount of time to complete). - When fetching a key that doesn’t exist, return a
null
value.