Discussion 9: Heaps of Hashing Christine Zhou Agenda Announcements Heaps Problem 1 Hash tables Problem 2 Hash Codes Problem 3 Announcements Mid-semester survey due this Friday Less time to work on the problems by yourself Goes a little too slowly Don’t really need to talk to each other to discuss the problem Make sure to go through the harder problems Midterm coming up next week Start studying early! Advising sessions are updated weekly! tinyurl.com/cs61b-advising Project 2 Take a look at spec for extra credit opportunities! Start early! We’ll have extra office hours just like we did for Proj1 Refetch from shared to get an updated col/row Heaps Sometimes we want to prioritize elements in a certain way, always get the minimum Use a heap! Complete: missing items only at the bottom level and pushed as far left on the bottom level as possible (Min/Max) heap property: every node’s value is (less/greater) than or equal to its children’s value Common Methods of Heaps Insert Put new item in first free bottom leftmost position, then bubble up removeMin/removeMax Replace root item with the bottom rightmost item, then bubble down the root getMin/getMax Return the value at the root How do we represent heaps? 1 Heaps of fun 1 Heaps of fun HashMaps Use an array to represent your data For each key-value pair, assign each key a “hash code” mod (%) the hash code by the length of the array (this gives you a number between 0 and array.length - 1), use this as the index! N = num elements, M = num buckets, C = some constant If N/M > C, then increase M! N/M is called the load factor If we have multiple elements that go to same place in the array, usually we will keep track of a list Be careful about negative numbers when modding! This is called external chaining What is the runtime of .contains and .insert? 2 HashMap Modification Hash Codes What is necessary for a valid hash code? If A.equals(B) is