Hash Maps

Question 1

What is a map data type? Whats another name for it? What does a map data type consist of?

Answer 1

Map data types are data types found in programming languages. In python, maps are known as dictionaries. Maps can also be known as associative array. Maps consist of key-value pairs.

Question 2

Is hash map the same as hash table?

Answer 2

Yes it’s the same thing

Question 3

What is time complexity of lookup/search in a hash table?

Answer 3

O(1) on average because to get the index of a key, we run it through the hash function which is a fixed number of steps, and once we know the index, searching at a known index is constant

Question 4

Whats the work flow for getting an index in a hash map based on a given key (two step process)

Answer 4

Pass the key through the hash function
Take modulo of the hashed key % capacity of hash map….this gives you the index relative to the array size

hash = hash_function(key)
index = hash % array_size

Question 5

What is a hash function?

Answer 5

A hash function takes a key value of some type and returns an integer that corresponds to an index in an array

Question 6

When choosing/designing a hash function, what are the 3 properties you should have for an optimal function?

Answer 6

1) Determinism- The hash function should be consistent in the hashing that it does for values. A given input should always map to the same hash value.
2) Uniformity- the inputs should be mapped as evenly as possible over the output range. A non-uniform function can result in many collisions, where multiple elements are hashed to the same array index. So basically the hash function should as best as possible uniformly DISTRIBUTE filling buckets across the whole array
3) Speed- The hash function should have a low computational burden…in other words it should be fast

Question 7

What is a perfect hash function?

Answer 7

A perfect hash function is one that results in no collisions…every key gets a unique output.

Question 8

What is a minimally perfect hash function?

Answer 8

A minimally perfect hash function is one that results in no collisions for a table size that equals exactly the number of elements.

A minimally perfect hash function is one that results in no collisions for a table size that exactly equals the number of elements. A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers – usually the numbers from 0 to n − 1 or from 1 to n.

Question 9

What is a collision?

Answer 9

A collision is when two different keys are hashed to the same index. i.e same output for two different inputs.

Question 10

What is chaining and what is it used to address?

Answer 10

Chaining is a way to resolve collisions in a hash table. Chaining allows keys to be hashed to the same index by creating linked lists or buckets at every index. When two different keys are hashed to the same index, the key/values are simply chained as nodes in the bucket where they belong.

To accommodate multiple keys, linked lists can be used to store the individual keys that map to the same entry. The linked lists are commonly referred to as buckets or chains, and this technique of collision resolution is known as chaining.

Question 11

Are linked lists the only data structure you can use to address chaining?

Answer 11

No, you can also use balanced binary trees or dynamic arrays

Question 12

In a chained hash table, accessing the value for a particular key would follow this procedure:

Answer 12

1) hash the key to get the index of the bucket
2) search the linked list in the correct bucket for the key. There may be multiple keys hashed into the same bucket, so we need to search the linked list for the specific key that was passed in

Question 13

What is the “load factor” of a hash table. Whats its equation?

Answer 13

Load factor is the average number of elements in each bucket

The equation is 𝝺 = total number of elements in table/number of buckets

Question 14

In a chained hash table, can the load factor be greater than 1?

Answer 14

Yes in a chained hash table, the load factor can be greater than 1.

Question 15

As load factor increases, what happens to the speed of operations on the table?

Answer 15

Speed decreases.

Question 16

For a linked list-based chained table, the average number of links traversed for successful searches is…(hint: load factor plays a part)

Answer 16

𝝺 / 2

Question 17

For unsuccessful searches, the average number of links traversed is equal to…

Answer 17

the load factor, 𝝺

Question 18

What can you do to maintain strong performance speeds on a hash table?

Answer 18

To maintain strong performance with a hash table, we often double the number of buckets when the load factor reaches a certain limit (e.g., 8)

Question 19

When resizing a hash table, what do you have to do to all elements?

Answer 19

You have to rehash them based on the new capacity/new number of buckets

Question 20

What is the average-case complexity of a linked list-based chained hash table?

Answer 20

1. Assume that the hash function has a good distribution.
2. The AVERAGE case for all operations is O(𝝺).
   If the number of buckets is adjusted according to the load factor, then the number of elements is a constant factor of the number of buckets (i.e.,: 𝝺 = n/m = O(m)/m = amortized O(1)). This is because the hash table will get resized every time it reaches a certain amount of elements. So, assuming the hash function has good distribution, there will be less collisions as the hash table size increases. Thus, lookup will be O(1) because you wouldn’t have to iterate through long buckets to find the value you’re looking for for a given key

Question 21

What is the worst case time complexity of a hash table? When would this happen?

Answer 21

O(n). This would happen when all elements end up in the same bucket. This could be a result of a bad hash function and/or a large load factor with a lack of resizing.

Question 22

Aside from chaining, what is another form of collision resolution in hash tables? Briefly explain how it resolves collisions.

Answer 22

Open addressing. It works by probing for a next empty spot in the array if a collision occurs.

Question 23

How are hashed elements stored in the array in open addressing?

Answer 23

They are stored directly in the array. No linked lists or other data structures involving chaining.

Question 24

Whats the 3 step general process for inserting into hash table that uses open addressing collision resolution?

Answer 24

1) Hash the passed key for output of an index to be inserted in the array
2) If the index is empty, insert the element there and stop
3) If the index is not empty, iterate down the line looking for the next open spot using a probing method

Question 25

What is the process called for searching for a next open position in a hash map using open addressing collision resolution? What are three different kinds of it?

Answer 25

Probing.
Linear probing: index = index_initial + j (where j = 1, 2, 3,….)
Quadratic probing: index = index_inital + j^2 (where j = 1, 2, 3…)
Double hashing: index = index_inital + j*(h_2(key)) (where j = 1, 2, 3,…)
h_2 is a second independent hash function

Probing is only done when the initial index from the hash function results in a collision, meaning an element already exists at that index so we have to find the next open spot

Question 26

How do you know when to stop probing when searching in an open-address collision resolution?

Answer 26

You probe until you find the element you’re looking for or you encounter an empty spot

Question 27

What do you need to do when removing an element from a hash table thats using open addressing. Why do you need to do this?

Answer 27

You have to insert a special value called a tombstone when you remove an element. This is needed because without it it disrupts probing for an element you’re searching for because probing relies on stopping when you’ve found the first empty index or the element you’re searching for

Question 28

Can tombstones be replaced?

Answer 28

Yes, tombstones just denote a no longer occupied space” so when you add a new element it can be hashed into the space that the tombstone is occupying

Question 29

Does open addressing involve linked lists or buckets?

Answer 29

No it’s just an array

Question 30

What is clustering in open addressing? Which probing method is more likely to create clusters? Why?

Answer 30

Clustering is when elements are placed directly next to each other in adjacent indices, causing clusters of elements.

Linear probing is more likely to create clusters. This is because the probability of a new entry being added to an existing cluster increases as the size of the cluster increases, mainly because linear probing simply searches for the next adjacent available spot.

Question 31

What probing methods can be used to limit clustering?

Answer 31

Quadratic probing and double hashing

Question 32

Using open addressing, a table’s load factor absolutely cannot exceed what number? Why?

Answer 32

1. Because a load factor of 1 means the array is full and you can therefore no longer insert new elements into it.

Question 33

What is a common solution to a full hash table? What is a good load factor to use this solution?

Answer 33

Resize it into a bigger table. Resizing could occur ar some threshold such as 0.75 load factor

Question 34

Why is it bad to have a very low load factor, especially in open-addressing hash tables?

Answer 34

This means that we have a lot of unused space allocated, so this is space inefficient.