Do caches need to be key-value pair?

Question

From my understanding caching is to store data at a convenient location, for quick access. Each implementation of caching (eg: LinkedHashMap, MemcacheD ) are key-value store. It makes sense, I agree. But my question is do cache by default also imply a key-value ? in other words wont an arraylist of objects be considered a cache ? In other words, if while implementing LRU cache is it necessary that I need the data to be an Entry<key, value> object ?

I explained in 3 different questions to prevent questions requiring more explanation / incomplete data provided etc.

Answer 1

in other words wont an arraylist of objects be considered a cache ?

Yes, you might use it as a cache. The array index is then your cache key.

The problem with the array list is that you usually can not suggest from an index to the object. I mean the index is usually not a meaningful reference data of the data you are mapping it to.

If you think about why caches are key-value based you have to think about the problem that a cache solves.

The problem a cache solves is:

How to access a data structure that is time consuming to obtain quickly through some easy reference data?

Thus you always have some data that is just a referent for a data structure that is hard to obtain, e.g. customer no. -> customer. These referent data is called the cache key. It is an easy data structure with enough information to create or obtain the more complex data structure. So it is just a mapping and therefore a cache is usually implemented by a map data structure.

Back to the initial question

in other words wont an arraylist of objects be considered a cache ?

We can now understand that using an array means that you have reference data that is just an integer. So the array list cache will usually be very fragmented with a lot of unused space. Think about the customer no. -> customer example. In this example the array list's size must be at least the largest customer no. that's cached and it grows if a new customer with a larger customer no. should be cached.

If we want to optimize this we have to find a way to map the complete integer range to an extremely smaller range. But if we do this there might be two customer no. that are mapped to the same index. Thus we would have a collision. To handle this we must introduce use a list or some kind of linked data structure to save all objects with the same value at a position.

That's how a HashMap works.

Answer 2

I think, it is not about using a specific strategy, Its all about the goal of cache.

What is expected from a cache - A good pointer could be http://commons.apache.org/proper/commons-jcs/

Key-Value pair easily fits with many popular algorithm (including apache one) to implement a cache, and hence becomes a natural candidate.

But, I think there is no issue in using any other algorithm, which may not be based on key-value pair. In that case, you may need to write a new implementation of a caching scheme from scratch.