Construct a hash from scratch and adapt it for tables, sharding and security

In a technical product manager interview, you are asked to design a hash function. Explain what a good hash function has to achieve, propose one concretely enough to walk through how it turns an input into an output, and describe how the design would change depending on what the hash is used for. ```hint Let the job set the requirements A hash used to find keys in an in-memory table, one used to spread data across servers, and one used to protect passwords are judged by very different standards. Settle the use first, then choose operations that serve it. ``` ### Clarifying Questions - What is the hash for: finding keys in an in-memory table, spreading records or traffic across servers, detecting duplicate or changed data, or a security purpose such as storing passwords? - What do the inputs look like: short strings such as account IDs or phone numbers, or arbitrary binary data of any length? - How many output bits are needed, and must the output stay the same across machines, programming languages and software versions? - Could an attacker choose the inputs the system hashes? ### What a Strong Answer Covers - The properties a good hash needs (deterministic, fast, evenly spread, sensitive to small input changes) and which matter most for the stated use - A concrete construction worked through on a small input, including how the output becomes a bucket or server choice - Collisions: why they cannot be avoided, how likely they are for a given output size and number of keys, and how the system copes with them - When to rely on a vetted cryptographic or keyed function instead of a homemade one, including adversarial inputs and password storage - How the design would be tested and maintained: distribution, sensitivity to small changes, speed, and changing the function safely later ### Follow-up Questions - You hash customer IDs to pick one of several database servers and then add one more server. What goes wrong, and how would you fix it? - An attacker sends many keys that all land in the same bucket of your hash table. What happens to the service, and how do you defend against it? - How would you explain to a non-technical stakeholder why two different inputs can share a hash value, and when that matters?