namespace HashTable
{
    class HashTable<K, V>
    {
        private const int DEFAULT_CAPACITY = 16;
        private const double loadFactor = 0.75;
        private int CURRENT_CAPACITY;
        private int size;
        public LinkedList<KeyValuePair<K, V>>[] keys;

        public HashTable(int capacity)
        {
            keys = new LinkedList<KeyValuePair<K, V>>[capacity];
            this.size = 0;
            CURRENT_CAPACITY = capacity;
        }

        public HashTable()
            : this(DEFAULT_CAPACITY)
        {
        }

        public LinkedList<K> Keys
        {
            get
            {
                LinkedList<K> result = new LinkedList<K>();
                for (int pos = 0; pos < keys.Length; pos++)
                {
                    if (keys[pos] != null)
                    {
                        foreach (var item in keys[pos])
                        {
                            result.AddLast(item.Key);
                        }
                    }
                }
                return result;
            }
        }

        public int Count
        {
            get { return size; }
        }

        public V this[K argument]
        {
            get { return this.Find(argument); }

            set
            {
                this.Remove(argument);
                this.Add(argument, value);
            }
        }


        public void Add(K key, V value)
        {
            KeyValuePair<K, V> newPair = new KeyValuePair<K, V>(key, value);
            int hash = key.GetHashCode() % CURRENT_CAPACITY;
            if (keys[hash] == null)
            {
                keys[hash] = new LinkedList<KeyValuePair<K, V>>();
            }
            keys[hash].AddLast(newPair);
            size++;
            if (loadFactor <= size / CURRENT_CAPACITY)
            {
                Resize();
            }
        }

        private void Resize()
        {
            CURRENT_CAPACITY *= 2;
            HashTable<K, V> container = new HashTable<K, V>(CURRENT_CAPACITY);
            for (int pos = 0; pos < keys.Length; pos++)
            {
                if (keys[pos] != null)
                {
                    foreach (var pair in keys[pos])
                    {
                        container.Add(pair.Key, pair.Value);
                    }
                }
            }
            this.keys = container.keys;
        }

        public V Find(K key)
        {
            int position = key.GetHashCode();
            foreach (var pair in keys[position])
            {
                if (pair.Key.Equals(key))
                {
                    return pair.Value;
                }
            }
            return default(V);
        }

        public bool Remove(K key)
        {
            int hash = key.GetHashCode() % CURRENT_CAPACITY;
            if (keys[hash] != null && keys[hash].Remove(new KeyValuePair<K, V>(key, default(V))))
                    {
                        this.size--;
                        return true;
                    }
            return false;
        }
    }
}