A well implemented HashMap in Java would give you performance of O(1) for get and put. Well implemented in this case means your hashCode and equals are helpful to reduce collisions.
From Java 7 to Java 8 the HashMap implementation changed from using linkedList to balance trees to resolve collisions, this means for very bad implementation (sometimes there are just collisions) of hashCode which may result in many collisions we’ll no longer have a LinkedList of items,which would give us O(n) worst case. Balance trees improve this with a O(log n) from Java 8. This article talks about it in depth.
Now to the main point of this article, there are many In-Memory Key-Pair databases there. Eg: Redis. But just in case you want one built with HashMap data type. Which can get you performance of O(1) for both put and get without using a framework HashMaps would be our go-to data structure.
But the problem with using HashMap as a cache is,if you don’t control the size it might blow up your memory. The default HashMap can grow in size. If memory is not your problem you are good to go with HashMap but if you want to control the size and the items to be stored with FIFO priorities then let’s continue.
Unfortunately HashMaps don’t maintain the order of items when inserted. Why do we need the order?, we need the order to determine what gets to leave the queue. That is know the order the items were entered.
LinkedHashMap however maintains the order and also has removeEldestEntry
By simply extending the properties of removeEldestEntry. We can build an in-memory cache with fixed size HashMap with O(1) performance for get and push operations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class HashMapCache<K,V> extends LinkedHashMap{
private final int maxSize;
public FixedSizeHashMap(int maxSize) {
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
@Override
public boolean equals(Object obj){
return obj==this;
}
@Override
public int hashCode(){
return System.identityHashCode(this);
}
}
Lets write a test to test our implementation. You can see I’ve not written tests for all the behaviors of a ListHashMap. Our main focus is to see if your canPushEarliestOut() would be green.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class HashMapCacheTest{
@Before
public void setup() {
fixedSizeHashMap.put("one", "one");
fixedSizeHashMap.put("two", "two");
fixedSizeHashMap.put("three", "three");
}
@Test
public void hasRightSize() {
Assert.assertEquals(3, fixedSizeHashMap.size());
fixedSizeHashMap = new FixedSizeHashMap<>(5);
Assert.assertEquals(0, fixedSizeHashMap.size());
}
@Test
public void canAdd() {
Assert.assertTrue(fixedSizeHashMap.containsKey("one"));
Assert.assertEquals(3, fixedSizeHashMap.size());
}
@Test
public void canGet() {
Assert.assertTrue(fixedSizeHashMap.containsKey("one"));
Assert.assertTrue(fixedSizeHashMap.containsKey("two"));
Assert.assertTrue(fixedSizeHashMap.containsKey("three"));
Assert.assertEquals(3, fixedSizeHashMap.size());
}
@Test
public void canPushEarliestOut() {
Assert.assertTrue(fixedSizeHashMap.containsKey("one"));
Assert.assertEquals(3, fixedSizeHashMap.size());
fixedSizeHashMap.put("four", "four");
Assert.assertFalse(fixedSizeHashMap.containsKey("one"));
Assert.assertTrue(fixedSizeHashMap.containsKey("four"));
Assert.assertEquals(3, fixedSizeHashMap.size());
}
}
REFERENCES
https://dzone.com/articles/hashmap-performance - Tomasz Nurkiewicz