[JVM-0] Architecture of JVM

Java and Java Platform

Java has 4 core parts
  0. Language: a programmer uses it to write programs
  1. Class file format: java compiler translates it to byte codes to be executed by jvm
  2. JVM: an application that executes bytecode
  3. API: to interact with host machine

Java platform has 2 parts
  0. API
  1. JVM

A Java program runs on a Java platform.

Java program execution

Here are the steps to run a java program on a Java platform.

0. programmer writes java code

  class Test{
    public static void main(String args[]){
      int i = 0;
      int j = 1;
      for(i = 0; i < 10; i++){
        j = j + 1;
      }
    }
  }

1. Compile and produce byte code
              javac Test.java
bytecode has instruction that is targeted for a virtual architecture, java virtual machine.

javap -c Test.class produces the following output

class Test {
  Test();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: iconst_0
       1: istore_1
       2: iconst_1
       3: istore_2
       4: iconst_0
       5: istore_1
       6: iload_1
       7: bipush        10
       9: if_icmpge     22
      12: iload_2
      13: iconst_1
      14: iadd
      15: istore_2
      16: iinc          1, 1
      19: goto          6
      22: return
}

2. user starts jvm by the command,

                java Test

Note: a jvm only runs a single application. jvm takes a class file as an agrument. the class file must have the main method with proper signature.

3. jvm loads, interprets the byte code and runs on host system.

Parts of JVM

0. Class loader: locates and imports byte code to jvm's memory.
    a. checks correctness of a type.
    a. on method area, loads byte code, initializes class variables. on heap creates Class object.
    b. links bytecode of method area with Class on heap.

there are two types of class loader
    a. bootstrap class loader: loads java api from installation location. this is part of jvm and written in c++ probably.
    b. user defined class loader: java classes created by user. these are objects in heap.

1. Method area: class loader loads byte code instructions to this place. For each class following information are stored
    a. fully qualified name of the type
    b. super class
    c. is it class or interface?
    d. modifier (public, abstract, final)
    e. constant pool: constants used by this type
        - string, int, float,
        - other classes used by this class (initially it holds only a symbolic link(fully qualified name), later when those classes are loaded to method area and in heap, those symbolic links are replaced by reference to class)
    f. field information (field name, type, modifier)
    g. method information
      0. name
      1. return type
      2. argument info
      3. modifier
      4. bytecode
      5. number of local variables
      6. size of operand stack
      7. exception table
    h.  class variable: all class's get a copy of static-final variable. static non-final are stored method area.
    i. class loader reference: reference to the loader that loaded this class.
    j. method table: instruction memory address for each method's start.

2. Java stack: each thread has separate java stack. only push and pop operations are allowed. contains stack frames for methods. each stack frame holds following information of a method
  a. parameters
  b. local variables
  c. operand stack
  d. return val
  e. return address
  f. exception table

      if an exception occurs and not catch clause found for that instruction, jvm causes the method return abruptly and re-throws the exception to the callers context.
one thread cannot access another thread's java stack.

3. Program counter: each thread gets one entry in the program counter (pc). pc remembers the next instruction to be run for a thread.

4. Heap: objects gets created in this area.

5. Execution engine: Fetches instructions from method area, translates and executes them. instructions acts on the data on java stack and heap. each thread is an execution engine. Interpreted byte code is cached and accessed if necessary.
2 popular techniques
  a. just in time compile: One by one, takes byte code, translates to native code, executes.
  b. adaptive: acts just like jit except as soon as it finds a code that is being used a lot of time(hot spot) it forks a thread. the thread heavily optimizes the code in hotspot and jvm in later time executes those optimized instructions.

6. Native method stack: holds frames for native methods. native methods works on the frame data and data in heap of JVM.

The following picture shows architecture of JVM

The following picture depicts Program counter and Java stack

** Object representation on JVM

** Thread Synchronization
Thread needs object locking and wait-notify mechanism to work.
calling the following methods on an object
  a. lock: a thread can access lock to an object. another thread has to wait to acquire the lock until the first thread unlocks the object.
  b. wait: a thread calls wait on an object. jvm puts the thread to the wait list of the object and makes it sleep. the thread sleeps until another thread calls notify or notify all
  c. notify and notify all: a thread calls this method on an object to notify the threads waiting on the object's wait list.

