Hash function, hash table lecture notes study

Feb. 6, 2017

3 lecture notes to study 

Spent more than 2 hours to study the lecture notes - Lecture 6 about Rabin-Karp algorithm from MIT, and also lecture 7, resize of hashtable. 

Will come back to write down some notes and also share something about the algorithm.

Lecture 5 notes: 

Hash functions

Consider a function h(k) that maps the universe U of keys (specific to the hash table, keys could be integers, strings, etc. depending on the hash table) to some index 0 to m. 
We call this function a hash function. 

A good hash function

. satisfies ( approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the m slots. The hash function shouldn't bias towards particular slots

. does not hash similar keys to the same slot (e.g. compiler's symbol table shouldn't hash variables i and j to the same slot since they are used in conjunction a lot)

. is quick to calculate, should have O(1) run time

. is deterministic. h(k) should always return the same value for a given k

Example 1: Division method 

prime number vs should ok be a power of 2 

h(k) = k mod m 

if m = 2 ^p, then the h(k) only looks at the p lower bits of k, completely ignoring the rest of bits in k. A good choice for m with the division method is a prime number ( why are composite numbers bad?). 

Example 2: Multiplication method


h(k) = floor(m(k A mod 1))

Collisions

Chaining - 

load factor alpha

If there are n keys in a hash table with m slots, we can the load factor alpha for the hash table to be n/m. 
Under the assumption of simple uniform hashing, the length of each linked list in the hash table is alpha. 

Open addressing collisions 


Linear probing 

Linear probing resolves collisions by simply checking the next slot, i.e. if a collision occurred in slot j, the next slot to check would be slot j + 1. More formally, linear probing uses the hash function 

  h(k, i) = (h'(k) + i ) mod m. 

Quadratic probing resolves collisions in a similar fashion: 

h(k, i) = h'(k) + c₁ i + c₂ i²) mod m

for some constants c₁, c₂. Instead of linearly traversing through the hash table slots in the case of collisions, quadratic probing introduces more spacing between the slots we try in case of a collision, which reduces the clustering effect seen in linear probing. 

Double hashing resolves collisions by using another hashing function to determine which slot to try next. 

Lecture 6 notes 

Rabin-Karp algorithm

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Rolling hash 

Lecture 7 notes

Hash table

Learn a few keywords:

probe sequence  

Performance of Open Addressing

linear probing 
quadratic probing 
double hashing 

simple uniform hashing assumption (SUHA)
a hash function mapped to any slot from 0 to m -1 with equal probability 

uniform hashing assumption (UHA) 
a random permutation of the slots 0 to m-1 

load balance alpha, p = 1 - alpha probability that the first probe will find an empty slot under UHA. 

Universal hashing  

Rabin-Karp algorithm

Feb. 6, 2017

Introduction
Julia usually does some sports workout after intensive study. This time she chose to study Rabin-Karp algorithm, play with Rolling Hashing algorithm.

She needs some break from the code review Leetcode 49. Julia also traces the top performer's review, here is the one review Rabin-Karp algorithm.

Study

Read Rabin-Karp algorithm wiki article, some keywords from the article:

hash collisions

linear congruential generator 

modular arithmetic

prime

Rabin fingerprint

rolling hash - moving average 

Rabin-Karp rolling hash - read twice, very good talk about time complexity analysis 

Read the article - write down some words: 

https://courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf

Actionable items:
review string algorithm - hidden message.

Rabin-karp algorithm implementation is here in C#.

HackerRank Stryker Code Sprint Grind (V) - The Hidden Message - 70%

Sept. 18, 2016

Problem statement

Julia's C# solution is here.

Here is the timeline Julia worked on the problem solving:

Section 1:
 /* 7:08pm - start to read the problem statement
     *
     * 7:47pm start to write down her approach
     * start position is increasing
     * How to find word match?
     *
     * Time complexity -
     * Data structure
     * Space complexity:
     *
     * 7:55pm start to code
     *
     * 10:04pm start to conduct testing
     */

 Section 2: 
Copy the code from previous practice - substring search, using Boyer algorithm to speed up, avoid timeout issues. 
/*
         * 8:24pm
         * copy code from blog:
         * http://juliachencoding.blogspot.ca/2016/04/hackerrank-string-function-calculation_10.html
         *
         * 8:36 prepare to exit the function
         */
        private static bool findUsingBoyerAlgo(string substring, string s, ref int start)

Section 3:
/*
         * 9:02pm - start to code
         * 9:43pm - still work on the calculation of cost
         * - try to think about how many chars to be removed - second step
         * 9:57pm use brute force solution first
         */
        public static string calculateCost(IList<Match> data,
            string message
            )

Section 4:
 /*
     * 10:19pm
     * Summary of submission:
     * 40.80/60
     * Wrong answer for test case: 11, 15
     * Try to fix the bug
     */

Summary:
1. 40 minutes to read the problem statement
2. 2 hours coding - including eating a dinner - 20 minutes

55 minutes to work on calculation of cost, looked into interval algorithm, and then, figured out using brute force solution instead.

2. 10:04pm testing

Score 40.80/ 60 

Decided to give up bug fix, and then, moved on next question.

Study C# submission - 60 out of 60
1. Use Trie

2. C#: use dynamic programming.

Related to Leetcode 72: "Edit Distance"

3. Study the blog: Levenshtein Distance wiki

4. Study Java 8 solution - use Rabin Karp algorithm search class, DP

5. C++ code - Learn from the best, competitive programmer

6. C++ - KMP algorithm, DP

7. The programmer - 5 Gold - rank 32/1700
a Googler, a blog.

Talk about Google code review - in Chinese, link is here.