This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.
Hash Table Context
Loading...
En provenance du cours de Princeton University
Algorithms, Part I
3697 notes
À partir de la leçon
Hash Tables
We begin by describing the desirable properties of hash function and how to implement them in Java, including a fundamental tenet known as the uniform hashing assumption that underlies the potential success of a hashing application. Then, we consider two strategies for implementing hash tables—separate chaining and linear probing. Both strategies yield constant-time performance for search and insert under the uniform hashing assumption.
Rencontrer les enseignants
Kevin WayneSenior Lecturer
Computer Science
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
So let's just look at a little bit of the context of hashing in practical
applications. As I mentioned, it's very widely used. So here's an, here's an
example right from Java. The first. Implementation of Java 1.1. The designers
found that the cost of computing the hash function for strings seemed to be
excessive, particularly for long strings. And that was one of the main uses of
hashing, was just to be able to do searching with string keys. And so what
they decided in the first implementation was let's just look at every eighth or
ninth character, and that way, we don't have to spend a lot of time computing the
hash function. So they had a hash function pretty much like the one that we use.
Except that it compute a skip that would mean that, that only look at about every
eight key and they wouldn't have to do quite so much work performing the hash
function. And that's diffidently one thing to consider when using hashing is that the
cost of computing the hash function for a complicated key might exceed the cost of
searching and using a simpler structure like a binary search tree. And anyway for
Java 1.1 what happened was that there was a huge potentail for really bad collision
patterns on typical data. So here's the example of typical data, which is a URL.
All of these keys, which are totally different, would wind up having the same
collision. And so client programs and system programs on the Java system were
having terrible performance on their symbol table because of the shortcut in
hashing. So this well illustrates that you need to use all of the data in the hash
function and sometime we do a closer analysis. The cost of computing the hash
function can mean that something like red black trees will even outperform hashing
even for just searching and insert. So there is another thing about the uniform
hashing assumption is that it is an assumption and if you are writing code
where we have to have guaranteed performance like when your aircraft is
landing or you are controlling a nuclear reactor or somebody's pa cemaker. That, if
that assumption doesn't hold and you get bad performance you're going to have
disastrous consequences. So that's another reason to think about maybe paying a
little extra and using to guarantee that you get with red black search trees.
Instead of hashing. And there's another surprising situation that happens in
today's world. For example Java publishes its hash function. And so if you're trying
to provide a service over the web. An adversary can learn your hash function and
just send you data that causes huge performance problem by just making all
that data hash to one particular item. And that's definitely something to worry
about. And, and in the real world you can nowadays find on the web particular
sequences of keys that will cause particular services to crash. And again,
that's a little harder to do with something like a red black tree where we
have performance guarantees. When you make an assumption you better be sure and
you're depending on that assumption, you better be sure that it holds somehow. This
is different than for example for quick sort when we, our assumption was we're
going to create randomness and we are going to depend on that randomness. In
this care we're kind of hoping for randomness and maybe that doesn't really
always hold. So that's certainly something to be aware of when using hashing in
practice. So here's just simple example on hashing in java. So what we can do is it's
pretty easy to find a family of strings that have the same hash code for example
with just a little fooling around now days you can just look it up on the web, you
can see that these two character keys, both have the same hash code because when
you just do the math in a base 31 hash code it'll tell you that answer. Well what
that means is that actually, just like working in binary you got, you can combine
those things. In all possible ways, and you can get two to the N strings, for any
N of length to N that all hash to the same value. And somebody's implemented a
service in Java that it uses a simp le table that takes string keys, you can
cause that to crash in this way. Little bit scary for some systems designers. At
least reason for pause in using hashing. Now, hashing also has a extremely
important application in today's Internet commerce. And so the, it's the concept of
so called one way hash functions which mean that we, we, use it for secure to try
to be, have some secure fingerprints for use on the web. And there's been a lot
research done to develop functions that take keys as input, and then produce
values that look random. In such a way that, it's hard for someone else to find
another key that collides with that. This technology is, is useful for storing
passwords and digital fingerprints and things. But it's too expensive for use, in
a symbol table. So the bottom line is separate chaining versus linear probin
collision resolution message methods. Now there's a number of considerations to take
into account. Separate chaining is really easy to implement both insert and delete
it performs, it degrades, it does so gracefully and the clustering is, is maybe
less of a problem if you have a bad hash function. Linear probing tends to make
better use of space. And also it'll perform better for huge tables whereas
caching is involved. And if, in the classic algorithm or computer science
problems for people to think about is what do we do to delete in these two situations
and exactly how do we resize. Those are all at the level of exercises in the
context of the kinds of algorithms that we've seen. And as I mentioned, there's
been many, many improved versions of hashing that have been studied. I
mentioned the two probe, or double hashing version. Another way to use two hash
functions is just to hash the two positions and put the key in the shorter
of the two chains. In, in that case, then the expected length of the longest chain
will be lg, lg N which is quite an improvement. You get constant time
expected and lg, lg N worst case. Double hashing is the variant of layer probing
where you just skip a variable amount, not one each time. And that pretty much wipes
out clustering but it, it is more difficult to implement delete for that
one. In a new method called, relatively new method called Cuckoo Hashing. It's
another variant of linear probing where we hash a key to two positions and insert the
key in either one. If occupied you, you reinsert the displaced key into its
alternative. It was in one, each one can go to two. And that one actually gives
constant worst case time for search. That's another variation on the team. And
all of these things allow us to make better use of memory, allows the table to
become nearly full. It would have been very exciting. Thing to be researchers in
the 1950's who cared so much about memory and nowadays a little extra memory is not
something that people care about so much and most people just go with the easy
algorithm except for really performance critical applications. What about hash
tables versus balance search trees? Well hash tables are really simple to code
usually if you don't have to do the hash function. And if you don't have order in
the keys at all then you need the compare to, to implement balance search trees. So
you have to use hashing if you don't have the comparison. And it'll probably be
faster for simple keys to use hashing. It's a few arithmetic operations to do the
hash versus lg N and compares for the balance tree. And there's some better
system support in Java for strings that cache hash code means that you don't even
have to compute the hash if your, your simple table for strings is in an inner
loop. On the other hand, balanced search trees have a much stronger performance
guarantee. It, you don't have to assume anything. It's going to be less than lg N
and compares and it's got support for all those ordered ST operations, and compared
to and is pretty easy and natural function to implement. So it's more flexible and
more broadly useful. And actually the Java system and other systems include both so
that programmers can make use of either one in diff erent situations. That's our
context for hashing algorithms.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
