What is a hash table? It is a data structure that has extra logic underneath (a hash function).

What is a hash function? It is a function that maps strings to numbers (keys to values). It tells exactly where a value is stored, so that a search is not needed.

What are the requirements of a hash function? . Always map the same string to the same index . Map differnt strings to different indexes . Know the array’s length and only return valid indexes.

What is a hash table composed by? A hash function and an array.

What is the Big-O notation for searches on hash tables? O₍₁₎. That is because they use arrays to store data, and you can get an item from an array instantly.

Do hash tables map to memory positions? No. They use a hash function to figure out where to store elements.

Which are synonyms for hash tables? Hashmaps, maps, dictionaries, associative arrays.

Since most programming languages have an implementation of hash tables, which is python’s? Dictionaries (dicts).

Where you can use hash tables? For lookups, preventing duplicate entries and caches.

How can we use a hash table for lookups? For DNS resolution, e.g.

How can we use a hash table to prevent duplicate entries? First you check if the element is on the hash table (which is O₍₁₎ - returns instantly). If it is not, you add it. If it is, you do not add it.

How can we use a hash table for caching? You can store the input and result of an operation (which may be costly in terms of resources) into a hash table. Then, before doing the operation again, you can check the hash table and immediately return the result if the input value is already on the hash table.