Hey Guys, A warm welcome to tech-maze, in today's article, we will see how Least Recent Used aka LRU can be implemented, the very basic idea behind implementing LRU is the item which we save should be in order and it should not allow duplicates otherwise implementing LRU will be quite challenging and will end up having unreliable code.
To achieve this we can use that data structure which stores data in some order and does not introduce much complexity to the system, and what can be better than LinkedHashSet or LinkedHashMap.
LinkedHashSet and LinkedHashMap both maintains insertion order.
Lets go through this one by one
LinkedHashSet :----------------------------------
LinkedHashSet stores items in insertion order so the item which has added first will be the oldest item in the set and based on this hypothesis we will be writing the code.
public boolean pushEmployee(Employee employee) {
if(employee == null)
return false;
if(empset.contains(employee)) {
putIfEmployeeExist(employee);
}else if(capacity == empset.size()) {
Employee emp = empset.iterator().next();
empset.remove(emp);
empset.add(employee);
}else {
empset.add(employee);
}
return true;
}
public boolean popEmployee() {
if(empset.size()>0) {
Employee emp = empset.iterator().next();
empset.remove(emp);
return true;
}
return false;
}
public void putIfEmployeeExist(Employee emp) {
empset.remove(emp);
empset.add(emp);
}
Note : The requirement here is, we have to keep track of those employees who has most recently access the company website, this is one of the scenario I have taken in account, there are plenty of scenarios where LRU can be implemented and will be really helpful.
In general the capacity will go higher such as 200, 500 etc but for the sake of simplicity we have considered the capacity as 6.
here we have three methods :
1. pushEmployee : in this method we push the employee details in set whenever employee access the website, following few scenario we have to take care
a.
if the employee which we are pushing in the set doesn't exist then the process is quite straight forward, just check if the size of the set is equal to its capacity if yes then remove the oldest employee and add this employee.
On finishing this process second oldest employee become oldest employee and newly pushed employee will hold latest position in the set.
b.
If the employee which we are pushing in the set exist then the process changes a little bit, in this case first of all we remove this employee object wherever and whichever position it exist in the set and then add the employee object.
On finishing this process, only one object exist of this employee and it will go at the latest position.
2. popEmployee : This method doesn't do any fancy thing, whenever we call this method, it simply remove one employee object, it can either be oldest object in the set or if set contains only one employee object then it will remove that object.
3. putIfEmployeeExist : This method internally called in pushEmployee method when employee exist in the set, please check point b of pushEmployee method for the explanation.
here we finishes LRU implementation using LinkedHashSet
Now lets see how LinkedHashMap can be used for the same purpose
LinkedHashMap :----------------------------------
LinkedHashMap stores items in insertion order so the item which has added first will be the oldest item in the map and based on this hypothesis we will be writing the code.
In this example, we have created a LinkedHashMap with employee id as key and employee object as value, same process will be repeated as done for set except we need to utilize the key to access/remove the object.
public boolean pushEmployee(Employee emp) {
if(emp == null)
return false;
if(empMap.containsKey(emp.empId)) {
pickEmployee(emp);
}else if(capacity == empMap.size()) {
int empkey = empMap.entrySet().iterator().next().getKey();
empMap.remove(empkey);
empMap.put(emp.empId, emp);
}else {
empMap.put(emp.empId, emp);
}
return true;
}
public boolean removeEmployee() {
if(empMap.size()>0) {
int empKey = empMap.entrySet().iterator().next().getKey();
empMap.remove(empKey);
return true;
}
return false;
}
public void pickEmployee(Employee emp) {
int empKey = empMap.entrySet().iterator().next().getKey();
empMap.remove(empKey);
empMap.put(emp.empId, emp);
}
here we have three methods :
1. pushEmployee : in this method we push the employee details with employee id as key in the map whenever employee access the website, following few scenario we have to take care
a.
if the employee which we are pushing in the map doesn't exist then the process is quite straight forward, just check if the size of the map is equal to its capacity if yes then remove the oldest employee and add this employee in the map.
On finishing this process second oldest employee become oldest employee and newly pushed employee holds the latest position in the map.
b.
If the employee which we are pushing in the map exist then the process changes a little bit, in this case, we remove the employee object based on the employee id wherever and whichever position it exist in the map and then add the employee object.
On finishing this process, only one object exist for this employee and it will go at the latest position.
2. removeEmployee : This method doesn't do any fancy thing, whenever we call this method, it simply remove one employee object, it can either be oldest object in the map or if map contains only one employee object then it will remove that.
3. pickEmployee : This method internally called in pushEmployee method when employee exist in the map, please check point b of pushEmployee method for the explanation.
That's all folks in this article, if we closely look into LRU implementation, we will find many places in the project where this can be really helpful and improve the performance of the code.
Hope this will help at some extent to start with Least Recent Used, for complete code, please have a look in the below GitHub project, I will come up with another article shortly.
Git location for the demo : https://github.com/rohitmodi07/Programs
A Big thank you for checking out my article, this really encourage me to come up with more topics.
Here are some resources you might be interested ------------------------