package utils;

import java.util.*;

// implements an m-way universal hash
public class UniversalHash {
  static Random r = new Random();
  int[] a; int m;

  public UniversalHash(int m) {
    this.m=m;
    int size = (int)(Math.ceil(Math.log(Integer.MAX_VALUE)/Math.log(m)));
    a = new int[size];
    for(int i=0;i<a.length;i++) a[i] = r.nextInt(m);
  }
    // return the hash for a key
  int hash(int k) {
    int total = 0;
    for(int i=0;i<a.length;i++) {
      total += a[i]*(k%m);
      k/=m;
    }
    return total%m;
  }
}
