Hash Map

Question 1

What are the 3 requirements for a good hash function?

Answer 1

• Consistent
• Efficient to compute and not ignore siginficant numbers
• Should uniformly distribute

Question 2

Why should array size M be prime?

Answer 2

If not, not all bits of key will play role and will therefore lose a chance to disperse evvenly and avoid collisions

Question 3

How do we hash integers, floating-pont numbers, strings?

Answer 3

Use modular hashing
* Integers: Calculation with modular hashing to get index
* Floats: Binary representation of key
* Strings: Treat as large integers
* Compound keys: Mix together in a similar way to strings

Question 4

How do we convert hashCode() into an array index?

Answer 4

Combine with modular hashing by converting 32-bit to 31-bit then compute remainder

Question 5

What is separate Chaining?

Answer 5

Build a linked list or symbol table for each bucket that contains a collision. Should be kept short.

Question 6

How do we implement symbol tables into hash table?

Answer 6

Build for each array index a symbol table of keys that hash to that index
Therefore maintain an array of ST objects that implements operations. This is done by computing Hash Function to get index of object that contain key, then using get() and put() to delegate the operation to that table.

Question 7

What is the average length of the list?

Answer 7

N/M

Question 8

What is the probability that a list has more than t x a keys?

Answer 8

(a e/y)^t e ^(-a)

Question 9

What is linear probing?

Answer 9

Store N key-value pairs in hash table of size M > N, relying on empty entries for collision

Question 10

What are the 3 cases for linear probing?

Answer 10

• Key equal to search key
• Search reaches null
• Key not equal, try next with iteration

Question 11

What is probing?

Answer 11

Operation of determining whether a given table entry holds an item whose key is equal to the search

Question 12

How do we delete a key-value pair from a linear probing table?

Answer 12

• Check if key exists
• Find index by hashing
• Find index where key matches given key, set both the key and value at index to null
• Rehash the subsequent key-value pairs re-inserting key-value pairs into hash table using put

Question 13

What is the load factor, a?

Answer 13

Percentage of table entries that are occupied. Can never be 1