private static void generatePivots(String[] values,int start,int length,int[] pivots,int pivotIndex){
  final int capacity=Integer.highestOneBit(length - 1) << 1;
  final int depth=Integer.numberOfTrailingZeros(capacity);
  pivots[pivotIndex << 1]=depth;
  pivots[(pivotIndex << 1) + 1]=length;
  pivotIndex++;
  for (int i=0; i < depth; i++) {
    int step=capacity >> i;
    for (int j=(1 << (depth - i - 1)) - 1; j < capacity; j+=step) {
      final int part;
      final int comp;
      if (j >= length - 1) {
        part=Integer.MIN_VALUE;
        comp=0;
      }
 else {
        final String v1=values[start + j];
        final String v2=values[start + j + 1];
        final int l1=v1.length();
        final int l2=v2.length();
        if (l1 == l2) {
          int tPart=-1;
          int tComp=-1;
          for (int k=0; k < l1; k++) {
            final char c1=v1.charAt(k);
            final char c2=v2.charAt(k);
            if (c1 == c2)             continue;
            if (c1 < c2) {
              tPart=k;
              tComp=c1;
            }
 else {
              throw new IllegalStateException();
            }
            break;
          }
          if (tPart == -1)           throw new IllegalArgumentException("duplicate value: " + v1);
          part=tPart;
          comp=tComp;
        }
 else {
          part=-1;
          comp=l1;
        }
      }
      pivots[pivotIndex << 1]=part;
      pivots[(pivotIndex << 1) + 1]=comp;
      pivotIndex++;
    }
  }
}

private static void generatePivots ( String [ ] values , int start , int length , int [ ] pivots , int pivotIndex ) { final int capacity = Integer . highestOneBit ( length - 1 ) << 1 ; final int depth = Integer . numberOfTrailingZeros ( capacity ) ; pivots [ pivotIndex << 1 ] = depth ; pivots [ ( pivotIndex << 1 ) + 1 ] = length ; pivotIndex ++ ; for ( int i = 0 ; i < depth ; i ++ ) { int step = capacity > > i ; for ( int j = ( 1 << ( depth - i - 1 ) ) - 1 ; j < capacity ; j += step ) { final int part ; final int comp ; if ( j >= length - 1 ) { part = Integer . MIN_VALUE ; comp = 0 ; } else { final String v1 = values [ start + j ] ; final String v2 = values [ start + j + 1 ] ; final int l1 = v1 . length ( ) ; final int l2 = v2 . length ( ) ; if ( l1 == l2 ) { int tPart = - 1 ; int tComp = - 1 ; for ( int k = 0 ; k < l1 ; k ++ ) { final char c1 = v1 . charAt ( k ) ; final char c2 = v2 . charAt ( k ) ; if ( c1 == c2 ) continue ; if ( c1 < c2 ) { tPart = k ; tComp = c1 ; } else { throw new IllegalStateException ( ) ; } break ; } if ( tPart == - 1 ) throw new IllegalArgumentException ( "duplicate value: " + v1 ) ; part = tPart ; comp = tComp ; } else { part = - 1 ; comp = l1 ; } } pivots [ pivotIndex << 1 ] = part ; pivots [ ( pivotIndex << 1 ) + 1 ] = comp ; pivotIndex ++ ; } } }
builds a ( typically v . small ) decision tree for distinguishing strings that share the same hash value .
