using System;
using System.Collections.Generic;

namespace Hash
{
    class HashTable<KeyType, ValueType>
    {
        const int MINSIZE = 89;
        const int MASK = 0x7fffffff;

        public HashTable()
        {
            addedElements = 0;
            stepsSinceLastResize = 0;
            chain = AllocArray(MINSIZE);
        }

        public int Count
        {
            get { return addedElements; }
        }

        public void Remove(KeyType key)
        {
            int hash = key.GetHashCode() & MASK;
            int smallHash = hash % chain.Length;

            foreach (var item in chain[smallHash])
            {
                if (hash == (item.Key.GetHashCode() & MASK))
                {
                    if (key.Equals(item.Key))
                    {
                        chain[smallHash].Remove(item);
                        addedElements--;
                        TryResize();
                        return;
                    }
                }
            }
        }

        public ValueType Find(KeyType key)
        {
            int hash = key.GetHashCode() & MASK;
            int smallHash = hash % chain.Length;

            foreach (var item in chain[smallHash])
            {
                if (hash == (item.Key.GetHashCode() & MASK))
                {
                    if (key.Equals(item.Key))
                    {
                        return item.Value;
                    }
                }
            }

            throw new KeyNotFoundException();
        }

        public void Add(KeyType key, ValueType value)
        {
            try
            {
                Find(key);
            }
            catch (KeyNotFoundException)
            {
                int hash = key.GetHashCode() & MASK;
                int smallHash = hash % chain.Length;

                KeyValuePair<KeyType, ValueType> node = new KeyValuePair<KeyType, ValueType>(key, value);

                chain[smallHash].AddLast(node);
                addedElements++;
                TryResize();
            }
        }

        public void Replace(KeyType key, ValueType value)
        {
            int hash = key.GetHashCode() & MASK;
            int smallHash = hash % chain.Length;

            foreach (var item in chain[smallHash])
            {
                if (hash == (item.Key.GetHashCode() & MASK))
                {
                    if (key.Equals(item.Key))
                    {
                        chain[smallHash].Remove(item);
                        chain[smallHash].AddLast(new KeyValuePair<KeyType, ValueType>(key, value));
                        return;
                    }
                }
            }

            throw new KeyNotFoundException();
        }

        public ValueType this[KeyType key]
        {
            get
            {
                ValueType value;

                try
                {
                    value = Find(key);
                }
                catch
                {
                    throw;
                }

                return value;
            }

            set
            {
                try
                {
                    Replace(key, value);
                }
                catch
                {
                    Add(key, value);
                }
            }
        }

        private LinkedList<KeyValuePair<KeyType, ValueType>>[] AllocArray(int newSize)
        {
            LinkedList<KeyValuePair<KeyType, ValueType>>[] newChain = new LinkedList<KeyValuePair<KeyType, ValueType>>[newSize];

            for (int i = 0; i < newChain.Length; i++)
            {
                newChain[i] = new LinkedList<KeyValuePair<KeyType, ValueType>>();
            }

            return newChain;
        }

        private void ResizeArray(int newSize)
        {
            LinkedList<KeyValuePair<KeyType, ValueType>>[] newChain = AllocArray(newSize);
            LinkedList<KeyValuePair<KeyType, ValueType>>[] oldChain = chain;
            chain = newChain;
            addedElements = 0;

            foreach (var LinkedList in oldChain)
            {
                foreach (var item in LinkedList)
                {
                    int hash = item.Key.GetHashCode() & MASK;
                    int smallHash = hash % chain.Length;

                    chain[smallHash].AddLast(item);
                    addedElements++;
                }
            }

            stepsSinceLastResize = 0;
        }

        private void TryResize()
        {
            stepsSinceLastResize++;

            if (stepsSinceLastResize < chain.Length / 3)
            {
                return;
            }

            double ratio = addedElements / (double)chain.Length;

            if (ratio > 0.75)
            {
                int newSize = chain.Length * 2 + 1;

                ResizeArray(newSize);
            }

            if (ratio < 0.25 && chain.Length > MINSIZE)
            {
                int newSize = (chain.Length - 1) / 2;

                ResizeArray(newSize);
            }
        }

        private LinkedList<KeyValuePair<KeyType, ValueType>>[] chain;
        private int addedElements;
        private int stepsSinceLastResize;
    };

    class Program
    {
        static void Main(string[] args)
        {
            HashTable<string, int> ht = new HashTable<string, int>();

            ht.Add("edno", 1);
            ht.Add("edno", 2);
            ht.Add("dve", 2);

            string key = "a";
            char nextChar = 'b';

            for (int i = 0; i < 10000; i++)
            {
                ht.Add(key, i);

                ht[key] = i * 2;

                if (nextChar == 'z')
                {
                    nextChar = 'a';
                }
                if (key.Length == 27)
                {
                    key = string.Empty;
                }
                key = key + nextChar;


                nextChar++;

            }

            Console.WriteLine("end");
        }
    }
}