CSI 2110 Hashing

DoubleHash.java

public class DoubleHash {

    public static void main(String[] args) {
        DoubleHash map = new DoubleHash(17);
        map.insert( 17 );
        map.insert( 2 );
        map.insert( 8 );
        map.insert( 19 );
        map.insert( 15 );
        map.remove( 19 );
        map.insert( 26 );
        map.insert( 51 );
        map.remove( 8 );
        map.insert( 36 );
        map.search( 25 );
        map.insert( 19 );
    }


    int n;
    Integer[] array;

    public DoubleHash(int n) {
        this.n = n;
        array = new Integer[n];
    }

    void insert(int key){
        System.out.printf("\nINSERT %d\ntable   = %s\n",key, toString());

        for(int j = 0; j < n; j++){
            int hash = hashHJ( key, j );

            Integer value = probe( hash );

            if( value == null ){
                System.out.printf("set cell %d to value %d\n", hash, key);
                array[hash] = Integer.valueOf( key );;
                System.out.printf("table   = %s\n", toString());
                return;
            }
            System.out.printf( "found %s but looking for an empty cell, iterate!\n", value.toString() );
        }
        System.out.println("HASH FULL!");
    }

    void remove(int key){
        System.out.printf("\nREMOVE %d\ntable  = %s\n",key, toString());
        for(int j = 0; j < n; j++){
            int hash = hashHJ( key, j );
            Integer value = probe( hash );
            if( value == null ){
                System.out.printf("NO SUCH ELEMENT %d\n", key);
                return;
            } else if ( value.equals( key )){
                System.out.printf("remove value %d from cell %d\n", key, hash);
                array[hash] = null;
                break;
            }
            System.out.printf( "found %s but looking for %d, iterate!", value.toString(), key );
        }
        System.out.printf("table   = %s\n", toString());
    }

    void search(int key){
        System.out.printf("\nSEARCH %d\ntable   = %s\n",key, toString());
        for(int j = 0; j < n; j++){
            int hash = hashHJ( key, j );
            Integer value = probe( hash );
            if( value == null ){
                System.out.printf("NO SUCH ELEMENT %d\n", key);
                return;
            } else if ( value.equals( key )){
                System.out.printf("Found value %d in cell %d!!\n", key, hash);
                break;
            }
            System.out.printf( "found %s but looking for %d, iterate!", value.toString(), key );
        }

        return;
    }

    Integer probe(int index){
        System.out.printf("probing cell %d; contains %s\n",
                index,
                array[index] == null? "nothing": array[index].toString());
        return array[index];
    }

    int hashHJ(int k, int j){
        System.out.printf("h_%d(%d) = [h(%d) + %dd(%d)] mod %d\n",j,k,k,j,k,n);
        int h = primaryHashH( k );
        int d = secondaryHashD( k );
        int hash = (h + j*d) % n;
        System.out.printf("h_%d(%d) = %d\n",j,k,hash );
        return hash;
    }

    int primaryHashH(int k){
        System.out.printf("h(%d)   = %d\n", k, k % n);
        return k % n;
    }

    int secondaryHashD(int k){
        System.out.printf("d(%d)   = %d\n", k, k / n);
        return k / n;
    }


    public String toString() {
        StringBuilder b = new StringBuilder();
        b.append( '[' );
        b.append( array[0] == null ? "  ": array[0].toString() );
        if(array.length > 1){
            for(int i = 1; i < array.length; i ++){
                b.append( ',' );
                String value = array[i] == null ? "  ": array[i].toString();
                if(value.length() == 1) value = " " + value;
                b.append( value );
            }
        }
        b.append( ']' );
        return b.toString();
    }

}