** Type of java threads
0. non-daemon thread: used by jvm. inital thread that starts a program, garbage collector.
1. daemon thread: created by running program.
As long as a non-daemon thread keeps running, the jvm would not stop unless exit method has not been called.

Atomic operations such as int, char operations makes sure a variable gets a value assigned either by one of the racing threads. if thread_1 tries to assign 0100 and thread_0 tries to assign 1011 to a variable x, it is guaranteed that x will have either 0100 or 1011 not any other values.

** Data types of jvm
a. reference type: holds object reference
b. primitive type: holds int, float. boolean false is stored as 0, any non-zero is stored as true. primitive types has same size and properties in all jvms. they don't depend on the host architecture.

As the jvm starts working, it's class loader loads byte codes to jvm's method area.

[Algorithms] Binary Search Tree (BST)

          parent
            / \
          /     \
        left    right

Binary search trees stores information (keys) holding some constraint. Each node holds some value. A left node holds value less than or equal to the parent node and right node holds value greater than parent node.

Motivation:
Interval scheduling problems can be solved efficiently with binary search trees. We will need to traverse left and right to see where a given interval should fit into. If that place is already taken or being overlapped by an existing interval, we discard the interval otherwise we insert it.

BST operations
0. insert : insert a key to the tree if the key does not already exist.
1. search : check if a key is present in the tree or not.
2. delete : delete a key if exist in the tree.

0. Insert
def insert (node, key):
  if node == null:
    return new Node(key)
  else if node.key == key:
    return node
  else if (node.key > key):
    node.left = insert(node.left, key)
  else:
    node.right = insert(node.right, key)

1. Search
def search(node, key):
  if node == null:
    return false
  if node.key == key:
    return true
  else if node.key > key:
    return search(node.left, key)
  else
    return search(node.right, key)

2. delete:
def delete(node, key):
  if node == null:
    return node
  if node.key == key:
    if node.left == null
      return node.right
    else if node.left.right == null
      return node.left
    else
      new_node = get_right_most(node.left)
      delete_right_most(node.left)
      new_node.left = node.left
      new_node.right = node.right
      return new_node
  else if node.key > key:
     node.left = delete(node.left, key)
  else
    node.right =  delete(node.right, key)
  return node

Augmented Binary Tree
When a binary tree holds information along with keys, it is called augmented binary tree. A common augmented BST is storing node counts of a subtree.

We will be discussing about the following binary search trees
0. avl tree
1 red-black tree
2. b-tree

AVL Tree
Self balancing binary trees. Balances herself using "rotate" operation. There can be log n number of rotations.
This tree is an augmented data structure. Every node contains the following information
  height of subtree
  left child
  right child
 
property:
  at any node, let h_left and h_right are left sub tree height and right sub tree height.
    |h_left - h_right| <= 1
  number of nodes, at worst case, N_h = 1 + N_(h-1) + N_(h-2) [because in best case both the left and right will be balanced]
  1 + N_(h-1) + N_(h-2) > 1 + 2 * N_(h-2) > 2 * N_(h-2)
  N_h > 2 * N(h-2)
  so number of nodes N = 2 ^ (h/2) => h = O(logn)

Rotation:
      x           <- left rotate                 y
    /   \         right rotate ->              /   \
   A     y                                    x     C
        / \                                  / \
       B   C                                A   B

in order traversal produces A x B y C for both the trees.

insert:
  simple bst insert
  fix avl property broken at any point of insertion. move up.

while insertion, the following cases can occur where AVL tree properties are broken at node x.
0. Right child is right heavy.

         x (h)          
       /   \      
(h-3) A     y (h-1)                                  
           / \                                
   (h-3)  B   C (h-2)                              

a left rotate against right child, y fixes the properties.

        y (h-1)
       / \
(h-2) x   C (h-2)
     / \
    A   B  [both A and B have h-3 height]

1. Right child is left heavy
                      x (h)          
                    /   \      
            (h-3) A     y (h-1)                                  
                       / \                                
               (h-2)  z   C (h-3)                              
                     / \
              (h-3) B   D (h-4)

              do a right rotate with respect to y

                  x (h)
                /   \
        (h-3)  A     z (h-1)
                    / \
            (h-3)  B   y (h-2)
                      / \
               (h-4) D   C (h-3)

        now we have the same situation as case 0. do as we did in case 0.

