Hash Table

Hash Tables are used to implement a Map, they consist of two main components:

• Bucket Array

  Bucket Array: array $A$ of size $N$ where each cell of $A$ is thought of as a “bucket” (collection of key-value pairs)

  Link to original

• Hash Function

  A hash function $h(x)$ has the properties:

  • Compression: $h$ maps an input of $x$ of arbitrary bit length to an output $h(x)$ of fixed bit length $n$ which may be smaller
  • Polynomial time computable

  Link to original

When implementing a map with a hash table, we store the item $(k,v)$ at the index $i=h(k)$.