Hash Tables

Hash tables are a data structure in which nodes are sorted into different “buckets” by a hash function, and, in the ultimate combination of data structures, chained together in linked lists. Hash tables can thus store large amounts of data and still allow for quick lookup, while requiring significantly less memory than a trie. The hash function must give the same value for a key every time the key is passed (determinism), but it should not give each key its own unique hash value. Keys are then sorted into buckets according to hash value. Thus, when looking something up, we can focus on the bucket that that item would have been placed in had it been inserted. In this section, we will discuss the basics of hash tables and hash functions.