static <K>void generate(ArrayList<K> list,UniversalHash<K> hash,int level,int seed,ByteArrayOutputStream out){
  int size=list.size();
  if (size <= 1) {
    out.write(size);
    return;
  }
  if (level > 32) {
    throw new IllegalStateException("Too many recursions; " + " incorrect universal hash function?");
  }
  if (size <= MAX_SIZE) {
    int maxOffset=MAX_OFFSETS[size];
    int[] hashes=new int[size];
    for (int i=0; i < size; i++) {
      hashes[i]=hash.hashCode(list.get(i),level,seed);
    }
    int testSize=size;
    if (size >= SPEEDUP) {
      testSize++;
      maxOffset/=testSize;
    }
    nextOffset:     for (int offset=0; offset < maxOffset; offset++) {
      int bits=0;
      for (int i=0; i < size; i++) {
        int x=hashes[i];
        int h=hash(x,level,offset,testSize);
        if ((bits & (1 << h)) != 0) {
          continue nextOffset;
        }
        bits|=1 << h;
      }
      if (size >= SPEEDUP) {
        int pos=Integer.numberOfTrailingZeros(~bits);
        writeSizeOffset(out,size,offset * (size + 1) + pos);
      }
 else {
        writeSizeOffset(out,size,offset);
      }
      return;
    }
  }
  int split;
  if (size > 57 * DIVIDE) {
    split=size / (36 * DIVIDE);
  }
 else {
    split=(size - 47) / DIVIDE;
  }
  split=Math.max(2,split);
  boolean isRoot=level == 0;
  ArrayList<ArrayList<K>> lists;
  do {
    lists=new ArrayList<ArrayList<K>>(split);
    for (int i=0; i < split; i++) {
      lists.add(new ArrayList<K>(size / split));
    }
    for (int i=0; i < size; i++) {
      K x=list.get(i);
      ArrayList<K> l=lists.get(hash(x,hash,level,seed,0,split));
      l.add(x);
      if (isRoot && split >= SPLIT_MANY && l.size() > 36 * DIVIDE * 10) {
        level++;
        lists=null;
        break;
      }
    }
  }
 while (lists == null);
  if (split >= SPLIT_MANY) {
    out.write(SPLIT_MANY);
  }
  writeVarInt(out,split);
  boolean multiThreaded=isRoot && list.size() > 1000;
  list.clear();
  list.trimToSize();
  if (multiThreaded) {
    generateMultiThreaded(lists,hash,level,seed,out);
  }
 else {
    for (    ArrayList<K> s2 : lists) {
      generate(s2,hash,level + 1,seed,out);
    }
  }
  if (isRoot && split >= SPLIT_MANY) {
    out.write(level);
  }
}

static < K > void generate ( ArrayList < K > list , UniversalHash < K > hash , int level , int seed , ByteArrayOutputStream out ) { int size = list . size ( ) ; if ( size <= 1 ) { out . write ( size ) ; return ; } if ( level > 32 ) { throw new IllegalStateException ( "Too many recursions; " + " incorrect universal hash function?" ) ; } if ( size <= MAX_SIZE ) { int maxOffset = MAX_OFFSETS [ size ] ; int [ ] hashes = new int [ size ] ; for ( int i = 0 ; i < size ; i ++ ) { hashes [ i ] = hash . hashCode ( list . get ( i ) , level , seed ) ; } int testSize = size ; if ( size >= SPEEDUP ) { testSize ++ ; maxOffset /= testSize ; } nextOffset : for ( int offset = 0 ; offset < maxOffset ; offset ++ ) { int bits = 0 ; for ( int i = 0 ; i < size ; i ++ ) { int x = hashes [ i ] ; int h = hash ( x , level , offset , testSize ) ; if ( ( bits & ( 1 << h ) ) != 0 ) { continue nextOffset ; } bits |= 1 << h ; } if ( size >= SPEEDUP ) { int pos = Integer . numberOfTrailingZeros ( ~ bits ) ; writeSizeOffset ( out , size , offset * ( size + 1 ) + pos ) ; } else { writeSizeOffset ( out , size , offset ) ; } return ; } } int split ; if ( size > 57 * DIVIDE ) { split = size / ( 36 * DIVIDE ) ; } else { split = ( size - 47 ) / DIVIDE ; } split = Math . max ( 2 , split ) ; boolean isRoot = level == 0 ; ArrayList < ArrayList < K > > lists ; do { lists = new ArrayList < ArrayList < K > > ( split ) ; for ( int i = 0 ; i < split ; i ++ ) { lists . add ( new ArrayList < K > ( size / split ) ) ; } for ( int i = 0 ; i < size ; i ++ ) { K x = list . get ( i ) ; ArrayList < K > l = lists . get ( hash ( x , hash , level , seed , 0 , split ) ) ; l . add ( x ) ; if ( isRoot && split >= SPLIT_MANY && l . size ( ) > 36 * DIVIDE * 10 ) { level ++ ; lists = null ; break ; } } } while ( lists == null ) ; if ( split >= SPLIT_MANY ) { out . write ( SPLIT_MANY ) ; } writeVarInt ( out , split ) ; boolean multiThreaded = isRoot && list . size ( ) > 1000 ; list . clear ( ) ; list . trimToSize ( ) ; if ( multiThreaded ) { generateMultiThreaded ( lists , hash , level , seed , out ) ; } else { for ( ArrayList < K > s2 : lists ) { generate ( s2 , hash , level + 1 , seed , out ) ; } } if ( isRoot && split >= SPLIT_MANY ) { out . write ( level ) ; } }
generate the perfect hash function data from the given set of integers .
