Notes On Hashing

• Technique that promises near-ϑ(1) data lookup, compared with ϑ(n) for linked lists or ϑ(log n) for binary search trees.
• Uses a hash function - a means of interpreting some object numerically (with an integer usually) to determine its position in some table (hashtable).
• There's no order (e.g. sorting) to items stored in the hashtable - it all seems random and is the reason this process is sometimes called randomizing.
• Implementations prone to inefficient storage usage and high rates of collisions when used slots are far-flung and many entries end up with the same hash code, respectively.
• There's no such thing as a perfect hashing algorithm - there will always be some collisions and space will never always be utilized efficiently enough - a good trade-off is needed.
  
• Prime numbers are king when calculating hashes.
• The JDK's String class has the simplest and yet effective hashing algorithm I have ever seen!
• When a hashing table fills up, you need to resize it dynamically.
• Two techniques exist that help reduce the need to resize hashtables: (1) probing, and (2) bucketing.
• Linear probing = if a collision occurs, look for the next available slot (including wrapping to the head of the table if necessary) to place the object in. At some point with more and more objects being added, performance degrades to linear/brute-force ϑ(n).
  
• Bucketing = maintain a collection at each hashtable slot so that each hashcode can have more than one object.
• One way to determine when to resize a hashtable is to keep track of a load factor = the ratio of stored values to available buckets (for bucketing).
• A load factor of about 75% is a fairly good trade-off between space and time, and works well for most implementations.
• Bucketing is the most efficient of the two techniques. Nor surprisingly, the JDK version implements bucketing with a default load factor if 0.75.
• Modern hashing functions are based on serious mathematical analysis (beyond me). There are several websites I came across with some good hashing algorithms for everything from cryptography to applications in geometry: Arash Partow's site and Hash Algorithm Directory are just two of the many out there.
• HowStuffWorks.com discusses hashing algorithms in their article about encryption.
• Most everyday programmers don't deal with hashing (designing and implementing algorithms) beyond using data structures available in most APIs. I've never had to do anything like that beyond using the Hashtable and HashMap classes provided in the JDK. Always preferable to use any of the good GUID generators currently available (which probably use some sort of hashing internally). The advantage is that they guarantee you will have a unique identifier for every object in the proper context.
  

It's In The Sorting, Dude!

I just finished consulting on an interesting project: this client's inhouse web application had been working great until recently when it seemed to take longer and longer to respond to requests. Being it is an SOA application that uses AJAX all over, speed is of the essence for an overall satisfactory user experience. A couple of times, the IT guys had upgraded the servers running the webapp (hardware), but the problem lingered. So obviously the webapp itself was to blame - but where would the issue be in an application that's been relatively bug free since its inception?
Long story short, the sorting algorithms used were to blame. I couldn't identify which one was being used (proprietary or more advanced than I have learned?), but magic happened when I replaced the sorter with the well-known mergesort algorithm. In preliminary testing, the problem is pretty much gone for the size of live data the company typically works with. Amazing!

My real excitement though is in the fact that I got to use (so soon) knowledge from a previous school class I had taken (Design and Analysis of Algorthms, and Data Structures). I didn't expect to be using ideas from the class in a real-world environment yet, but I found myself doing real analysis of the client's code like we had done in assignments, and making a decision based solely on the results - and it worked. Sometimes class materials don't make complete sense until you have to use them practically.

Mergesort is a divide-and-conquer comparison-based algorithm that runs in ϑ(n log n) computational time. Its only drawback is that it requires significantly more memory to do its job than other algorithms. Here's the Java implementation of mergesort:

public class MergesortListSorter implements ListSorter {
    private final Comparator comp;
    
    public MergesortListSorter(Comparator comp) {
        assert (comp!=null): "Comparator cannot be null.";
        this.comp = comp;
    }
    
    public List sort(List list) {
        assert (list!=null): "List cannot be null.";
        return mergesort(list, 0, list.size()-1);
    }

