system
Given the following post, respond as if you're commenting on Reddit:
human
What exactly are hash tables?

I’ve recently watched a couple videos of live programming interviews and in almost every one hash tables get brought up. Sorry if this is a really basic question but I can only get convoluted answers from googling hash tables. If someone could ELI5 hash tables it’d be much appreciated!
gpt
Imagine you have a mapping of usernames to user information like this:

* johndoe1 → (name: "John", email: "johndoe@example.com")
* alice → (name: "Alice", email: "alice@example.com")
* etc.

You want to be able to do a *lookup* of a particular user using their username. The username, being unique for every user, is called a *key*.

If you were to store this information naively, as an array for example, then a lookup would require you to go through the list one-by-one and compare the username to the the requested username for each entry. So in the worst case (if it's the last one) you'll need to go through the entire list until you hit the user you're looking for.

A hash table is a data structure that allow you to do lookups much more quickly. You create an array of a certain predetermined size (let's say 256). And then you "hash" the username to some index between 0-255. So "johndoe1" might hash to 132, "alice" to 42, etc. And you store the user information at the corresponding location in the array. There are many possible hash functions, a good hash function will be as random as possible but will always hash each input to a fixed hash.

Now, if you want to do a lookup of "alice", you just hash that username to get 42, and then you go straight to the corresponding array index: `users[42]` is your user entry.

A problem here is, since there's only 256 possible "slots", what do you do if you get clashes (for example if there are more than 256 users there must be at least one clash). This is called a hash collision, and there are multiple ways to solve it. Most commonly you will just gather all the users with the same hash in a list, and then go through that list the "naive" way.