Mirror situation occurs for left heaviness.

[Algorithms] String search algorithms

String Matching Algorithms

problem: given two strings, s and t. does s occurs as a substring of t?

naive approach:

def substringSearch(t, s):
  for i in range(0..len(t)):
    matched = true
    for j in range(0..len(s)):
      if t[i+j] != s[j]:
        matched = false
        break
    if matched:
      return "String occurs"
  return "does not occur"

Runtime: O(m * n)

Rabin-Karp Algorithm:

def subStringSearch(t, s):
  len_s = len(s)
  pattern_hash = get_hash_val(s, 0, len_s)
  substr_hash = -1
  for i in range(0..len(t)-len(s)):
    substr_hash = get_hash(t, i, i+len_s, substr_hash)
    if substr_hash == pattern_hash:
      if t[i:i+len_s].matches(s):
        return true
  return false

def get_hash_val(s, start, end, prev_hash=-1):
  size_of_alphabet = SIZE_OF_ASCII_CHARS
  lowest_ascii_char = 'a'
  hash_val = 0
  if prev_hash == -1:
    for i in range(start..end):
      hash_val *= size_of_alphabet
      hash_val += (s[i] - lowest_ascii_char)
  else:
      start_char = s[start]
      hash_val = prev_hash * size_of_alphabet + (s[end] - lowest_ascii_char) - start_char * (size_of_alphabet ^ (end-start+1))

Analysis:
  if prev_hash = -1, hashing takes O(s)
  inside the for loop, hashing happens in O(1) time
  the hash function is designed in such a way that if two hash value equals then they are the same string.
  So for good hash function, O(n)
  for bad hash function O(m * n)

[Algorithms] Perfect Hashing: Guarantying constant time operation for hash function

For any hash function, it is possible to find a set of keys that will result O(n) time in search. In this article, I will talk about a scenario when we already know the keys, and we want to do the look up the keys in O(1) time even for the worst case.

Perfect Hashing Scheme:
We need two level hashing. In first level, we have n slots in hash table T where n = number of keys.
At level1, we use one hash function h_l1. Each slot of T contains 3 things
[number of items, hash function, pointer to array holding keys at level 2]

for any slot in T, size of key array in level 2 = (number of keys in level 2) ^ 2.

Index     Level-1         Level-2
0         [2 | 40 | ->]   [- | 40 | 37 | 27 ]
1         [1 | 01 | ->]   [- | 3 ]
2         [1 | 23 | ->]   [- | 25 ]
3         [0 | 19 | ->]   [ ]
4         [1 | 44 | ->]   [ 127 ]

at 0 index, level-1 slot has [2 | 40 | ->] this means, level-2 has 2 elements. So level-2 hash table will have size 2 ^ 2 = 4. the value 40 means universal hash function number 40, h_40 will be used to hash in level 2.

In level-1 there will be collision. We need to guarantee that in level-2 we can find hash functions that won't collide for m_i number of keys.

Proof:
x is a random variable that represents number of collisions in level-2 for a slot i. in i, level-2 has m_i number of keys. then hash table has size (m_i) ^ 2 slots. since, a universal hash function will be used probability of any two keys collide would be 1 / (m_i) ^ 2.

E[x] = sum (1/(m_i ^ 2)) for all keys x and y for given set of keys in level-2 at slot i.
we can make n Choose 2 combinations, so
E[x] = (m_i C 2) * (1/(m_i ^ 2)) < 1 / 2
E[x] <= 1/2

from Markov Inequality, P{x >= t} <= E[x] / t
P{x >= 1} <= E[x] / 2 <= 1/2    [0]
Equation [0], basically says, if we use universal hashing, at least half the cases there will be no collision. So randomly picking some hash functions from universal hashing should quickly yield a good hash function that does not do any collision for the given keys.

Space:
let x is a random variable denoting total space in level-2, then x = sum(n_i ^ 2), where n_0 + n_1 + ... + n_m  = n [n keys and m slots]
E[space] = n + E[x] = O(n)

Reference:
0. MIT OCW 6.046 : Introduction to Algorithms

