Hash tables

Question 1

What is hashing?

Answer 1

Mapping an object or number onto a range of integers

Question 2

What is collision?

Answer 2

When multiple object hash to the same value

Question 3

What are 4 necessary properties of a hash function?

Answer 3

1. Fast, should take O(1)
2. Hash function must be deterministic
3. Equal objects should hash to the same slot
4. If two objects are randomly chosen, there is a 1/2^{32} chance they have the same hash value

Question 4

Give an example of a predetermined hash function.

Answer 4

Suppose you have a static member variable (available across all instances) to keep track of the hash value. Every time you create an object, the object gets the current hash value incremented by 1.

Question 5

What is an issue with the predetermined hash function example?

Answer 5

The hash value assigned is not tied to the object itself, but to the construction process, i.e. if we save the object to a secondary memory (e.g. write to file or disk), when we reload the data, the constructor will run again and the object will be assigned a different hash value this time, even though it is the same object.

Question 6

Using predetermined hash functions, each object gets a unique hash value. What is a scenario where this is not appropriate?

Answer 6

1. When we have two strings with the same characters
2. When we have two objects that are conceptually equal, e.g. two rationals 1/2 and 3/6

Question 7

How to solve the issue of two logically equal rationals not hashing to the same value?

Answer 7

Divide both numerator and denominator by gcd to reduce the fraction to its simplest form. Then apply the hash function. One example is take the product of the numerator and the denominator.

Question 8

Why is just adding the characters in a string a bad way to hash a string?

Answer 8

It takes a long runtime, hashes “ABC” to the same slot as “BCA” (ignores all ordering of words), poor distribution (long strings will always hash to bigger values and long strings might produce hash values that cluster near certain regions of the hash space)

Question 9

Suggest a way to hash strings efficiently that also preserves ordering.

Answer 9

Represent the string as a polynomial p(x)=c_0x^{n-1}+c_1x^{n-2}+…+c_{n-1} where each coefficient is an individual character. Pick a prime number and let that be x to evaluate p(x). Use Horner’s rule to re-order the equation to compute p(x) more efficiently. The result is a single integer, which is the hash value.

Question 10

Why is hashing strings this way good?

Answer 10

1. Using a prime number ensures good distribution of hash values
2. Order-sensitive, preserves information of the string

Question 11

Why do we want to study asymptotic?

Answer 11

We want a way to analyze an algorithm and compare their performances regardless of the computer it is run on. It helps us learn about the scalability of algorithms, independent of hardware.

Question 12

How can we think of f(n) ~ g(n) and f(n) < g(n)?

Answer 12

f(n)~g(n) means their performances are comparable for large values of n and improving hardware will affect both algorithms similarly. It is always possible to buy a faster computer so one algorithm will run faster than the other.

f(n)<g(n) means f(n) grows asymptotically slower than g(n). No matter how fast a computer becomes, f(n) will always run faster than g(n).

Question 13

Is o(.) weaker than O(.)?

Answer 13

No, o(.) is stricter than O(.). Small-o requires that f(n) grows strictly slower than g(n) as n tends to infinity.

Big-o is an upper bound indicating that f(n) does not grow faster than g(n) for sufficiently large n.

Question 14

Is small-omega stricter than big-omega?

Answer 14

For small-omega, f(n) grows strictly faster than g(n), while for big-omega, f(n) grows at least as fast as g(n), up to a constant factor.