W2D5 - Hashmaps & LRU Caches
Topics
Sets
Maps
Hashing functions
HashSets
HashMaps
LinkedLists
Singley-linked list
Doubley-linked list
LRU Cache
Big-Oh Space/Time Complexity
Projects
MaxIntSet : [0,2,3,5] --> [true, false, true, true, false, true]
O(1) lookup time, wasteful space
IntSet : fixed length array, use el%num_buckets to determine which bucket el will fall under
O(1) insertion, O(n) retrieval
ResizingIntSet : Double length of underlying fixed-length array when num_elements >= length
O(1) insertion, O(1) amortized retrieval
Hashing - built custom Array#hash,String#hash, Hashmp.hash using Ruby's Fixnum#hash method
HashSet - like previous Set, but use el.hash % num_buckets rather than el. Can now accept any type of element
LinkedList
Singly-linked - still take O(n) time to reach last object
Doubly-linked - more efficient
Remove links by reassigning points for @prev & @next to skip over current link
HashMap - use a Map with an underlying Linked List for the buckets
LRU Cache - use a Map
Least Recentuly Used - method of deciding what to keep/discard in memory
Keys -- hashed version of the original key
Values -- Link in ordered LinkedList
Keep length of linked list
Partner: Raymonds Zhang