import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

class DSAHashTable<K,V> {

    private Set<Pair<K,V>>[] array;
    private int size = 0;

    DSAHashTable(int size) {
        createArray(size);
    }

    private void createArray(int size) {
        array = (Set<Pair<K,V>>[]) new Set<?>[size];

        for(int i = 0; i < size; i++)
            array[i] = new HashSet<Pair<K, V>>();
    }

    void put(K key, V value) {
        if(key == null)
            return;

        remove(key);

        Pair<K,V> pair = new Pair<K, V>(key, value);
        array[getIndexOf(key)].add(pair);
        size++;

        if(!isBigEnough())
            resize(array.length*2);
    }

    void remove(K key) {
        Iterator<Pair<K,V>> iterator = array[getIndexOf(key)].iterator();

        while(iterator.hasNext()) {
            if (iterator.next().key.equals(key)) {
                iterator.remove();
                size--;
                return;
            }
        }
    }

    V get(K key) {
        Set<Pair<K,V>> set = array[getIndexOf(key)];

        for(Pair<K,V> pair : set)
            if(pair.key.equals(key))
                return pair.value;

        return null;
    }

    Set<Pair<K,V>>[] getArray() {
        return array;
    }

    int getIndexOf(K key) {
        return key.hashCode() % array.length;
    }

    boolean isBigEnough() {
        return size <= array.length * 2;
    }

    void resize(int newSize) {
        Iterator<Pair<K,V>> iterator = iterator();
        Pair<K, V> pair;
        createArray(newSize);

        while(iterator.hasNext())
        {
            pair = iterator.next();
            array[getIndexOf(pair.key)].add(pair);
        }
    }

    Iterator<Pair<K,V>> iterator() {
        return new Iterator<Pair<K, V>>() {

            Iterator<Pair<K,V>> iterator;
            int offset = 0;
            Set<Pair<K, V>>[] array = DSAHashTable.this.array;

            @Override
            public boolean hasNext() {
                do {
                    if (iterator == null)
                        iterator = array[offset].iterator();

                    if (iterator.hasNext())
                        return true;

                    iterator = null;
                } while(++offset < array.length);

                return false;
            }

            @Override
            public Pair<K, V> next() {
                do {
                    if (iterator == null)
                        iterator = array[offset].iterator();

                    if (iterator.hasNext())
                        return iterator.next();

                    iterator = null;
                } while(++offset < array.length);

                throw new NoSuchElementException();
            }
        };
    }

}