Discussion [Java]Implementing An Lru Cache

[FelonBIG]

Hello there!

 

Let's go straight in the topic!

I want to implement an lru cache for educational purposes.

The main LRU cache class will implement an interface which contains the following methods :

Note : V and K are generic references

 

• V lookUp(K key) : returns the value V with K as its key 
• void store(V value, K key) : obviously stores the data in the cache 
• double getHitRatio() 
• long getNumberOfLookups() 
• long getNumberOfhits() 
• long getNumberOfMisses()

 

Sooooo right now i have an alpha implementation implemented as following :

I use a hashmap which i implement (NOTE : i wanna implement each data structure im gonna use by myself)

to store the values, and a queue where i insert the keys.

Each time an item is inserted, i check the size of the queue.

If queue.size() > cacheSize, i pop() all the expired keys and remove their values from the map

 

So after testing it with Strings and 50k entries input i get the freaking huge time of 17seconds!!!!!!! and a hit ratio of 9%(!)

If i remove the removal of the expired keys the time drops to 1 sec and the hit ratio goes to 98%,but the application isnt an lru cahce implementation.....

 

Another implementation suggested by a friend was to use splay trees, cause the least recently used nodes would be near the root.

I also thought to try and implement B Trees , but i aint so fond of it

 

So , what do you guys suggest?

Which data structures should i use for this "project"?

If i need to use a hashmap , is linear probing the type of hash that would fit, since there are no memory issues?

 

Thanks in advance for your help guys,

Regards FelonBIG

Edited January 24, 2015 by FelonBIG

[FelonBIG]

well since it's outdated you can lock it.

Also i finished an alpha version of this project which i can share for the community if someone's interested.

[MeVsYou]

Locked