hey what's up everybody welcome back
today's topic is hash tables hey
everybody today I want to talk about
hash tables which is a favorite data
structure of mine and a lot of other
programmers out there and not just
because it sounds like it should be
illegal in some states or the name of
Willie Nelson's favorite restaurant I
mean seriously every time I'm having a
conversation with someone who's not a
programmer and I mention a hash table
everyone always gives me this weird look
like this little smirk on their face
like there's no way that's a real thing
but it is a real thing and today we're
gonna talk about it because it's super
useful also note that all of the source
code for this video is available online
through patreon thank you to all of you
that have contributed to the channel
more information on that in the
description now two hash tables now to
understand hash tables we need to first
talk a little bit about linked lists and
arrays if you're new to linked lists I
do have a few videos that I made on
those I'll link to those in the
description you may want to watch those
first it may make the rest of the video
make more sense but from the beginning
when we first start programming we're
used to using arrays and now lists once
you learn linked lists in order to keep
track of different variables different
objects different chunks of data that we
want to keep track of we like to store
them in arrays unless so these data
structures are simple and they're
sequential meaning that they keep
objects one after another in a
particular order linked lists are a
little bit more flexible than arrays and
make it easier to insert things in the
middle or delete stuff from the middle
without shifting things and copying and
but what about finding things in both of
these data structures now with a linked
list you're going to start at the
beginning and you're going to go through
the list one element at a time until you
find the one that you're looking for now
computers are fast and so if I have a
list of ten elements well that's not too
terrible but if I have a list that has
ten million elements I might get lucky
and the one that I'm looking for might
be the first element in the list but I
might get unlucky and I may have to
search through ten million different
elements in order to find the one I'm
looking for so it could be really fast
it could be really slow sometimes you're
gonna hear this referred to as a linear
time operation or they might say that
it's time complexity is Big O of n all
that means is that the expected time
that it takes to complete the operation
is going to depend on the size on n
which is the the size of the list so as
the list gets bigger the time that it's
expected to take in order to find what
you're looking for is going to grow
linearly so basically the bigger the
list the longer the wait and
tables help us get around this ideally a
hash table should be able to find the
object we're looking for in constant
time ideally it doesn't matter how many
items I have in my in my data structure
I should still be able to find those
items with the same amount of time and
it should be really fast now that's the
ideal case we'll give it a little
reality check later on as we actually
implement these things but that's the
goal that's what we're going for so how
does it work well conceptually a hash
table is an array with a hash function
and yeah I know that a hash function
sounds like a party with a whole lot of
weed being smoked focus people this is
serious stuff so our hash function is
going to take some input it's going to
map and that input to a location in our
array and that's where our item is
stored so say we want to store records
of people in our table and for each
record we are going to store their name
their age their weight stuff like that
and say we want to look up people by
their names
then our hash function is going to take
a name that's the thing we're gonna look
it up by so it's gonna take a string of
characters and it's going to map that to
an integer and that's going to be an
index in our hash table now there are a
lot of different hash functions out
there and they have different strengths
and weaknesses but there's three things
I want you to keep in mind when you're
thinking about a hash function
first of all calling the hash function
on the same input should always produce
the same output if it doesn't we're
gonna have problems in our hash table
isn't going to work
second our hash function needs to be
fast the whole point of this is to make
lookups fast so if it takes a long time
to compute our hash function that's no
good and third our hash functions result
should be pretty random so I want to
spend some time on this last one because
it may not be obvious well let's think
of the simplest function that I can
think of let's say it takes the name and
no matter what name you put in it always
produces a 5 now you can't get any
faster or simpler than that function and
it's super consistent it always produces
the same result but it defeats the
purpose because it's going to try to put
every single person at location 5 in my
hash table and if I want to store more
than one person that's going to be a
problem so we want different inputs to
produce different outputs we want
different names to produce different
locations in our hash table and that's
enough conceptualizing let's just look
at how this works in code so let's start
out simple we have a main function now
let's assume that our hash table is
going to store information about
people let's give each person a name and
that's a lot of names to be up to 256
bytes while I'm up here let's also
define the size of our hash table we'll
start with 10 it's small but it will
work for now and we can always change
that later and we're gonna store a
person's age as well and we could add
other personal information in here but
for now this is gonna do because that
doesn't really change anything as far as
how the hash table works okay now we
need our hash function in this example I
want to look up people by their names so
my hash function is going to take a
named string and map it to a location in
the table which is an unsigned int and
let's start out with a really stupid
hash function we'll just use that one I
talked about before one that always
returns five just to get us started we
can only improve from here now before we
get into building the actual table let's
play around a little bit with the hash
function let's try it out with a few
different names because as we try
different functions I want to look at
how they affect this mapping if I
compile it and run it you can see that
it prints out fives for all the names so
if I use this hash function it will map
everything to the same location in the
table which is location five and that's
not very helpful so we want different
names to map to different locations so
let's try something different let's try
to use something like a checksum so for
this I'm going to get the length of the
string and then go through the string
one character at a time and simply add
up the values of the character so this
is the ASCII values of the characters so
let's declare a variable to keep our sum
started at zero and then each time
through the loop we'll just add the next
character value to the sum
and then we're done we can return the
sum now if we compile this and we run it
now we're getting more random results
but they're still not as random as I
would like
so let's add a little more randomness by
also multiplying the sum each time by
the character value this just mostly
spreads the values out a little more and
there are a lot of different ways we
could do this I'm just messing around
here it's not like this is the right or
wrong way to do it it's an OK hash
function it's going to work for today if
I had time I'm sure we could play around
with it and come up with an even better
one okay now if we compile it and run it
notice that the results are much more
randomly spread out but now we have
another problem the point of this hash
function is to pick a location in the
table and we only have ten spots in our
table so these numbers are way too big
but we can solve this easily by just
using the modulus operator like I
recently showed you in a recent video
link below in the description and this
just wraps my numbers to ensure that
they land between 0 and the table size
minus 1 now if we compile it and run it
we end up with something a bit more
random but it's consistent and that's
important my function needs to always
produce the same output for the same
input and now we have numbers that are
actually going to fit inside our table
so that's important too and of course we
could change the table size to something
bigger and we would get numbers that are
bigger but they're still fitting inside
the table but for now let's just keep it
small because this is going to
illustrate another issue now a perfect
hash function or an ideal hash function
would always map different inputs to
different locations this function is not
going to do that if we keep adding more
names we're eventually going to get
collisions this is when two names map to
the same location in the table and you
can see that here where Ron and Marin
both map to position zero and Natalie
and Bill both map to position six so
here we have two collisions and we're
going to have to deal with that well
it's not get ahead of ourselves
now let's just shift over and let's make
our hash table it's just going to be an
array of pointers to people's trucks now
why use pointers one reason is space
with pointers I don't need space for the
full table unless I actually fill up the
table I just need space for some
addresses and if your structures small
as they are in this example then this
doesn't make that much difference but if
the structs for people were really big
this would matter a lot more the second
reason I'm using pointers is that it
makes it easy for me to tell when a spot
in the table is empty because I can just
set the pointer to null so a null
pointer means that that's an empty
location there's nothing stored there so
let's do that let's make a function
that's going to set up the table
initially I want all the entries in my
table to be empty so I'll just go
through the table and set each of the
pointers equal to normal we'll call our
an it function down in main just to make
sure we start off with a clean slate and
let's also make a function that prints
out the status of the table so that we
can see what's going on now let's go
through the table and if there's
something in each slot we'll print it
out if not we'll just print out
something that lets us see if it's empty
and then let's print out the table
okay so we'll compile it oops I forgot a
variable and okay compile it and run it
and there's our empty table all ready to
put some people into it okay so now
let's make a function that's going to
insert a person into the table this
function will return a boolean true if
we successfully insert the person to
false if we don't let's make sure we
don't accidentally call this function
with a null pointer then let's compute
the hash function of the person's name
and this is going to be the index or the
location in the table where we are going
to try to put the person then we check
to see if the pointer at that location
in the table is null if the pointer
isn't null then somebody's already there
and this is a collision for now let's
just return false so we're saying here
sorry somebody's already there I can't
add you and we're going to fix that
later but if the spot in the table is
available then we simply set the table
to point to the new person and we return
true because we were successful now
let's see if it works let's make some
people
I'll make Jacob Kate and PO and let's
add them to the hash table and then
print out the status of the table
and what's with me today pages are in
snot strings and compile it and run it
and you can see that they were added and
I'm not liking that I can't easily see
where one printout at my table ends and
the other begins so I'm going to go up
here and print out a start and end
marker just to make things a little
easier to parse visually
okay now that looks better so that's
great but not yet very useful the whole
point of this hash table business is we
want to be able to quickly look up
people in our table so let's make a
lookup function that takes one argument
a name that's what we're looking up by
and it returns null if the person is not
in the table and it returns a pointer to
the person if it is in the table now
once again let's compute our hash on the
name then we're going to look at the
location in the table first we check to
see if it's not an old meaning something
is there and then we use STR and compare
to see if the names match and if they do
then we return the pointer to that
person that means the person we're
looking for is actually in the table
otherwise we're going to return null now
let's try this out first off let's try
to look up a name that is in there we'll
look up and PO because we know that that
is in there and we can print out whether
or not we found her or not next we'll do
the same thing with a name that we know
is not in there and oops I tried to
declare temp twice and if we compile it
and run it notice that it doesn't find
George as we would expect and it does
find an PO just as it should okay now
let's go back and look at our lookup
functions notice that there are no loops
in here I'm not hunting through the
array this is true of our insert
function as well I'm not looking for an
empty slot I'm just using the hash
function to pick the spot for me and so
this is going to be very fast and it's
going to take roughly the same amount of
time no matter how big my table is or
how many people I put in that table now
you remember I was talking earlier about
linear time operations or Big O of n
this is what we call a constant time
operation or Big O of one meaning that
the time it takes for this operation to
run is going to stay constant if I was
keeping people in a linked list or an
array I would have to hunt through this
list and with a longer list I would
spend a lot more time and really that's
the magic of a hash table now for
completeness let's make a delete
function it's actually a lot like insert
except that we want to remove the person
so when we find the location we save
pointer to it and then we remove it from
the table just set it to null and then I
return the pointer that I saved to the
caller
so the caller can free the pointer if it
happened to be allocated on the heap and
in this case it wasn't so there's
nothing to do I can just ignore the
pointer that comes back so just to make
sure it works let's delete and PO and
then check to make sure she's no longer
in there we just want to make sure the
delete is actually working and let's
also print out the table for good
measure and if I compile it and run it
you can see that she's no longer there
okay so we have the basics working
except for one thing we haven't yet
dealt with collisions so let's add a few
more people I'm gonna add Sarah Edna
Marin
Eliza Robert and Jane let's give them
different ages and then let's add them
all to the table
now if I compile it and run it notice
that some of them weren't added we're
missing both Robert and Jane and this is
because the hash function mapped them to
the same location in the table so there
was a collision and so the first one
that got there was inserted and the
others failed and this is a problem
nobody wants a data structure that
occasionally decides not to store your
data especially when there's plenty of
memory and lots of space left in the
table when collisions occur there are
two traditional ways that people handle
this one is called open addressing and
one is called external chaining with
open addressing we're gonna keep
everything in the table if the first
location the hash function gives us is
full we need to look for another and
this can be done by either using the
hash function again to try to find
another location in the table and there
are different ways to do that the
simplest way to solve this is called
linear probing
and with this we start at the hash
location and then if that's taken we
don't actually call the hash function
again we just checked the next location
in the table and then the next and the
next until we find one that's available
or maybe we go through the entire table
and eventually we get back to where we
started and realize that the table is
full and at that point we really can't
add anything so we're just done sorry so
let's do this in our code we need to
update insert so now we actually do need
to add a loop and we're going to start
at our hash location and then we're
going to go until we find an open space
in the table if we go through the entire
array and don't find one then we're out
of luck so return null
now take
make sure this all makes sense
and now I need to add this logic to both
lookup and delete in lookup I'm going to
start at the location the hash function
gave me and then just keep looking to
see if I can find a match
you
and delete we do the same except as
before we delete the person and return a
pointer to the struct now pause a moment
and think about what this code is doing
it's using my hash function but this
searching has made things rather
inefficient especially when the thing
we're looking for isn't there in that
case we're always going to go through
the entire table if the table is large
then these operations that used to be
fast are now quite slow so let's make
one improvement and instead of setting
deleted nodes back to null we're just
going to use a value like null that I
know will never be a valid address and
so any pointer that I see that has this
value I know it's been deleted and this
allows me to determine when I can stop
hunting so if I find a deleted node I
have to keep looking but if I find one
that's null then I can stop because I
know the node I'm looking for can't be
beyond that point
okay so let's update our insert logic
now if we find a pointer that is null or
deleted we use it and look up we want to
bail if we find a null pointer if we
find a deleted node just continue on to
the next iteration and if it's not null
or deleted we check to see if the names
match just like we did before and then
we do the same thing and delete return
if the note is null keep going if it's
deleted and then delete it otherwise
if I can pilot no we get warnings
because okay what did I do I cast it to
the wrong type sorry about that and now
if we compile it fine and we run it and
we get a segfault
Peke what did i do because i forgot to
update my print table function okay and
is trying to dereference one of these
deleted node pointers which of course
isn't ending well so let's just adjust
the printing code to check to see if
it's been deleted and now we compile it
and we can run it and notice now that we
were able to add all of our people and
we can also see where the one person was
that I deleted so what's nice about this
approach with open addressing the table
is always the same size once it's full
it's full that can be a good thing or a
bad thing depending on how you want your
system to fail but if you're in a
scenario where you have hard limits on
how much memory you can use then this
can be a good thing what I don't like
about it is that as your table fills up
all of those claims that I made about
hash tables getting really fast they all
disappear because as the table fills up
we're gonna do more and more hunting and
so our table is gonna get quite slow and
eventually if I do a lot of insertions
and a lot of deletions over time
eventually all of my empty spots are all
going to be marked as deleted and so
that little optimization that I did by
marking them as deleted isn't actually
gonna benefit me much anyway and so once
again performance could get really
terrible now I could also add some code
that would go through and try to clean
up those deleted markers when they're no
longer needed but that's a pain and I'm
definitely not gonna do that in this
video I'll leave that to you if you want
an exercise have at all so if my hash
function isn't very random then linear
probing can also produce big clusters of
objects so even if the table is not full
you can have problems where your
performance still gets really bad so in
response to this there are other options
there's things like quadratic probing
and double hashing that people use to
avoid clustering and they come up with
their own issues and complications but
for now I'm going to leave it to you to
explore these options if you need them
because I want to talk about the other
alternative to open addressing and that
is external chaining this is the one
that I find myself using most often
especially when I'm worried about
performance and I'm on a machine like my
laptop that has a lot of memory with
external chaining you're always going to
put the objects into the table location
that was chosen by the nation' always we
don't go looking for another place when
that collision occurs we simply just
chain them up so basically each location
in the table will be
the head of a linked list so again if
you aren't familiar with linked lists
you can watch my videos but yes each
location becomes its own linked list and
when we get a collision we simply add
the person we want to insert onto the
appropriate list so let's make this
happen in our code for this I'm going to
make a separate file so we can leave the
open addressing one as is you can you
can get that if you want because we're
using linked lists I want to change our
struct a bit really just to give it a
next pointer and we don't need to leash
and markers anymore and we don't need to
hunt for open spots anymore so here in
insert we simply get the index from our
hash function and then we add the person
to the front of the list which is a lot
simpler now down in lookup we don't have
to look through the table anymore but we
may have to look through the list if
there have been collisions so so here
I'm going to get a temporary pointer to
the head of the list at the location we
got from the hash function and then
we're going to go through the nodes as
long as temp is not null this is pretty
much just how you go through a linked
list and the names don't match
so which again this codes a lot simpler
than we had before not surprisingly
delete is still a lot like lookup the
only real differences relate to deleting
from the linked list we need another
pointer previous which will point to the
previous node in the list as temp goes
through and of course we could use a
doubly linked list to simplify this a
little bit but that means more pointers
and anyway I'll leave that as an
exercise to you if you want to do it now
once the loop is done if temp is null
then we didn't find a match so there's
nothing to do if the previous pointer is
null then we know that the matched node
was the front of the list
otherwise it was somewhere in the middle
or at the end of the list so we handle
those cases appropriately
and then in our print table function we
need to get rid of the deleted stuff and
add a loop that goes through each chain
and prints it out and if I compile now
you can see that everything made it into
the table and where we had collisions we
now have chained person struts so we can
basically just have more people at each
location in the table okay so this style
of hash table is usually a bit faster
and I think it's a bit more convenient
it keeps the code simpler if the table
ends up being too small and if I have a
bad hash function that produces a lot of
collisions things can still be slow
because those chains are going to get
long and lookup start to resemble
searches through a linked list which is
linear again so it's important to have a
good hash function and keep your table
appropriately sized but if you do
overfill your table it can keep growing
these chains just they can keep growing
until your operating system eventually
tells you you don't get to have any more
memory and that may be really nice it
really just depends on the situation you
find yourself in but all things being
equal I usually go with external
chaining because it keeps things simpler
and that's where I'm gonna end today
folks there's a lot more that we could
say about hash tables but now at least
you know what they are why they're
useful and you know how to implement
them please comment if you have
questions please let me know if there's
other things about hash tables you'd
like to see me address in a future video
like if you'd like to see a hash table
example in another language I'll see
what I can do but in the meantime happy
coding and I'll see you later
[Music]