table of contents

[aside] psa

  1. myExperience
  2. last lab before ass2 is due
  3. this week’s quiz is due earlier

<aside> 💡 today’s topics: hash tables, heaps, tries

</aside>

<aside> ⚠️ #1 exam tip: learn how to “walk through” each data structure’s main functions:

hash tables

<aside> 📘 hash tables are an associative data structure (as opposed to ordered data structures like arrays or linked lists)— it stores key-value pairs (think dictionaries in Python or objects in JavaScript)

</aside>

ideally…

we want to store key-value pairs, where given a key, we can access its value in $\approx O(1)$ time

we can’t just use a linked list of key-value pairs coz this would take $O(n)$ to search!!

under the hood, hash tables use: