Hash tables allow O₍₁₎ time when doing searches.

A hash function is a function where the input is a string and the output is a number. It “maps strings to numbers”.

A hash function has the requirements below: . Consistency (given an input value, it must always return the same output) . Map different words to different numbers (in the best case, every different word should map to a different number)

A hash function tells exactly where a value is stored, so a search is not needed. What allows that are the following statements: . A hash function must map a name to the same index . A hash function maps different strings to different indexes . A hash function knows the array’s length and only returns valid indexes.

A hash table is composed by a hash function and an array. It is a data structure that has extra logic behind it.

Arrays and lists map straight to memory, but hash tables DON’T. They use a hash function to figure out where to store elements.

Hash table is one of the most useful complex data structures.

Synonyms: hash maps, maps, dictionaries, associative arrays.

A hash table uses an array to store data. Since you can get an item from an array instantly (which means O₍₁₎), they are as fast as arrays.

You probably will never implement a hash table yourself, since most programming languages already have an implementation. On python a dictionary is a hash table.

A hash table has keys and values. It maps keys to values.

Use cases for hash tables: . Lookups . Preventing duplicate entries . Cache

Elaborate on using a hash table for lookups. When you need to create a mapping from one thing to another or look something up. E.g. DNS resolution.

Elaborate on using a hash table to prevent duplicate entries. Let’s say you have to manage that during an election a person cannot vote twice. To do that, you can use a hash table with the person’s id. When a new person is ready to vote, you can check the hash table. If the person’s name is on it, s/he has already voted, so you do not allow them to proceed. But if the person’s name is not, then you allow them to proceed and add the person to the hash table, so that if it tries again you can prevent s/he from voting. A hash table is great for that because it instantly can check if a key (the person’s name) is on it or not - O₍₁₎.

Elaborate on using a hash table for caching. Caching is a common way to make things faster. You can store a long computation’s result in a hashmap as keys-values. So, before doing the computation, you can first check if its’ result is on the hashmap. If it is, you return the value. If not, you can compute it and, when finished, store on the hashmap so that future requests to the same key return directly from the cache instead of waiting the processing to be done more times.