Hashing

Overview

Recall questions on hash functions and why hashing is not encryption, collisions, hash tables and collision handling, storing passwords as salted hashes, checksums for downloads, and hashing a message before signing it.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a hash function?

   Model answer

   A hash function is an algorithm that takes an input of any size and produces an output, called the hash or digest, of a fixed size. The same input always produces the same output, but the process is one way: there is no practical way to work backwards from the hash to recover the original input.

2. 2

   Explain why hashing is not a form of encryption.

   Model answer

   Encryption is reversible by design: it exists so that the holder of the correct key can decrypt the ciphertext and recover the original data exactly. Hashing is deliberately one way and has no key that reverses it; the output is a fixed size regardless of input size, so information is lost and the original cannot be reconstructed from the digest. Hashing is used to check or index data, not to hide data that must later be read back.

3. 3

   What properties make a hash function a good one?

   Model answer

   It should be quick to compute; it should be deterministic, always giving the same output for the same input; it should distribute outputs evenly across the available range so that values do not cluster; it should therefore produce as few collisions as possible; and for security uses it should be infeasible to reverse and should produce a wildly different digest for even a tiny change in the input.

4. 4

   What is a collision?

   Model answer

   A collision occurs when two different inputs produce the same hash value. Collisions are unavoidable in principle because there are more possible inputs than there are possible fixed-size outputs, so a good hash function aims to make them rare and hard to engineer rather than impossible.

5. 5

   How is a hash table used to store and retrieve data?

   Model answer

   The key of each item is passed through a hash function, which produces an index into an array of buckets, and the item is stored at that index. To retrieve an item the same key is hashed again, giving the same index directly, so the item is found without searching through the other entries.

6. 6

   A student writes that lookup in a hash table is O(1). Under what conditions is that true, and when does it break down?

   Model answer

   It is O(1) on average, when the table is not too full and the hash function spreads keys evenly, so most buckets hold at most one item and the index calculation leads straight to it. It breaks down when collisions become common, for instance when the load factor gets high or the hash function distributes poorly: many items then share buckets and must be searched through, and in the worst case, where every key hashes to the same bucket, lookup degrades to O(n).

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.