    private List merge(List left, List right) {
        List result = new LinkedList();
        Iterator l = left.iterator();
        Iterator r = right.iterator();
        l.first();
        r.first();
        while(!(l.isDone() && r.isDone())) {
            if(l.isDone()) {
                result.add(r.current());
                r.next();
            } else if (r.isDone()) {
                result.add(l.current());
                l.next();
            } else if (comp.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }
        return result;
    }

    private List mergesort(List list, int s, int e) {
        if(s == e) {
            List result = new LinkedList();
            result.add(list.get(s));
            return result;
        }
        int split = s + (e - s)/2;
        List left = mergesort(list, s, split);
        List right = mergesort(list, split+1, e);
        return merge(left, right);
    }
}

There's probably better implementations out there than this, but this variety worked well. The actual solution was a blend of mergesort and shellsort because both perform well in average and worst case scenarios. Java helps with the problem of memory because object references are used in collections (as opposed to objects themselves), so the overhead in memory is in the additional references that are created.

Selection Sort With Comparator

Selection sort works by finding the smallest unsorted element in the collection and swapping it with an item in the position that's to be filled next. Because swaps don't happen all the time, this algorithm is a little but more efficient than bubblesort (about 60% better).
The algorithm is a ϑ(n²) complexity computation, efficient enough for small problem sizes. Here's a Java implementation of the algorithm that uses a comparator to specify more complex ordering criteria.

package com.strive.research.algorithms.sorting;

import java.util.Comparator;
import com.strive.research.algorithms.lists.List;
import com.strive.research.algorithms.util.Utilities;

@SuppressWarnings("unchecked")
public class SelectionsortListSorter implements ListSorter {
 private final Comparator comparator;
 
 public SelectionsortListSorter(Comparator comparator) {
  assert(comparator != null): "Comparator cannot be null";
  this.comparator = comparator;
 }
 
 @Override
 public List sort(List list) {
  assert(list != null): "List cannot be null";
  int size = list.size();
  for(int slot = 1; slot < size - 1; ++slot) {
   int smallest = slot;
   for(int check = slot + 1; check < size; ++check) {
    if(comparator.compare(list.get(check), list.get(smallest)) < 0) {
     smallest = check;
    }
   }
   Utilities.swap(list, smallest, slot);
  }
  return list;
 }
}

Bubblesort With Comparator

Bubblesort works by iterating over items in a list and swapping adjucent elements into the required order. Iteration continues until no more swaps are required.
You can make sorting more generic by using comparators. This allows a sorter to sort any collection of data using more complex criteria specified in a comparator. Here's a simple implementation:

package com.strive.research.algorithms.sorting;

import java.util.Comparator;
import com.strive.research.algorithms.lists.List;
import com.strive.research.algorithms.util.Utilities;

@SuppressWarnings("unchecked")
public class BubblesortListSorter implements ListSorter {
 private final Comparator comparator;
 
 public BubblesortListSorter(Comparator comparator) {
  assert(comparator != null): "Comparator cannot be null";
  this.comparator = comparator;
 }

 @Override
 public List sort(List list) {
  assert(list != null): "List cannot be null";
  int size = list.size();
  for(int pass = 1; pass < size; ++pass) {
   for(int left = 0; left < (size - pass); ++left) {
    int right = left + 1;
    if(comparator.compare(list.get(left), list.get(right)) > 0) {
     Utilities.swap(list, left, right);
    }
   }
  }
  return list;
 }
}

The meat of the algorithm is public List sort(List list), which all implementors of my custom ListSorter interface must implement. This algorithm does in-place sorting, so there is no need to return the list really. Bubblesort is a ϑ(n²) complexity computation, efficient enough for small problem sizes.

Filter Iterators Using Predicates

Processing arrays is a simple affair: you can access elements directly by using their indexes, or iterate these simple data structures from start to end. Pretty soon though, you'll begin wishing for more flexibility with the use of more complex data structures and business rules. For example, if you wish to process only elements with a certain attribute, or exclude elements based on some selection criteria, or write applications that do not need to copy entire contents into arrays before processing, simple arrays are not what you need.
The solution is to write customized iterators that can manipulate your basic array without creating duplicate data, minimize having to write duplicate code if you wish to process the array in more than one place, and really separate logic for selecting data from code that processes the data. The easy way is to couple an iterator with a predicate: the iterator can visit any of the elements of the array, while the predicate evaluates whether the elements visited meet some criteria for selection.

Here's an implementation of this idea: this driver class shows how you can filter elements of an array based on a simple criterion. The program generates randomly an array of graph coordinates, and uses a predicate iterator to select only coordinates in the first quadrant.

package com.strive.research.algorithms.iteration;

public class PredicateIteration {
 
