Pathological Data Sets and Universal Hashing Motivation

The load of a hash table is the total number of elements in the hash table divided by total amount of space in the table. This is usually denoted as alpha. Alpha=O(1) is necessary for operations to run in constant time. With open addressing we need alpha << 1. For good performance, we need to control load.

Secondly, for good performance, we need a good hash function, i.e. spreads the data evenly across buckets. However, a hash table that spreads out every data set does not exist. That is, for every hash function, there is a pathological data set.

Pathological Data in the Real World
Reference: Crosby and Wallach, USENIX 2003.
You can paralyze several real-world systems (like network intrusion detection) by exploiting badly designed hash functions. Two characteristics of these breakable systems were:

1. Open source
2. Overly simplistic hash function designed for speed (easy to reverse engineer a pathological data set)

So what should we do to solve this problem? 

Object Oriented Programming

All OOP languages implement dynamic method dispatch. This means that the code invoked by a method call depends on the runtime type of the object that contains the method.

This dynamic dispatch is analogous to calls to higher-order-functions. Can we implement objects in terms of higher-order-functions? Can we implement higher-order-functions in terms of objects?

Traits

For a class that wants to inherit from more than one superclass, it can use inherit from traits. Traits are like abstract classes defined as:

trait name {}

Classes and objects can only inherit from one superclass, but many traits. For example,

class Square extends Shapes with Planar with Movable ...

Traits are like interfaces in Java, but are more powerful since they can contain fields and concrete methods. However, they cannot have valued parameters.

 

Functions returning Functions

In Scala, we can use multiple parameter lists. Before

def sum(f: Int => Int): (Int, Int) => Int = {
     def sumF(a: Int, b: Int): Int =
          if (a > b) 0
          else f(a) + sumF(a+1, b)
     sumF
}

Now, we can turn that into

def sum(f: Int => Int)(a: Int, b: Int): Int =
     if (a>b) 0 else f(a) + sum(f)(a+1, b) 

This way, we can still use sum without the second parameter list such as sum(cube).

Currying

In the sum function, there is repetition in the parameters a and b which just get passed from one function to another. We can get rid of these with currying. Then, we can rewrite sum as follows:

def sum(f: Int => Int): (Int, Int) => Int = {
     def sumF(a: Int, b: Int): Int =
          if (a > b) 0
          else f(a) + sumF(a+1, b)
     sumF
}

Now sum is a function that returns another function. This function applies the input function parameter and sums up the result. We can redefine the three sum functions as:

def sumInts = sum(x => x)
def sumCubes = sum(x => x * x * x)
def sumFacts = sum(factorial)

If we wanted to just use the function sumCubes without explicitly defining it, we could do it another way: sum(cube)(1, 10).  sum(cube) applies the cube function to the sum function and returns the sum of cubes function. This function is then applied to the parameters (1,10). We see that sum(cube) is equivalent to our definition of sumCubes. Function application associates to the left.

Rewriting the main sum method

We can optimize the main sum method by making it tail-recursive. This can be done with an accumulator as follows:

def sum(f: Int => Int, a: Int, b: Int) = {
     def loop(a: Int, acc: Int): Int =
          if (a>b) acc
          else loop(a+1, f(a) + acc)
     loop(a, 0)
} 

Anonymous Functions

An anonymous function is one that does not have a name and is treated as a literal. We can rewrite the cubic function as: (x: Int) => x * x * x. Another example is: (x: Int, y: Int) => x + y.

Every anonymous function can be written with a def like normal functions. Therefore we can say that anonymous functions are syntactic sugar.

Using anonymous functions, we can rewrite the three sum functions more succinctly:
     def sumInts(a: Int, b: Int) = sum(x => x, a, b)
     def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)