class ConcurrentIntHashMap {

    private transient Entry table[];

    private transient int count;

    private int threshold;

    private float loadFactor;

    private static class Entry {

        int hash;
        int key;
        Object value;
        Entry next;
        ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        Lock readLock = readWriteLock.readLock();
        Lock writeLock = readWriteLock.writeLock();

        protected Entry(int hash, int key, Object value, Entry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public int getHash() {
            return hash;
        }

        public Lock getWriteLock() {
            return writeLock;
        }

        public Lock getReadLock() {
            return readLock;
        }
    }

    public ConcurrentIntHashMap() {
        this(20, 0.75f);
    }

    public ConcurrentIntHashMap(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    public ConcurrentIntHashMap(int initialCapacity, float loadFactor) {
        super();
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        if (loadFactor <= 0) {
            throw new IllegalArgumentException("Illegal Load: " + loadFactor);
        }
        if (initialCapacity == 0) {
            initialCapacity = 1;
        }

        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int) (initialCapacity * loadFactor);
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }

        Entry tab[] = table;
        for (int i = tab.length; i-- > 0; ) {
            Entry e = tab[i];
            if (e != null) {
                e.getReadLock().lock();
                try {

                    for (; e != null; e = e.next) {
                        if (e.value.equals(value)) {
                            return true;
                        }
                    }
                } finally {
                    e.getReadLock().unlock();
                }
            }
        }
        return false;
    }

    public boolean containsValue(Object value) {
        return contains(value);
    }

    public boolean containsKey(int key) {
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        Entry e = tab[index];
        if (e != null) {
            e.getReadLock().lock();
            try {

                for (; e != null; e = e.next) {
                    if (e.hash == hash) {
                        return true;
                    }
                }
            } finally {
                e.getReadLock().unlock();
            }
        }
        return false;
    }

    public Object get(int key) {
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        Entry e = tab[index];
        if (e != null) {
            e.getReadLock().lock();
            try {
                for (; e != null; e = e.next) {
                    if (e.hash == hash) {
                        return e.value;
                    }
                }
            } finally {
                e.getReadLock().unlock();
            }
        }
        return null;
    }

    protected synchronized void rehash() {
        int oldCapacity = table.length;
        Entry oldMap[] = table;

        int newCapacity = oldCapacity * 2 + 1;
        Entry newMap[] = new Entry[newCapacity];

        threshold = (int) (newCapacity * loadFactor);
        table = newMap;

        for (int i = oldCapacity; i-- > 0; ) {
            for (Entry old = oldMap[i]; old != null; ) {
                Entry e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = newMap[index];
                newMap[index] = e;
            }
        }
    }

    public Object put(int key, Object value) {
        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        Entry e = tab[index];
        if (e != null) {
            e.getWriteLock().lock();
            try {

                for (; e != null; e = e.next) {
                    if (e.hash == hash) {
                        Object old = e.value;
                        e.value = value;
                        return old;
                    }
                }
            } finally {
                e.getWriteLock().unlock();
            }
        }

        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        Entry newEntry = new Entry(hash, key, value, tab[index]);
        tab[index] = newEntry;
        count++;
        return null;
    }

    public Object remove(int key) {
        Entry tab[] = table;
        int hash = key;
        int index = (hash & 0x7FFFFFFF) % tab.length;
        Entry e = tab[index];
        if (e != null) {
            e.getWriteLock().lock();
            try {
                for (Entry prev = null; e != null; prev = e, e = e.next) {
                    if (e.hash == hash) {
                        if (prev != null) {
                            prev.next = e.next;
                        } else {
                            tab[index] = e.next;
                        }
                        count--;
                        Object oldValue = e.value;
                        e.value = null;
                        return oldValue;
                    }
                }
            } finally {
                e.getWriteLock().unlock();
            }
        }
        return null;
    }

    public synchronized void clear() {
        Entry tab[] = table;
        for (int index = tab.length; --index >= 0; ) {
            tab[index] = null;
        }
        count = 0;
    }
}