 /**
  * Generates an array of coordinates.
  * @param number Number of coordinates to generate.
  * @return Array of coordinates.
  */
 public Coordinate[] generateCoordinates(int number) {
  Coordinate[] array = new Coordinate[number];
  for(int i = 0; i < array.length; i++) {
   array[i] = new Coordinate();
  }
  return array;
 }
 
 /**
  * Prints the contents of an iterator by calling elements' toString() method.
  * @param label Label to prefix ahead of iterator contents.
  * @param iterator The iterator with contents to print
  */
 public void print(String label, Iterator iterator) {  
  String contents = "{";
  boolean comma = false;
  for(iterator.first(); !iterator.isDone(); iterator.next(), comma = true) {
   if(comma) {
    contents += ", ";
   }
   contents += iterator.current().toString();
  }
  contents += "}";
  System.out.println(label + ": " + contents);
 }
 
 /**
  * Demo and test ...
  * @param args (Not used).
  */
 public static void main(String[] args) {
  PredicateIteration prediter = new PredicateIteration();
  // How many test items to use
  int number = 10;
  // Generate the coordinates
  Coordinate[] coordinates = prediter.generateCoordinates(number);
  // Print the generated list
  Iterator general = new ArrayIterator(coordinates);
  prediter.print("Original", general);
  // Use predicate to show only coordinates in first quadrant
  FilterIterator filtered = new FilterIterator(general, new FirstQuadrantPredicate());
  prediter.print("Filtered", filtered);
  // Exit
  System.exit(0);
 }
}

These projects are built using Eclipse 3.3.x (Europa) with JDK 1.6.x. You can find complete source code here:
Base project (AlgorithmsInJava) = defines the interfaces and base implementations that largely implement the idea above.
Demo project (IterationWithPredicates) = references the base project and implements a class the shows how to use iterators and predicates to filter data in arrays.

Bernoulli Trials

When you toss a coin, the chances that a head shows are 50/50. But using Bernoulli Trials, we can repeats the coin tosses any number of times to obtain a spread of probabilities - the bell curve we all know. Below is the Java implementation of this idea. The algorithm likely runs in O(n²) time, so it is not efficient for large experiments.

    /**
     * Prints a histogram showing the results of tossing a coin many times
     * and the probability that either heads or tails will be shown. This is
     * generally known as the sequence of Bernoulli Trials in probability theory.
     * @param trials Number of times to repeat the experiment.
     * @param flips Number of coin flips per experiment.
     */
    public static void bernoulliTrials(int trials, int flips) {
        int i, j, cnt;
        int[] f = new int[flips + 1];
        for (j = 0; j <= flips; j++)
            f[j] = 0;
        for (i = 0; i < trials; i++, f[cnt]++)
            for (cnt = 0, j = 0; j <= flips; j++)
                if (Math.random() < 0.5)
                    cnt++; 
        // Drawing the histogram
        for (j = 0; j <= flips; j++) {
            if (f[j] == 0)
                System.out.print(".");
            for (i = 0; i < f[j]; i += 10)
                System.out.print("*");
            System.out.println();
        }
    }

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for determining prime numbers less than a given maximum number. Prime numbers have become suddenly important to me, especially in scenarios where events must not collide. In that case, staggering timeouts minimizes the chances when primes are used.
This is the Java implementation of the algorithm, the quick and dirty way. Of course there's more complex and efficient algorithms out there. This one is good enough for small maximums and runs in O(n lg n) time. Beyond a certain number, the system will run out of memory and begin taking longer to determine the next prime.:

/**
* Prints a list of prime numbers less than the max given.
* @param max Prime numbers will be less than this maximum.
*/
private static void printPrimes(int max) {
// Create max-sized array
boolean[] a = new boolean[max];
// Initially assume all numbers are not non-prime
for (int i = 2; i+=1)
a[i] = true;
}
// Sieve of Eratosthenes algorithm
for (int i = 2; i+=1)
if (a[i] != false) {
for (int j = i; j * i < max; j+=1)
a[i * j] = false;
}
}
}
// Print the primes, 0 and 1 are not
for (int i = 2; i+=1)
if (a[i]) {
System.out.print(" " + i);
}
}
System.out.print("\n");
}