[Algorithms] Keeping operations on a Hash table constant

In this article, I will discuss how to keep search operation's run time constant in a hash data structure.

Let the table T has m slots. If h is a universal hash function then, for key x and y where x != y
probability(x) = h(y)) = 1 / m
if the number of keys = n, on average every slot will have n / m keys. this is also known as load factor, alpha. So, alpha = n / m.
so each slot will have on average alpha number of keys. So expected number of searches would be O(1 + alpha).
To keep searching constant, we need to keep alpha constant.

As number of keys, n grows alpha starts increasing. If we want to keep alpha ~ 1, we need to increase size of our table. If we can handle
resizing of the table in constant time, we will be able to do operations in hash table in constant time.

Idea is If alpha hits a certain threshold, then we double size of T. This way insertion will be in amortized O(1) time.

Example: Lets say initially T has size m = 1. Insertion has cost O(1) for a hash table as all it does is insert the element at the head.
When we double the table, the cost of insertion goes to O(n) from 1. Fortunately, this does not happen very often, which makes average insertion operation a O(n) time operation. Below I have shown the key number and the order of the operation. When there is only one key, the insertion time is 1. If we add another key, we need to increase size of our table and then copy all the data from old table to new table. This cause O(n) time.

Key#     cost
1             1
2             2
3             1
4             4
5             1
6             1
7             1
8             8
9             1
10           1
11           1
12           1
13           1
14           1
15           1
-----------------
total cost for n insertion  =  (1+1+1..) + (2+4+8) = O(n)  # as the bigger value gets scarce as you keep doubling the table
amortized cost = avg cost per insertion = O(n/n) = O(1)

for n = 1000, the following Haskel code snippet counts average cost of insert operation.
a = sum([2 ^ x | x <- [0..100], 2 ^ x < 1000] ++ take 1000 (repeat 1)) `div` 1000
print a # prints 2

Deletion
Table size = n, number of keys = k. Half the table size when k = n / 4

References:
0. MIT OCW 6.006 Introduction to Algortihms
1. MIT OCW 6.046J Introduction to Algorithms

Quick Haskel

I have been documenting the  concepts and apis of the programming language Haskel. This document has examples of various constructs of the Haskel programming language. It is a live document. Until I complete the contents of [0], I will be updating this document.

function declaration
f x = x + 2   # f(x) = x + 2

conditional
abs x = if x < 0 (-1) * x else x  # an if should always have an else

list
list contains element of the same type.
let myList = [1,2,3]
strings are considered as lists too. "abc" is equivalent to ['a', 'b', 'c']

append to last [slower operation if the first list is big]
myList ++ [5, 6]

append single element to first
7 : myList
[1, 2, 3] is equivalent to 1:2:3:[]

access list element
myList !! 2     # access 2nd element of the list

list comparison
rule: 2 lists can be compared if the elements can be compared. Nonempty list is greater than empty list. element by element is done from start of the list until a match found or one/both of the lists ends.
operator: <, <=, >=, >, ==
a = [1,2,3], b = [4,5,6]
a < b # False

list of list
a = [[], [1,2,3], [4]]

list operations
[<head><......tail......>]
[<.......init.....><last>]
operations does not have side effect meaning they don't modify the list.
head [1,2,3,4,5] #1
tail [1,2,3,4,5] #[2,3,4,5]
init [1,2,3,4,5] #[1,2,3,4]
last [1,2,3,4,5] #5
length [1,2,3] # 3
null [] # True
null [1] # false
reverse [1,2,3] # [3,2,1]
take 1 [7,2,3] # [7]
drop 1 [7,2,3] #[2,3]
maximum [2, 4, 5, 1] # 5
minimum [2, 3, 1, 5] # 1
sum [1, 2, 3] # 6
product [1, 2, 3, 4] # 24
elem 7 [1, 6, 7] # True, 7 belongs to the list
[1..5] #[1,2,3,4,5]
['a'..'d'] # ['a', 'b', 'c', 'd']
[5,4..1] #[5,4,3,2,1]
cycle[1,2,3] #produces infinite list [1,2,3,1,2,3,1,2,3,...infinite]
repeat 5 # [5,5,5,5,5,5,5....infinite size]
repeat [1] # [[1], [1], [1], [1], [1] ... infinite size]
replicate 4 2 # [2, 2, 2, 2]

