Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment