HashtableExample.java

Go to the documentation of this file.

package aud.example.hash;
 
import java.io.File;
import java.util.Scanner;
 
import aud.util.ColormapCount;
import aud.util.SVGViewer;
 
public class HashtableExample {
 
  static public class HashString extends HashFunction<String> {
    long m_ = 2019773507l; // Integer range18014398509481951l;
 
    public HashString() {}
    public HashString(long m) { this(); m_=m; }
 
    @Override public long hash(String s) {
      long h=0;
      for (byte b : s.getBytes()) {
        h =(h*0x100+(b+0x80));
        h%=m_;
      }
      //System.err.println(s+" -> "+h);
      return h;
    }
    @Override public String toString() {
      return "HashString[m="+m_+"]";
    }
  }
 
  static public class IdentityHash extends HashFunction<Integer> {
    @Override public long hash(Integer k) { return k; }
    @Override public String toString() {
      return "Identity";
    }
  }
 
  static public class UniversalHash extends HashFunction<Integer> {
    long a_ = 7177;
    long b_ = 3179303;
    long p_ = 18014398509481951l;
 
    public UniversalHash() {}
    public UniversalHash(long a,long b,long p) {
      this();
      assert(0<a && a<p && 0<=b && b<p);
      a_=a; b_=b; p_=p;
    }
 
    @Override public long hash(Integer k) {
      return (a_*(k>=0 ? k : -k)+b_) % p_;
    }
    @Override public String toString() {
      return "UniversalHash[a="+a_+", b="+b_+", p="+p_+"]";
    }
  }
 
  public class LinearProbing<T> extends CollisionHandler<T> {
    int b_ = 1;
    public LinearProbing() {}
    public LinearProbing(int b) {
      this();
      assert(b>0);
      b_=b;
    }
 
    @Override public long
      newHash(SimpleHashtable<T> table,T key,long h,int count) {
        return h+count*b_;
      }
 
    @Override public String toString() {
      return "LinearProbing[b="+b_+"]";
    }
  }
 
  public class QuadraticProbing<T> extends CollisionHandler<T> {
    int b_ = 1;
    int c_ = 1;
    public QuadraticProbing() {}
    public QuadraticProbing(int b,int c) {
      this();
      assert(b>=0 && c>0);
      b_=b;
      c_=c;
    }
 
    @Override public long
      newHash(SimpleHashtable<T> table,T key,long h,int count) {
        return h + count*b_ + (count*count)*c_;
      }
 
    @Override public String toString() {
      return "QuadraticProbing[b="+b_+", c="+c_+"]";
    }
  }
 
  public class DoubleHashing<T> extends CollisionHandler<T> {
    HashFunction<T> h2_ = null;
 
    public DoubleHashing(HashFunction<T> h2) { h2_=h2; }
 
    @Override public long
      newHash(SimpleHashtable<T> table,T key,long h,int count) {
        long h2=h2_.hash(key);
        return h+count*(h2!=0 ? h2 : 18014398509481951l);
    }
 
    @Override public String toString() {
      return "DoubleHahsing[h2="+h2_+"]";
    }
  }
 
  //
  // test framework
  //
 
  class Key {
    final HashString hashstring = new HashString();
 
    public long intValue;
    String s = null;
 
    public Key(Integer i) { intValue=i; }
    public Key(String s)  { intValue=hashstring.hash(s); this.s=s; }
 
    public boolean equals(Key other) {
      return s==null ?
            (intValue==other.intValue) :
            (s.compareTo(other.s)==0);
    }
 
    @Override public String toString() {
      return s!=null ? s : (""+intValue);
    }
  }
 
  class HashKey extends HashFunction<Key> {
    HashFunction<Integer> ihash;
    HashKey(HashFunction<Integer> hash) { this.ihash=hash; }
    @Override public long hash(Key k) { return ihash.hash((int) k.intValue); }
 
    @Override public String toString() {
      return ihash.toString();
    }
  }
 
  SimpleHashtable<Key>  hashtable=null;
 
  HashFunction<Key>     hashfunction=new HashKey(new IdentityHash());
 
  CollisionHandler<Key> collisionhandler=null;
 
  boolean               readIntegers=true;
 
  int timestep = 1;
 
  int time=0;
 
  int verbose = 0;
 
  static void usage() {
    System.err.println(
        "java HashtableExample [-m M] [-s|--string] [--timestep T]\n"+
        "  [-v | --verbose LEVEL]\n"+
        "  [-u] [--universal A B P]\n"+
        "  [-L] [--linear B]\n"+
        "  [-Q] [--quadratic B C]\n"+
        "  [-S] [--separate]\n"+
        "  [-D] [--double]\n[-h] [--help]\n\n"+
        " The short form switches ('-' except '-m') don't take parameters,\n"+
        " the long forms '--' require all listed parameters. (See methods\n"+
        " for a description of parameters.)\n\n"+
        " -s | --string forces input of strings otherwise integers are\n"+
        "               expected!\n"+
        " --timestep set timestep for recording history\n"+
        " -v | --verbose print additonal information\n"+
        " The default hash function is modulo table size M (default M=11).\n"+
        " -u | --universal select the universal has function\n\n"+
        " -L,-Q,-S select linear probing, quadratic probing, or separate\n"+
        "          chaining (default)\n"+
        " -D  selects double hashing, any subsequent -u | --universal modifies\n"+
        "     the secondary hash function, which should be specified\n"+
        "     differently from the primal hash function! (No checks!)\n\n"+
        " -h | --help displays this message\n\n"+
        "The program reads from standard input and inserts integers/words to\n"+
        "into the hash table.\n"+
        "The following \"words\" have a special meaning:\n"+
        " '.' quits,\n" +
        " '?' prints the contents of the hash table to standard output\n"+
        " '!' visualizes the history of the hash table in a new window\n\n"
        );
    System.exit(-1);
  }
 
  public HashtableExample(String args[]) {
    int m=11;
 
    HashFunction<Integer> h2=new IdentityHash();
    boolean haveDoubleHashing=false;
 
    for (int i=0;i<args.length;++i) {
      if (args[i].compareTo("-m")==0)
        m=Integer.parseInt(args[++i]);
      else if (args[i].compareTo("--timestep")==0)
        timestep=Integer.parseInt(args[++i]);
      else if (args[i].compareTo("-v")==0)
        ++verbose;
      else if (args[i].compareTo("--verbose")==0)
        verbose=Integer.parseInt(args[++i]);
      else if (args[i].compareTo("--string")==0 || args[i].compareTo("-s")==0)
        readIntegers=false;
      else if (args[i].compareTo("--help")==0 || args[i].compareTo("-h")==0)
        usage();
      else if (args[i].compareTo("-u")==0)
        hashfunction=new HashKey(new UniversalHash());
      else if (args[i].compareTo("--universal")==0) {
        HashFunction<Integer> h=
          new UniversalHash(
              Integer.parseInt(args[++i]), // a
              Integer.parseInt(args[++i]), // b
              Integer.parseInt(args[++i])  // p
              );
        if (haveDoubleHashing)
          h2=h;
        else
          hashfunction=new HashKey(h);
      }
      else if (args[i].compareTo("--separate")==0 || args[i].compareTo("-S")==0)
        collisionhandler=null;
      else if (args[i].compareTo("-L")==0)
        collisionhandler=new LinearProbing<Key>();
      else if (args[i].compareTo("--linear")==0)
        collisionhandler=new LinearProbing<Key>(Integer.parseInt(args[++i]));
      else if (args[i].compareTo("-Q")==0)
        collisionhandler=new QuadraticProbing<Key>();
      else if (args[i].compareTo("--quadratic")==0)
        collisionhandler=new QuadraticProbing<Key>
        (Integer.parseInt(args[++i]),Integer.parseInt(args[++i]));
      else if (args[i].compareTo("--double")==0 || args[i].compareTo("-D")==0) {
        haveDoubleHashing=true;
        collisionhandler=null;
      }
      else
        usage();
    }
 
    if (haveDoubleHashing)
      collisionhandler=new DoubleHashing<Key>(new HashKey(h2));
 
 
    System.err.println("> hash table with m="+m);
    System.err.println("> hash function="+hashfunction);
    System.err.println("> collision handling="+
        (collisionhandler==null ?
            "separate chaining" : collisionhandler.toString()
        ));
    if (readIntegers)
      System.err.println("> reading integers...\n");
    else
      System.err.println("> reading strings (HashString)...\n");
 
    hashtable=new SimpleHashtable<Key>(m,hashfunction,collisionhandler);
    hashtable.verbose=(verbose>0);
  }
 
  public void start() {
    SVGViewer viewer=null;
    time=0;
    hashtable.beginRecording();
 
    Scanner s=new Scanner(System.in);
    s.useDelimiter("\\s+");
 
    while (s.hasNext()) {
      String key=s.next();
      if (key.startsWith("."))
        break;
      else if (key.startsWith("?")) {
        if (key.startsWith("?svg:")) {
          hashtable.history_.renderSpySVG(
              new File(key.substring(5)+".svg"),new ColormapCount());
        }
        else if (key.startsWith("?tikz"))
          System.out.println(hashtable
                .history_.spyTikZ(true,new ColormapCount()));
        else
          System.out.println(hashtable);
      }
      else if (key.startsWith("!")) {
        if (viewer!=null)
          viewer.close();
        viewer=hashtable.showHistory();
      }
      else {
        Key k=readIntegers ? new Key(Integer.parseInt(key)) : new Key(key);
        if ((time++)%timestep==0)
          hashtable.nextTimeStep();
        hashtable.insert(k);
      }
    }
 
    if (viewer!=null)
      viewer.close();
    viewer=hashtable.showHistory();
    // TODO reuse viewer instance (write to same tempfile)
  }
  // TODO: catch exceptions (cycles while probing)
 
  public static void main(String args[]) {
    new HashtableExample(args).start();
  }
}