2022 May 4
  • 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.

NOTE: The original content(s) that inspired this one can be found at:
All copyright and intellectual property of each one belongs to its' original author.