Hi guys, I need to store my key-value pairs in a map which should have a limited size. If the map reaches its limit, for a new put, the eldest key-value pair should be dropped and the new one should be added. I do not want to utilize an extra data structure for timings in addition to my map. Could you recommend a data structure for this? I searched some types of maps in collection framework but i cannot find a built-in support for FIFO in maps. Can i use SortedMap for this?
this requirement is a serious one because we have memory limitations and this map would have more than 1 million key-value pairs. If we utilize another structure it would be as large as this map (am i wrong?) and it consumes more memory.
LinkedHashMap maintains the elements in the order that they are inserted in the map. It does this by maintaining a linked list of the elements of the map under the covers (so then you do have a second data structure, even though you don't see it directly!).
Every time you insert something into the LinkedHashMap, you'd have to check if it becomes too large and if yes, you remove the topmost element (which is the oldest element that was inserted).
Note that if you want to do what you want to do, you have to maintain extra information one way or another to be able to keep track of which element is the oldest.