Hello, dear students in this class, and we are going to talk about one more implementation of map
interface linked hash map, we're going to understand how the hash map is different from hash map will
review structure of link, hash map and we'll review methods that it has.
I'm going to explain to you what the cash is and how we can implement our own cash with the help of
the hash map.
Also, we'll learn how to implement logic that would keep fixed number of elements in our linked hash
map object.
Let's start to understand how linked hash map work.
Let's look at this slide.
First of all, what we have to understand is that hash map is also implemented on the base of hash table.
Then hash map has projectable iteration order.
How is this achieved?
It is achieved because of the support of double placed inside.
On the screen.
You can see the image that represents the structure of each bucket and hash table and in addition to
that, the properties that allows us to link elements in both directions.
That's why when we insert each new entry in the hash map, each entry now is about the next and previous
entry that allows us to iterate over this data structure with predictable order.
There are also a few more differences in length hash map that I would like to show you in the source
code.
Here is a source code of linked hash map class.
Notice that it extends hash map class and implements map interface.
I'd like to draw attention to the special constructor that also takes Boolean Flag as one of the arguments.
This documentation set that we have to pass through for access, order and force for insertion order.
When I read this first time for me it is not obvious what is the difference between axis order and insertion
order.
I would say that these are two a different order mechanism.
By default it is insertion order, but we can set access order by passing through into this constructor
access.
So the strategy will ensure that order of iteration of elements is the order of in which the elements
were last accessed from the list recently accessed, the most recently accessed.
You might be wondering when this can be used.
I know that the things are better learned when you know that you can apply your knowledge and practice
access order maybe come in handy when you want to implement cache.
Probably.
You heard those words the first time.
Let me explain you what a cache is.
Cash is a hardware or software component that stores data so that future requests for that data can
be served faster.
The data stored in the cache might be as a result of an earlier computation or a copy of data stored
elsewhere.
For example, you can always keep in cache information about products that attribute most of the times
to save time on retrieving all information for product details.
Page.
We can just store these products in cash and retrieve them only when it is needed to be cost effective
and to enable efficient use of data caches must be relatively small.
That's why there are several content eviction policies that keep size of the cache fixed.
Sometimes it is also called cache replacements.
Algorithms.
Once a cash flow algorithm should choose which items to discard to make room for the new ones.
There really a lot of different election policies.
Some of them are first in, first out, last in, first out.
You already know what FCF oh, and LIFO means last recently used.
According to the strategy, we discard elements that were not used for a long time.
The logic that stands behind that is in the case element is not used.
There is no science to keep it in cash and it is better to substitute it with a new element.
And in case here is a good new element already in the element that counts as usage and element is moved
on the new place in this data structure to not be removed.
By the way, this is one of the most popular ones.
You're going to have a homework to implement your own cache with the help of the hash map most recently
used the eviction strategy.
It works in the opposite way from least recently use cache.
Among the other eviction strategies.
It is also possible to mention random replacement, least frequently used, least frequently recently
used, etc..
So I believe now when you know what the cache is, you can imagine how we can use length hash laced
to implement cache.
The Access Order EnLink hash map allows us to implement LRU cache an easy way, but what else?
We need to implement cache with the help of the cache map.
We need to set the size of our cash and then cache map can help us to support fixed size of our cache.
How not to get back to the source code in the source code of link Hashmat we can find Remove Alessandri
remastered.
This method is invoked by Puth and put all methods after incertain and you entry into the map.
And in case this message returns through, that means maps should remove its earliest entry.
You can see that it has protected access modifier.
That means it is not available by default outside of this package and outside of this class and its
child classes.
The idea is, in case you have to implement cash, we have to override this method and implement the
rule that would tell us when we have to remove the Elvis element.
Does it make sense?
And prepare, for example, to show you this, here is a class that extends length.
Hashmat, I also declared filled with a name capacity that contains the value of max elements in the
current map, how elements will be removed automatically.
I will let little hash map to handle or remorse.
What I have to do is to override or remove Alessandri and return true when elements should be removed
from map.
So when the size of map will become more than capacity, then we have to remove the our capacity by
default is three elements.
Now, let me create the object of the current class and add four entries here.
By default, I insertion order.
And that means that when I add force element, the first one should be removed here.
Aberrant elements to cancel.
Let me run the program to show you console output.
And here we can see that the first entry is removed.
Now you have enough information that will help you to implement your homework from the public interface
that link Hashmat provides.
There is no massive that present in this class and absent in hash map since this class extends Hashmat.
That means all methods that were reviewed and Hashmat lesson and that were reviewed during the review
of map interface are also available for objects of the hash map type.
That's why we want to review those methods again.
So that's all what I wanted to share with you regarding the hash map.
Now let's recap what we have learned today in this lesson we reviewed and in fact, map class.
We learned how law enforcement works and what are key features of this type.
Now we know what the difference between insertion, order and access order is and how to change the
smooth inline hash map.
After that, we learned what a cache is.
Now, you know, the theory of different election policies and you know that Lenfest map can be used
to create LRU cache.
Also, we learned how to override the method that would keep constant number of elements.
EnLink hash map.
Now I suggest reviewing your homework.
You have to implement Alario Cash on the basis of little cash map here.
I provided you with an interface that you have to implement.
According to this task, you have to implement three methods yet that returns value by key on minus
one in case the key is not found.
Good method that should put key value pair of jeans or update the value for key if such already exists
and set capacity method that sets maximum number of elements that can be stored in cash.
Try to use knowledge that you gained in this lesson to implement this task.
I also share my solution for this task in attachments to this lesson.
After you're done, you can compare two solutions if you wish.
That's all for today.
Thanks a lot for your attention.
See you in the next lesson.