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.
-
Lecture
-
Shorts
-
Supplementary Resources
- Brian Barto on Hash Crash: The Basics of Hash Tables
- Bilal Ahmad Khan on Hash Tables
- Prashanth Irudayaraj on Distributed Hash Tables
- Patrick Woodhead on Hash functions explained with Emojis
-
Thought Questions
- What real world situation is a hash table useful for?
- Hash tables and tries can often accomplish similar tasks. What are the benefits of using each?
-
Problem