Hashmaps

Question 1

what’s about Map ADT

Answer 1

Keys are unique and immutable, essentially allowing keys to act as search objects for their associated values.
Values are tied to keys, but they do not need to be unique. There may be multiple key value pairs where the value is the same.
The keys do not need to have any sort of ordering to them, though they are allowed to. If ordering is desired, then it becomes something called an Ordered Map, which we will not be delving into in this course.

Question 2

explain the process from hash function -> compression function -> table size -> load factor

Answer 2

1. hash function maps keys to integers
2. compression fuction helps spread out data in the backing structure, reducing collisions
3. table size is usually a prime number
4. load factor is size / capacity: once the load factor is reached, a resizing is needed

Question 3

closed addressing vs. open addressing

Answer 3

Closed Addressing: A policy where all keys that collide into the same location are stored at that location by some means.
Open Addressing: A policy where additional, colliding keys can be stored at a different location based on the original location.

Question 4

how does external chaining work and is it closed addressing or open addressing?

Question 5

how does linear probing work

Answer 5

if a collision occurs at a given index, increment the index by one and check again
- index = (h + original Index) % backingArray.length,
where h is the number of times probed

Question 6

how does resizing backing array work in hashmap

Answer 6

1. create a new backing array of capacity 2N + 1
2. loop through old backing array
3. rehash all cells to new backing array
4. skip over all DEL markers

Question 7

how does quadratic probing work