Not let's look at hostel which is a very interesting and a very widely used data structure it is very 2
widely used as it supports some really fast operations like searching of elements but hash map on how 3
set are based on how stable. 4
And so before we look at them it is important to understand how a hash table looks. 5
It has to as a fundamental data structure that is used to implement an associate to it which associates 6
. 7
He's with values. 8
So it is an area where each element is basically an association between a key and a value. 9
So we're talking about a collection of key value pairs. 10
An example key value pair can be NAME ON PHONE worki is name and value is fun. 11
This would help us to extract a person's phone number given a person's name. 12
So it is very useful for searching on hash table helps us to do it in a very efficient we know each 13
key value pair is also referred to as a mapping on a hash table is also referred to as a dictionary 14
as a dictionary with no help in looking up of words on their corresponding meanings. 15
And here are the key operations of the hash table. 16
We can insert a key value mapping into a hash table and we can also search a mapping using a given key 17
and we cannot remove a particular mapping by using a key and all of these operations happened in a constant 18
time. 19
So how stable is it really fast. 20
And here are some characteristics of a hash table. 21
A hash table can not contain duplicate keys. 22
However it can contain duplicate values which means that are more than one key can have the same value 23
. 24
Also each key maps to at most one value. 25
Now as for notes go certain implementations allow null values but they also allow only one Nalby but 26
some implementations do not allow nulls for Book use as well as what I use on here is an illustration 27
of how a hash table is implemented music that hash table is an associate at it. 28
So as you can see here we have an array and each element of it is referencing a linked list which stores 29
the actual Kubler mappings. 30
So the idea is not storing the key value mappings but it is a linked list which is doing that. 31
So here key is name and value as phone number or not that each slot in the array is commonly referred 32
to as a bucket. 33
Note that each of the linked list can have multiple mappings too as we can see here in the illustration 34
No front of any operation whether it is search insert or delete. 35
The most important goal is to quickly look at the target bucket that is next. 36
And then we need to search the linked list at that particular bucket not could we look at the bucket 37
for a given key value mapping function called hash function is applied on the key. 38
For example here in this diagram Epling the hash function on the key. 39
Lisa Smet build it on the next number one on hash function is basically a function of the key and the 40
arrests and a simple example of hash function will be key more precise and more helps in transforming 41
a lot space into smaller one the smallest space would be the size of the. 42
For instance if you're a resizes want to fight on your key is 315 then 315 Mark 4:59 would give us 15 43
. 44
So 15 would be the target bucket number for the mapping with the key 350 Jindalee hashing in using two 45
functions. 46
Angela also does that as we see here here in the first step function called hash is invoked. 47
And this function would be the hash code of Dekhi. 48
Recall the hash code method in the Object class Rutan's the hash code which would typically be the memory 49
address of the object that is converted into an angry value. 50
So the hash code muttered returns on end value. 51
Also the hash code method is provided in order to support hash table based implementations such as hash 52
map. 53
Later we will see a use case then this method is overridden. 54
So once you get the hash it becomes and is applied on it in order to offset into the hash table that 55
is defined the target bucket. 56
So here because and is used in sort of a modulus operation on here is the source of the hash method 57
in one of the jolliest expressions. 58
But let's not get into the details of this quarter the main goal for has to happen is to operate in 59
constant time and for this the hash function should have these properties. 60
First is it took quickly look at the target bucket. 61
And for this the hash function logic should be highly efficient. 62
For instance a function that uses a sober and moderate application some divisions can be slow but using 63
bitwise and better for operations such as this hash function will give us the performance benefit. 64
Second is the hash function should be able to dispose the elements as uniformly as possible into the 65
buckets. 66
For example if we use only hash code of the key instead of this additional hash function then there 67
is a chance that several keys may get passed into the same bucket. 68
And this is called us hash collision. 69
So even though the keys are different DeMeo it has to the same bucket on all the mappings then be stored 70
in the same linked list. 71
And if a large number of mappings get to the same bucket then operations like search can be slow. 72
That's because once we find the bucket we have to perform a linear search on the corresponding length 73
list in order to find the target mapping. 74
Ideal situation would be to have one mapping per bucket but that is very difficult to get you practically 75
. 76
So we should at least try to minimize the hash map collisions as much as possible which is what this 77
hash function Angela is also trying to do. 78
Let's see how a typical insertion operation looks like. 79
We just look at the bucket for a given key and we check if the bucket is empty. 80
If the bucket is empty then we create a new long list at that index on the mapping into that linked 81
list. 82
But if bucket is not empty which means that there is a collision then we check if the linked list has 83
and then that mapping with the scene key. 84
Now if there is no such mapping then the mapping gets added at the front of the list. 85
But if there is a mapping with the same key then the value in the old mapping is done using the new 86
value. 87
So here there is a collision and we're using a collision resolution strategy called Separate chinning 88
. 89
There is also another technique called Open interesting but we are not going to discuss it here. 90
There are also other factors besides a good hash function that contribute to performance. 91
One is capacity and the other is load factor capacity is the number of buckets in the hash table load 92
factor is about how from the hostel can get before it's capacity is automatically increased for Hasek 93
default capacity 16 points or in flight that is that people will not be resized until it is three quarters 94
. 95
Now in case of data just look at a list resizing is not an issue as it is simply about creating a new 96
larger array on copying the requirements. 97
But with Hastur bill it's not just about copying but the hash function has to be to be applied on all 98
the keys once again as a hash function is dependent on the precise. 99
Now we have a new Orosius. 100
So the keys might get hashed and no buckets. 101
So there is the additional expense of rehashing step with hash tables. 102
So if you're dealing with large number of entries then it is better to create a hash table that a very 103
large initial capacity. 104
Note that if you use a very high load factor then you may have less frequent rehashing but you may have 105
lots of collisions too and that can slow things down normally. 106
Defaults are good unless you are dealing with a large number of entries in which case you might have 107
to do some experiments to choose the right factors. 108
Finally know that hash tables are very widely used if you're familiar with relational databases. 109
You mean other indexes help faster to be full of data and an index can be based on hash tables nice 110
global databases are also based on hostages as are essentially key value stores Djama switch statement 111
also in dentally uses hashing to quickly locate matching case blocks. 112
So that's about hash tables. 113
They're primarily used for fast lookups which is possible by using a good hash function just know that 114
since elements are stored based on the hash function a hash table does not preserve the order of insertion 115
. 116
So elements can get inserted anywhere. 117
So that's about it. 118
Hope you like this lesson on hash tables. 119
Thank you