import java.util.Random;

public class Lab22 {
    static int probe = 0;

    public static void main(String args[]){
        int count = 0;
        while(count < 100){
            int m = 100000;
            Object[] T = new Object[m];
            int[] lup = new int[m];
            int[] ldown = new int[m];
            Random rand = new Random();
            for(int i = 0; i < 89999; i++){
                int value = rand.nextInt(100000);
                insert(T, value, lup, ldown);
            }
            probe = 0;
            insert(T, rand.nextInt(100000), lup, ldown);
            System.out.println(probe);
            count++;
        }
    }

    protected static int h(int x, Object[] T){
        return Math.floorMod(x, T.length);
    }

    protected static void insert(Object[] T, int x, int[] lup, int[] ldown) {
        int j = h(x, T);
        if (T[j] == null) {
            T[j] = x;
        } else {
            if (ldown[j] <= lup[j]) {
                hashInsertDown(T, x);
                ldown[j]++;
            } else {
                hashInsertUp(T,x);
                lup[j]++;
            }
        }
    }

    protected static void hashInsertDown(Object T[], int x) {
        for(int i = 0; i < T.length; i++) {
            int j = Math.floorMod(h(x, T) + i, T.length);
            if (T[j] == null){
                T[j] = x;
                return;
            }
            probe++;
        }
        System.out.println("Element "+x+" går ej att sätta in");
    }

    protected static void hashInsertUp(Object T[], int x) {
        for(int i = 0; i < T.length; i++){
            int j = Math.floorMod(h(x, T) - i, T.length);
            if (T[j] == null){
                T[j] = x;
                return;
            }
            probe++;
        }
        System.out.println("Element "+x+" går ej att sätta in");
    }
}