gistfile1.java

package hashash;


public class IntIntLinearProbing {

    private final int INITIAL_SIZE = 8;
    private final double DEFAULT_LOAD_FACTOR = .7;
    private int modulo = INITIAL_SIZE - 1;
    int[] keys;
    int[] values;
    int keyCount;
    int threshold = (int) (INITIAL_SIZE * DEFAULT_LOAD_FACTOR);

    public IntIntLinearProbing() {
        keys = new int[INITIAL_SIZE];
        values = new int[INITIAL_SIZE];
    }

    public IntIntLinearProbing(int size) {
        keys = new int[size];
        values = new int[size];
        threshold = (int) (size * DEFAULT_LOAD_FACTOR);
    }

    private int hash(int key) {
        return key & modulo;
    }

    private int locate(int key) {
        int slot = hash(key);
        while (true) {
            if (values[slot] == 0)
                return -slot;
            if (keys[slot] == key)
                return slot;
            slot = (slot + 1) & modulo;
        }
    }

    public void increment(int key) {
        increment(key, 1);
    }

    public int get(int key) {
        int l = locate(key);
        return l < 0 ? 0 : values[l];
    }

    public void decrement(int key) {
        increment(key, -1);
    }

    public void increment(int key, int amount) {
        int k = locate(key);
        if (k < 0) {
            k = -k;
            if (keyCount == threshold) {
                expand();
            }
            values[k] = amount;
            keys[k] = key;
            keyCount++;
        } else {
            values[k] += amount;
            if (values[k] == 0)
                keyCount--;

        }
    }

    public void remove(int key) {
        int k = locate(key);
        if (k < 0)
            return;
        values[k] = 0;
        keyCount--;
    }

    private void expand() {
        IntIntLinearProbing h = new IntIntLinearProbing(values.length * 2);
        for (int i = 0; i < keys.length; i++) {
            if (values[i] != 0) {
                h.set(keys[i], values[i]);
            }
        }
        this.values = h.values;
        this.keys = h.keys;
        this.keyCount = h.keyCount;
        this.modulo = h.modulo;
    }

    private void set(int key, int value) {
        int loc = locate(key);
        if (loc > 0) {
            values[loc] = value;
            return;
        }
        if (keyCount == threshold) {
            expand();
        }
        loc = -loc;
        keys[loc] = key;
        values[loc] = value;
        keyCount++;
    }


    public static void main(String[] args) {
        int[] testVals = new int[10000];
        for (int i = 0; i < testVals.length; i++) {
            testVals[i] = i;
        }

        for (int i = 0; i < 100; i++) {
            IntIntLinearProbing k = new IntIntLinearProbing();
            for (int testVal : testVals) {
                k.set(testVal, 1);
                System.out.println("testVal = " + testVal);
            }
            for (int testVal : testVals) {
                k.get(testVal);
            }
        }
    }


}