Using LinkedHasMap for caching in Java

Question

I'm new to using hash table structures. I'm using LinkedHashMap (ex: cache = new LinkedHashMap<K,V>(...)) to implement my own cache. I have a list of questions about this data structure:

I set a parameter capacity = 100 (eg.), it means that number of items in bucket is limited to 100. Then if I insert a new item into this cache (when cache size = 100), am I correct in thinking the evict policy will happen?
In my implementation, keys are composite object include two items like this:
```
class Key { public string a; public string b; @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((a == null) ? 0 : a.hashCode()); result = prime * result + ((b == null) ? 0 : b.hashCode()); return result; } } 
```
With this hashcode(), suppose the bucket already has 100 items. When I insert a new item, assuming that hashcode() returns a duplicate key with a previous item, my understanding is that linkedhashmap will remove the eldest item using the evict policy and use linkedlist to handle collision for the new item, so the number of items in the bucket will be 99. Is it right ?
Is there any way to identify which entries in the bucket current contain a chain for handle collision?

You should really make Key immutable if you are using it as a hash-based map key: make class final, and make a and b final. — Andy Turner
– Andy Turner, Commented Apr 11, 2016 at 8:10
Also: your hashCode implementation is the same as simply return Objects.hash(a, b);. — Andy Turner
– Andy Turner, Commented Apr 11, 2016 at 8:14

mlewandowski · Accepted Answer · 2016-04-11 08:18:38Z

Answering to question one:

You need to explicity override method removeEldest to make the eviction work.

Default implementation returns false, so it won't remove any element:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }

Question two: Nothing will be removed in your case, if you don't override the method removeEldest
Question three: I don't think there is a way to handle such situation.

Please read this useful article to become more familiar with eviciton algorithm based on LinkedHahMap:

http://javarticles.com/2012/06/lru-cache.html

For complementary lecture, read also about LFU eviction: http://javarticles.com/2012/06/lfu-cache.html

dimo414 · Accepted Answer · 2016-04-11 08:21:08Z

I set a parameter capcity = 100 (eg.), it means that number of items in bucket limit to 100. Then if I insert new item to this cache (when cache size = 100), the evict policy will happen,right?

No, the capacity parameter is a hint to the constructor of how large you expect the map to become. It uses this to attempt to avoid needlessly resizing the map as you add elements. If you add more than the specified capacity it will just resize the map to fit more elements efficiently.

when I insert new item, assuming that hashcode() return a duplicate key with one of previous items, then linkedhashmap will remove the eldest item as evict policy and use linkedlist to handle collision for new item, so the number items in bucket will be 99, is it right ?

No, if two non-equal elements are inserted with the same hash code they will simply be placed in the same bucket, but both will still exist and be accessible. Of course if you specify a key that is equal to a key that currently exists in the map, that entry will be overwritten.

Is there any way to identify which entries in the bucket current contain a chain for handle collision?

Generally no. You could use reflection, but that would be arduous at best. What are you trying to accomplish that makes you think you'd need to do this?

The caching behavior provided by LinkedHashMap depends on you extending the class and implementing removeEldestEntry(). As you can see in the example in that method, you can add a check such as size() > MAX_ENTRIES to instruct the map to remove the oldest element when put() or putAll() is called.

If you need a more powerful cache you might like Guava's Cache and LoadingCache classes.

Actually, I want to create an cache using LinkedHashMap in oder to it make sure that no collision happen by the initial ideal is that: Every time we get the hashcode() for one key: h = getHashcode(Key k), then I will update value like this: hashTable[(h+i) modulo size of hash table] = value if the element at this position already have value I will use my own policy to decide it will be replace or not (cache replacement policy). But if I use LinkedHashMap it will automatically handle collision. That's why I can not implement cache as this wa, is it right?
LinkedHashMap (and HashMap) don't allow you to avoid collisions; they are designed to behave well in spite of occasional hash collisions. If you want a data structure that prevents hash collisions (which sounds very much like an XY Problem - what are you actually trying to accomplish?) you'll probably need your own data structure, or you could potentially use a Map<Integer, V> where the keys are the value's hash codes.

Talijanac · Accepted Answer · 2016-04-11 08:15:48Z

Capacity is not fixed. It will dynamically change based on the map usage.

From javadocs:

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

So map will not remove items based on number of entries.

Simple cache to use is provided by guava library.

Collectives™ on Stack Overflow

Using LinkedHasMap for caching in Java

3 Answers 3

1 Comment

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Related