import java.util.*;

public class LinearProbing<T> {
    private static final int DEFAULT_TABLE_SIZE = 101;
    private HashEntry<T>[] array;
    private int currentSize;

    public LinearProbing() { this(DEFAULT_TABLE_SIZE); }

    public LinearProbing(int size) {
        array = new HashEntry[size];
        currentSize = 0;
    }

    public boolean contains(T element) { return array[findPos(element)] != null; }

    private int findPos(T element) {
        int currentPos = myhash(element);
        int offset = 1;
        while (array[currentPos] != null && !array[currentPos].element.equals(element)) {
            currentPos += offset;
            offset++;
            currentPos %= array.length;
        }
        return currentPos;
    }

    public void insert(T element) { array[findPos(element)] = new HashEntry<>(element, true); }

    public void remove(T element) { array[findPos(element)].isActive = false; }

    private int myhash(T element) {
        int hashValue = element.hashCode() % array.length;
        return hashValue < 0 ? hashValue + array.length : hashValue;
    }

    private static class HashEntry<T> {
        public T element;
        public boolean isActive;

        public HashEntry(T e, boolean i) { element = e; isActive = i; }
    }

    public void showAll() {
        for (HashEntry each : array)
            System.out.print((each != null ? each.element : "None") + " ");
    }

    public static void main(String[] args) {
        LinearProbing<Integer> sc = new LinearProbing<>(10);
        sc.insert(89); sc.insert(18); sc.insert(49); sc.insert(58); sc.insert(69);
        sc.showAll();
    }
}