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:

• [ ] insert + lookup into hash table (separate chaining, linear probing, double hashing)
• [ ] insert + delete from heap
• [ ] insert + delete + search in trie </aside>

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>

• example usage of a hash table (python/javascript)

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: