Let's begin by building up some intuition about what we would want from a hash
function, now that we know how hash functions are usually implemented. So
let's start with a hash function which is implemented by chaining. So what's going
to be the running time of our lookup, insert, and delete operations in a hash
table with chaining? Well, the happy operation in a hash table with chaining is
insertion. Insertion, we can just say without any qualifications, is constant
time. This requires the sort of obvious optimization that when you do insert, you
insert something at the front of the list in its bucket. Like, there's no reason to
insert at the end. That would be silly. So the plot thickens when we think about the
other two operations, deletion and the lookup. So let's just think about lookup.
Deletion's basically the same. So how do we implement lookup? Well, remember when
we get some key x, we invoke the hash function. We call h(x). That tells us
what bucket to look in. So if it tells us 17, we know that, you know, x may
or may not be in the hash table. But at this point we know that if it's in the
hash table, it's got to be in the linked list that's in the seventeenth bucket. So
now we descend into this bucket. We find ourselves a linked list. And now, we have
to resort to just an exhaustive search through this list in the seventeenth
bucket, to see whether or not X is there. So we know how long it takes to search a
regular list for some element. It's just linear and the list length. And now we're
starting to see why the hash function might matter. Right, so suppose we insert
100 objects into a hash table with 100 buckets. If we have a super lucky hash
function, then perhaps each bucket will get its own object. There'll be one object
in each of the lists, in each of the buckets, so. Theta of the list length
is just theta of one. We're doing great. Okay? So, a constant, constant link to lists,
means constant time insert delete. A really stupid hash function would map
every single object to bucket number zero. Okay, so then if you insert 100
objects, they're all in bucket number zero. The other 99 buckets are empty. And
so every time you do insert or delete, it's just resorting to the naive linked list
solution. And the running time is going to be linear and the number of
objects in the hash table. So the largest list length could vary anywhere from m/n,
where m is the number of objects, this is when you have equal linked lists,
to if you use this ridiculous constant hash function, m, all the objects in the
same list. And so the main point I'm trying to make here, is that you know,
first of all, at least with chaining, where the running time is governed by the
list length, the running time depends crucially on the hash function. How well
the hash function distributes the data across the different buckets. And
something analogous is true for hash tables that use open addressing. Alright
so here there aren't any lists. So you don't, there's no linked lists to keep
track of. So the running time is going to be governed by the length of the probe
sequence. So the question is how many times do you have to look at different
buckets in the hash table before you either find the thing you're looking for,
or if you're doing insertion, before you find an empty bucket in which to insert
this new object. So the performance is governed by the length of the probe
sequence. And again, the probe sequence is going to depend on the hash function. For
really good hash functions in some sense, stuff that spreads data out evenly, you
expect probe sequences to be not too bad. At least intuitive, And for say the
constant function you are going to expect these probe sequences to grow linearly
with the numbers of object you insert into the table. So again this point remains
true, the performance of a hash table in either implementation really depends on
what hash function you use. So, having built up this intuition, we can now say
what it is what we want from a hash function. So first we want it to lead to
good performance. I'm using the chaining implementations as a guiding example. We
see that if we have a size of a hash table, n, that's comparable to the number
of objects, m, it would be really cool if all of the lists had a length that was
basically constant; therefore we had our constant time operations. So equal length
lists is way better than unequal length lists in a hash table with chaining. So
we, we want the hash function to do is to spread the data out as equally as possible
amongst the different buckets. And something similar is true with open
addressing; in some sense you want hash functions to spread the data uniformly
across the possible places you might probe, as much as possible. And in
hashing, usually the gold standard for spreading data out is the performance of a
completely random function. So you can imagine for each object that shows up you
flip some coins. With each of the n buckets equally likely, you put this
object in one of the n buckets. And you flip independent coins for every different
object. So this, you would expect, you know, because you're just throwing darts
at the buckets independently, you'd expect this to spread the data out quite well.
But, of course, it's not good enough just to spread data out. It's also important
that we don't have to work too hard to remember what our hash function is and to
evaluate it. Remember, every time we do any of these operations, an insert or a
delete or a lookup, we're going to be applying our hash function to some key x.
So every operation includes a hash function evaluation. So if we want our
operations to run a constant time, evaluating the hash function also better
run in constant time. And this second property is why we can't actually
implement completely random hashing. So there's no way we can actually adjust when
say we wanted to insert Alice's phone number, flip a new batch of random coins.
Suppose we did. Suppose we flipped some random coins and it tells us to put
Alice's phone number into the 39th bucket, while. Later on, we might do a
lookup for Alice's phone number, and we better remember the fact that we're
supposed to look in the 39th bucket for Alice's phone number. But what does that
mean? That means we have to explicitly remember what choice we made. We have to
write down. You get a list of effects that Alice is in bucket number 39. In every
single insertion, if they're all from in the point of coin flips, you have to
remember all of the different random choices independently. And this really
just devolves back to the naive list base solution that we discussed before. So,
evaluating the hash function is gonna take us linear time and that defeats the
purpose of a hash table. So we again we want the best of both worlds. We want a
hash function which we can store in ideally constant space, evaluate in
constant time, but it should spread the data out just as well as if we had this
gold standard of completely random hashing. So I want to touch briefly on the
topic of how you might design hash functions. And in particular good hash
functions that have the two properties we identified on the previous slide. But I
have to warn you, if you ask ten different, you know, serious hardcore
programmers, you know, about their approach to designing hash functions,
you're likely to get ten somewhat different answers. So the design of hash
functions is a tricky topic, and, it's as much art as science at this point. Despite
the fact that there's a ton of science, there's actually a very beautiful theory,
about what makes good hash functions. We'll touch on a little bit of that in a, in a
different optional video. And if you only remember one thing of, you know, from this
video or from these next couple slides, the thing to remember is the following.
Remember that it's really easy to inadvertently design bad hash functions
and bad hash functions lead to poor hash table performance. Much poorer than you
would expect given the other discussion we've had in this video. So if you have to
design your own hash function, do your homework, get some examples, learn what
other experts are doing and use your best judgment. If you do just something without
thinking about it, it's quite possible to lead to quite poor performance, much
poorer than you were expecting. So to drive home this point, suppose that you're
thinking about keys being phone numbers. So let's say, you know, I'm gonna just be
very kinda United States centric here. I'm just gonna focus on the, the ten digit
phone numbers inside the US. So the universe size here is ten to the ten,
which is quite big. That's probably not something you really want to implement
explicitly and let's consider an application where, you know, you're only
say, keeping track of at most, you know, 100 or 1,000 phone numbers or something
like that. So we need to choose a number of buckets, let's say we choose 1,000
buckets. Let's say we're expecting no more than 500 phone numbers or so. So we double
that, we get a number of buckets to be equal 1,000. And now I got to come up with
a hash function. And remember, you know, a hash functions by definition. All it does
is map anything in the universe to a bucket number. So that means it has to
take as input a ten digit phone number and spit as output some number between zero
and 999. And, beyond that we have flexibility of how to define this mapping.
Now, when you are dealing with things that have all these digits it's very tempting
to just project on to a subset of the digits. And, if you want a really terrible
hash function, just use the most significant digits of a phone number to
define a mapping from phone numbers to buckets. Alright, so I hope it's clear why
this is a terrible choice of a hash function. Alright, so maybe you're a
company based in the San Francisco Bay area. The area code for San Francisco is
415. So if you're storing phone numbers from customers in your area. You know
maybe twenty, 30, 40 percent of them are gonna have area codes 415. All of those
are going to hash to exactly the same bucket, bucket number 415 in this hash
table. So you're gonna get an overwhelming percentage of the data mapping just to
this one bucket. Meanwhile you know not all 1000 possibilities of, of these three
digits are even legitimate area codes. Not all three digit numbers are area codes in
the United States. So there'll be buckets of your hash table which are totally
guaranteed to be empty. So you waste a ton of space in your hash table, you have a
huge list in the bucket corresponding to 415, you have a huge list in the
bucket corresponding to 650, the area code at Stanford. You're gonna have a very slow
look up time for everything that hashes to those two buckets and there's gonna be a
lot of stuff that hashes to those two buckets, So terrible idea. So a better but
still mediocre hash function would be to do the same trick but using the last three
digits instead of the first three digits. This is better than our terrible hash
function because there aren't ridiculous clumps of phone numbers that have exactly
the same last three digits. But still, this is sort of assuming you're using this
hash function as tantamount to thinking that the last three digits of phone
numbers are uniformly distributed among all of the 1,000 possibilities. And really
there's no evidence if that's true. Okay? And so there's going to be patterns and
phone numbers that are maybe a little subtle to see with the naked eye, but
which will be exposed if you try to use a mediocre hash function like this. So let's
look at another example. Perhaps you are keeping track of objects just based by
where they are laid out in memory. So in other words the key for an object is just
gonna be its memory location and if these things are in bytes, then you are
guaranteed that every memory location will be a multiple of four. So for a second
example let's think about a universe where the possible keys are the possible memory
locations, So here you're just associating objects with where they're laid in memory,
and a hash function is responsible for taking in as input some memory location of
some object and spitting out some bucket number. Now generally, because of, you
know the structure of bytes and so on, our memory locations are going to be multiples
of some power of two. In particular, memory locations are going to be even, And
so a bad choice of a hash function. Would be to take, remember, the hash function
takes the input of the memory location, which is, you know, some possibly really
big number, and we wanna compress it, we want to output a bucket number. Now let's
think of a hash table where we choose N equals 10^3, or 1000 buckets.
So then the question is, you know, how is this hash function going to take this big
number, which is the memory location, and squeeze it down to a small number. Which
is one of the buckets and so let's just use the same idea as in the mediocre hash
function, which is we're gonna look at the least significant bits so we can express
that using the mod operator. So let's just think about we pick the hash function h(x)
where h is the memory location to be x mod 1000 There again, you know, the
meaning of 1,000 is that's the number of buckets we've chosen to put in our hash
table because, you know, we're gonna remember roughly at most 500 different
objects. So don't forget what the mod operation means, this means you just,
essentially subtract multiples of 1,000 until you get down to a number less than
1,000. So in this case, it means if you write out x base ten, then you just take
the last three digits. So in that sense, this is the same hash function as our
mediocre hash function when we were talking about phone numbers. So we
discussed how the keys here are all going to be memory locations; in particular
they'll be even numbers. And here we're taking their modulus with respect to an
even number. And what does that mean? That means every single output of this hash
function will itself be an even number. Right, you take an even number, you
subtract a bunch of multiples of a 1000, you're still going to have an even number.
So this hash function is incapable of outputting an odd number. So what does
that mean? That means at least half of the locations in the hash table will be
completely empty, guaranteed, no matter what the keys you're hashing is. And
that's ridiculous. It's ridiculous to have this hash table 50 percent of which is
guaranteed to be empty. And again, what I want you to remember, hopefully long after
this class is completed is not so much these specific examples, but more the
general point that I'm making. Which is, it's really easy to design bad hash
functions. And bad hash functions lead to hash table performance much poorer than
what you're probably counting on. Now that we're equipped with examples of bad hash
functions. It's natural to ask about, you know, what are some good hash functions?
Well it's actually quite tricky to answer that question. What are the good hash
functions, and I'm not really going to answer that on this slide. I don't promise
about hash functions that I'm going to tell you about right now, are good in a
very strong sense of the word. I will say these are not obliviously bad hash
functions, they're let's say, somewhat better hash functions. And in particular
if you just need a hash function, and you need a quick and dirty one, you don't want
to spend too much time on it. The method that I'm going to talk about on this slide
is a common way of doing it. On the other hand, if you're designing a hash function
for some really mission-critical code, you should learn more than what I'm gonna tell
you about on this slide. So you, you should do more research about what are the
best hash functions, what's the state of the art, if you have a super important
hash function. But if you just need a quick one what's, what we say on this
slide will do in many, in most situations. So the design of a hash function can be
thought of as two separate parts. So remember by definition a hash function
takes as input something from the universe. An IP address, a name, whatever
and spits out a bucket number. But, it can be useful to factor that into two separate
parts. So first you take an object which is not intrinsically numeric. So,
something like s string or something more abstract. And you somehow turn an object
into a number, possibly a very big number. And then you take a possibly big number and you map it to a much smaller number,
namely the index of a bucket. So in some cases I've seen these two steps given the
names like the first step is formulating the hash code For an object, and then the
second step is applying a compression function. In some cases, you can skip the
first step. So, for example, if your keys are social security numbers, they're
already integers. If they're phone number, they're already integers. Of course, there
are applications where the objects are not numeric. You know, for example, maybe
they're strings, maybe you're remembering names. And so then, the production of this
hash code basically boils down to writing a subroutine that takes, as input, a
string, and outputs some possibly very big number. There are standard methods for
doing that, it's easy to find resources to, to give you example code for
converting strings to integers you know, I'll just say one or two sentences about
it. So you know each character in a string it is easy to regard as a number in
various ways. Either you know just say it is ASCII, well ASCII code then you just
have to aggregate all of the different numbers, one number per character into
some overall number and so one thing you can do is you can iterate over the
characters one at a time. You can keep a running sum. And with each character, you
can multiply the running sum by some constant, and then add the new letter to
it, and then, if you need to, take a module list to prevent overflow. And the
point of me giving you this one to two sentence of the subroutine is just to give
you a flavor of what they're like, and to make sure th at you're just not scared of
it at all. Okay? So it's very simple programs you can write for doing things
like converting from strings to integers. But again, you know, I do encourage you to
look it up on the Web or in a programming textbook, to actually look at those
examples. Okay? But there are standard methods for doing it. So that leaves the
quest, question of how to design this compression function. So you take as input
this huge integer. Maybe your keys are already numeric, like Social Security
numbers or IP addresses. Or maybe you've already some subroutine to convert a
string, like your friend's name, into. Some big number, but the point is you have
a number in the millions or the billions, and you need to somehow take that and
output one of these buckets. And again think of there being maybe a thousand or
so buckets. So the easiest way to do that is something we already saw in a previous
slide, which is just to take the modulus, With respect to the number of buckets. Now
certainly one positive thing you can say about this compression function is its
super simple, Both in the sense that it's simple to code and in the sense that it's
simple to evaluate. Now remember that was our second goal for a hash function. It
should be simple to store, it is actually nothing to store. And it should be quick
to evaluate. And this certainly fits the bill. Now the problem is, remember the
first. Property of a hash function that we wanted is that it should spread the data
out equally. And what we saw in the previous slide is that at least if you
choose the number of buckets N poorly, then you can fail to have the first
property. And in that respect you can fail to be a good hash function. So if for
example if N is even and all of your objects are even, then it's a disaster,
all of the odd buckets go completely empty. And honestly, you know, this is a
pretty simplistic method. Like I said, this is a quick and dirty hash function.
So, no matter how you choose the number of buckets N, it's not gonna be a perfect
hash function in any sense of the word. That said, there are some rules of thumb
for how to pick the number of buckets, how to pick this modulus, so that you don't
get the problems that we saw on the previous slide. So, I'll conclude this
video just with some standard rules of thumb. You know, if you just need a quick
and dirty hash function, you're gonna use the, the modulus compression function, how
do you choose N? Well, the first thing is we definitely don't want to have the
problem we had in the last slide, where we're guaranteed to have these empty
buckets no matter what the data is. So what went wrong in the previous slide?
Well. The problem is that all of the data elements were divisible by two. And the
hash function modulus, the number of buckets, was also divisible by two. So
because they shared a common factor, namely two, that guaranteed that all of
the odd buckets remained empty. And this is a problem, more generally, if the data
shares any common factors with N, the number of buckets. So, in other words, if
all of your data elements are multiples of three, and the number of buckets is also a
multiple of three, you got a big problem. Then everything's gonna hash into bucket
numbers which are multiples of three, too, that's if your hash table will go
unfilled. So the upshot is, you really want the number of buckets to not share
any factors With the data that you're hashing. So, how do you reduce the number
of common factors? Well, you just make sure the number of buckets has very few
factors, which means you should choose N to be a prime number, 'kay? A number that
has no nontrivial factors, And let me remind you, the number of buckets should
also be comparable to the size of the set that you're planning on storing. Again, at
no point did we need "N" to be, you know, very closely connected to the number of
elements that you're storing just within, say some small constant factor. And you
can always find a prime within a small constant factor of a target number of
elements to store. If the number of buckets in your hash table isn't too big,
if it's just in say the thousands or maybe the tens of thousands, then, you know, you
can just look up a list of all known primes up to some point, and you can just
sort of pick out a prime which is about the magnitude that you're looking for. If
you're gonna use a really huge number of buckets in the millions or more, then
there are algorithms you can use for primarily testing which will help you find
a prime in about the range that you're looking for. >> So that's the first order
rule of thumb you should remember if you're using the modulus compression
function, which is set the number of buckets equal to a prime. So you're
guaranteed to not have non-trivial common factors of the modulus shared by all of
your data. So there's also a couple of second order optimizations, which people
often mention. And you also don't want the prime; you want the prime to be not too
close to patterns in your data. So what does that mean, Patterns in your data?
Well, in the phone number example we saw that patterns emerged in the data when we
expressed it base ten. So for example, there is crazy amounts of Lumping in the
first three digits when we expressed a phone number-based ten, Because that
corresponded with the area code. And then, with. Memory locations when we express,
express it base two, there are crazy correlations in the low orbits. And these
are the two most common examples. Either there's some digit, to the base ten
representation or digits in the base two representation where you have, you know,
patterns that is non-uniformity. So that. Suggests that the prime, that, N that you
choose, you know, all else being equal, shouldn't be too close to a power of two,
and shouldn't be too close to a power of ten. The thinking being that, that will
spread more evenly data sets that do have these patterns in terms of base two
representation, or base ten representations. So in closing, this is a
recipe I recommend for coding of hash functions if what you're looking to do is
sort of minimize program ming, programmer time, subject to not coming up with a hash
function, which is completely broken. But I want to reiterate, this is not the state
of the art in hash function design. There are hash functions which are in some sense
better than the ones that expand on this slide. If you're responsible for some
really mission critical code that involves a hash function, you should really study
more deeply than we've been able to do here. We'll touch on some issues in, of
the different optional video, but really you should do additional homework. You
should find out about the state-of-the-art about hash function design. You should
also look into implementations of open addressing in those probing strategies.
And above all you really should consider cold, coding up multiple prototypes and
seeing which one works the best. There's no silver bullet, there's no panacea in
the design of hash tables. I've given you some high-level guidance about the
different approaches. But ultimately it's gonna be up to you to find the optimal
implementation for your own application.