list comprehension
[x * 2 | x <- [0..5]]  # all x * 2 s such that x belongs to the set [0, 1, 2, 3, 4, 5]
[x * 2 | x <- [0..5], x > 5] # multiple predicate
evenOdd xs = [ if x `mod` 2 == 0 then 0 else 1 | x <- xs ] # function evenOdd takes a list xs and returns a list of 0s and 1s
usage: evenOdd [0..10] # [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[x + y | x <- [0..5], y <- [0..3]] # for all x and y in the sets, generates a list that has the value x + y
length' ls = sum [1 | _ <- ls] # generate a list that has 1 for each element of ls, then sum up all the 1s

Tuple
stores heterogenous typed elements. size is fixed.
(1, 1.1, 'a', "saif")
tuple types are defined by the number of elements in it. a list can hold only same typed elements. thus,
[(1,2), (2, 3), (1,2,3)] causes ERROR
[(1, 2), ('a', 1)] also causes ERROR

Pairs
(1, 3)
fst (1,3) # 1
snd (1,3) # 3
zip ['a', 'b', 'c'] ['x', 'y', 'z'] # [('a','x'),('b','y'),('c','z')]
zip "abc" [1..] # [('a',1),('b',2),('c',3)] notice how only 3 elements are taken from the infinite set

## Type ##
Type is fixed.
ghci command :t shows type of a variable or function.
function type
sum :: Int -> Int -> Int
sum a b =  a + b

common types
Int : bounded by underlying system
Integer : unbounded
Float : real number with single precision
Double : real number with double precision
Bool : boolean type
Char : a Unicode character

Type Class
A type class encloses one or more types.
A type can be member of one more type classes.

ghci command. :t (==)
(==) :: (Eq a) => a -> a -> Bool
How to read. (==) takes 2 argument of type class Eq and returns a Bool type.

Eq
applicable function: ==, /= (not equal)

Ord
values of Ord type can be sorted.
functions to apply : >, >=, <, <=.
comparator function returns GT, LT or EQ.

Show
the value can be presented as a string.
function to apply on this type: show # show 3 => "3"

Read
from string, raw type can be formed
applicable function: read
ex: add (read "3") + 3  # 6
read function need enough hint to know which raw type to produce. for example,
this does not work, read "3"
but read "3" + 3 works, because read knows "3" to be converted to Int
the following example works similar to type casting (according to me)
read "3" :: Int # specifically specify we need 3 to be Int.

more examples:
read "[1, 2, 3]" :: [Int]  # [1,2,3]
read "(2, 'a')" :: (Int , Char) # (2, 'a')
[read "True", True, False, True]

Enum
sequentially enumerable values.
applicable functions: succ, pred

Bounded
has an upper and lower bound

Num
values act like numbers

Floating
applicable functions: sin cos
Enclosing type: Float, Double

Integral
enclosing type: Int, Integer

## Syntax in Functions ##
Pattern matching: choosing a function based on input parameters. Pattern matching works very similar to if else construct.
citizen :: String -> String
citizen "BD" = "Bangladeshi"
citizen "USA" = "American"
citizen x = "Unknown citizen"

line 0, is function input and output type declaration. line 1, says what to do if input = "BD", so on and so forth.

can be used to define base case.
fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci(n-1) + fibonacci(n-2)

If the pattern matching does not contain all the possibilities of input, interpreter will throw an exception.

