75
Hash tables
Your buddy Maggie can give you the price in O(1) time for any item, no
matter how big the book is. She’s even faster than binary search.
What a wonderful person! How do you get a “Maggie”?
Let’s put on our data structure hats. You know two data structures so
far: arrays and lists (I won’t talk about stacks because you can’t really
“search” for something in a stack). You could
implement this book as
an array.
Each item in the array is really two items: one is the name of a kind of
produce, and the other is the price. If you sort this array by name, you
can run binary search on it to find the price of an item.
So you can find
items in O(log
n
) time. But you want to find items in O(1) time. That is,
you want to make a “Maggie.” That’s where hash functions come in.
76
Chapter 5
I
Hash tables
Hash functions
A hash function is a function where you put in a string
1
and you get
back a number.
In
technical terminology, we’d say that a hash function “maps strings
to numbers.” You might think there’s no discernable pattern to what
number you get out when you put a string in. But there are some
requirements for a hash function:
• It needs to be consistent. For example, suppose you put in “apple” and
get back “4”. Every time you put in “apple”, you should get “4” back.
Without this, your hash table won’t work.
• It should map different words to different numbers. For example, a
hash function is no good if it always returns “1”
for any word you put
in. In the best case, every different word should map to a different
number.
So a hash function maps strings to numbers. What is that good for?
Well, you can use it to make your “Maggie”!
Start with an empty array:
You’ll store all of your prices in this array. Let’s add the price of an apple.
Feed “apple” into the hash function.
Dostları ilə paylaş: