Hashing
When we cannot use hashing - when order is important => Find key which is just smaller than the given key. COMPRESSION MAP => H(key) = key % M (M is prime number close to table size) POLYNOMIAL ACCUMULATION => H(string) = [(s[0]*x^0) + (s[1]*x^1) + ....] % M Requirements for hash function => H(key) = value No matter how many times you pass key => value should always be same If M is size of hash table => value must lie between 0 to M-1 Value should be uniformly distributed --> less collision UNIVERSAL HASHING - choose any hash function uniformly at random