vector_add :: (Double, Double) -> (Double, Double) -> (Double, Double)
vector_add a b = (fst a + fst b, snd a + snd b)
another way to write
vector_add (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

Usage of '_'
fst' :: (a, b, c) -> a
fst' (a, _, _) = a

head' :: [a] -> a
head' (a:_) = a

As pattern break up input in parts, also gives a way to access the whole. can be applied on list only.
shead :: [Int] -> Int
shead whole@(frst : rest) = frst

Guards
bmiTell :: Double -> String
bmiTell bmi
  | bmi <= 18.5 = "underweight"
  | bmi <= 25.0 = "normal wieght"
  | bmi <= 30.0 = "fat"
  | otherwise = "unhealthy fat"

guard syntax | boolean-expression = expression-to-be-evaluated

where
clause. provides variable like functionality of imperative programming language.

bmiTell w h
  | bmi <= skinny = "you are fine"
  | bmi <= fat = "you are not fine"
  where bmi = w / h ^ 2
        skinny = 18.5
        fat = 23.5

forming tuple and accessing it
initials :: String -> String -> String
initials first last = [f] ++ "." ++ [l] ++ "."
  where (f:_) = first
        (l:_) = last
where to pattern match
desList :: [a] -> String
desList ls = "the list is " ++ check ls
        where check [] = "empty"
              check [x] = "singleton"
              check xs = "a longer list"

Let
let lets you create an expression that generates a value. let are local in scope.
cylinder :: Double -> Double -> Double
cylinder r h =
  let sideArea = 2 * pi * r * h
      topArea = pi * r ^ 2
  in sideArea + 2 * topArea

pattern: let <variable binding> in <expression>
let square x = x * x in (square 2, square 3, square 4)

list comprehension
calcBMI xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi > 25.0]
the value bound through let is visible before '|' and after the let

Case expression
syntax:
case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   pattern -> result
example:
sum' :: [Int] -> Int
sum' xs = case xs of [] -> error "empty list"
                     _ -> sum xs

case can be used inside a function too.
describeList ::[a] -> String
describeList ls = "The list is " ++ case ls of [] -> "empty"
                                               [x] -> "singleton"
                                               xs -> "a longer list"

Reference:

[0] http://learnyouahaskell.com/

Construction and properties of Universal Hash function

Construction of Universal Hash function
Let m is a prime.
k is the key and decomposed in m-base number system with (r + 1) digits,
k = <k_0, k_1, k_2, ..., k_r> where 0 <= k_i <= m-1
take a random number a with r digits, such that
a = <a_0, a_1, a_2, ..., a_r> where a_i is chosen randomly and 0 <= a_i <= m-1

a universal random function, h(k) = sum(k_i * a_i) mod m

size of the set of universal hash functions, |H| = (m ^ (r+1)) [each a_i can be chosen from m choices]

Theorem: for h element_of H and for x != y, probability of collision = 1 / m
let x = <x_0, x_1, ..., x_r>, y = <y_0, y_1, ..., y_r> and x != y
x and y differ at least at 1 digit. how many h element_of H collides for x and y?
let, a = <a_0, a_1, ..., a_r> for h. if for h, x and y collides then
h(x) = h(y)
sum(a_i * x_i) (=) sum(a_i * y_i)    (mod m)
=> sum(a_i * (x_i - y_i)) (=) 0 (mod m)
=> a_0 * (x_0 - y_0) (=) -(sum(a_i * (x_i - y_i)))      (mod m)
=> a_0 (=) -(sum(a_i * (x_i - y_i))) * inverse(x_0 - y_0)     (mod m)     [Eqn. 0]

the [Eqn. 0] says to collide, we can choose any a_1 to a_r but the choice of a_0 is fixed by [Eqn. 0]. for all other choices of a_0 there will be no collision.
total possible ways to construct H, |H| = m ^ (r+1)
we have 1 option for choice of a_0 and m choices for all other r digits. so, number of collision = 1 * m * m * ... * m = m ^ r = |H| / m
for x != y, probability of collision = (cases when collision occurs) / (total number of cases) = (m ^ r) / (m ^ (r+1)) = 1 / m

Theorem: if there are n keys, then for a key x, E[numboer of collision with x] <= n / m
let C_x be a random variable denoting total number of collisions in keys in Table T with x, and C_xy is the indicator random variable
where, C_xy = 0 if no collision for x and y, and C_xy = 1 if there is collision between x and y.

C_xy = sum(C_xy) for all y in T - {x}
so, E[C_xy] = E(sum(C_xy)) = sum E(C_xy) = sum (1/m) = (n - 1) / m

Summary: Property of Universal Hashing
Let, U is the universe of keys and let H be a finite collection of has functions mapping u to {0, 1, ...., m-1}.

H is universal if for all h element_of H, and for all x and y element_of U, where x != y,
Probability(h(x) == h(y)) = 1 / m.

total number of cases where collision happens, for h and for all pair of different keys = |H| / m

Reference:
[0] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-8-universal-hashing-perfect-hashing/