Interview Cake
A hash function takes data (like a string, or a file’s contents) and outputs a hash, a fixed-size string or number.
For example, here’s the MD5 hash (MD5 is a common hash function) for a file simply containing “cake”:
And here’s the hash for the same file after it was edited to be “cakes”:
Notice the hash is completely different, even though the files were similar. Here's the hash for a long film I have on my hard drive:
The hash is the same length as my other hashes, but this time it represents a much bigger file—461Mb.
We can think of a hash as a "fingerprint." We can trust that a given file will always have the same hash, but we can't go from the hash back to the original file. Sometimes we have to worry about multiple files having the same hash value, which is called a hash collision.
Some uses for hashing:
- Dictionaries. Suppose we want a list-like data structure with constant-time lookups, but we want to look up values based on arbitrary "keys," not just sequential "indices." We could allocate a list, and use a hash function to translate keys into list indices. That's the basic idea behind a dictionary!
- Preventing man-in-the-middle attacks. Ever notice those things that say "hash" or "md5" or "sha1" on download sites? The site is telling you, "We hashed this file on our end and got this result. When you finish the download, try hashing the file and confirming you get the same result. If not, your internet service provider or someone else might have injected malware or tracking software into your download!"
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
