Be insensitive, and keep a lifelong growth mindset.

0%

### I. Hash Function

##### a. 31

In Java, the hash code for a String object is computed as

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

##### b. 31 mod n

Based on 31, mod the result with n, n stands for capacity.

##### c. rolling hash

This is used to find if str1 contains str2:

index = 0123456789
str1 = "fsaabcdefg"
str2 = "abc"
...
result1 = str1[3] * 31 ^ 0 + str1[4] * 31 ^ 1 + str1[5] * 31 ^ 2
...
result2 = str2[0] * 31 ^ 0 + str2[1] * 31 ^ 1 + str2[2] * 31 ^ 2

### II. Hash Families

ConcurrentHashMap: an advanced version of Hashtable;
TreeMap: https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

### IV. Probabilities

a. n elements, n cells, question: for any particular cell, the prob of
the number of elements is equal to k.
Ans: prob = C(n, k) * (1/n)^k * (1-1/n)^(n-k)

b. N people with everyone of different birthday
Ans: p(n) = 365/365 * 364/365 * .. * (365-n)/365 < 50%

c. More probability questions
https://www.careercup.com/page?pid=probability-interview-questions