hashTable

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace HashTableProject
{
  public class StringHashTable<T> : IDictionary<string, T>
  {
    private const double MaxLoadFactor = 0.75;
    private readonly List<string> _keys;
    private int _bucketCount;
    private List<KeyValuePair<string, T>>[] _buckets;

    public StringHashTable() : this(500)
    {
    }

    private StringHashTable(int capacity)
    {
      _keys = new List<string>();
      _buckets = new List<KeyValuePair<string, T>>[capacity];
    }

    #region Implementation of IEnumerable

    public IEnumerator<KeyValuePair<string, T>> GetEnumerator()
    {
      return _buckets.Where(list => list != null).SelectMany(list => list).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
      return GetEnumerator();
    }

    #endregion

    #region Implementation of ICollection<KeyValuePair<string,T>>

    public void Add(KeyValuePair<string, T> item)
    {
      Add(item.Key, item.Value);
    }

    public void Clear()
    {
      throw new NotImplementedException();
    }

    public bool Contains(KeyValuePair<string, T> item)
    {
      throw new NotImplementedException();
    }

    public void CopyTo(KeyValuePair<string, T>[] array, int arrayIndex)
    {
      throw new NotImplementedException();
    }

    public bool Remove(KeyValuePair<string, T> item)
    {
      throw new NotImplementedException();
    }

    public int Count { get; private set; }

    public bool IsReadOnly
    {
      get { return false; }
    }

    #endregion

    #region Implementation of IDictionary<string,T>

    public bool ContainsKey(string key)
    {
      return _keys.Contains(key);
    }

    public void Add(string key, T value)
    {
      if (_keys.Contains(key))
      {
        throw new ArgumentException("Dublicate key", "key");
      }

      if (LoadFactor >= MaxLoadFactor)
      {
        Resize();
      }

      int index = GetKeyIndex(key);

      if (_buckets[index] == null)
      {
        _buckets[index] = new List<KeyValuePair<string, T>>();
        _bucketCount++;
      }

      _buckets[index].Add(new KeyValuePair<string, T>(key, value));
      _keys.Add(key);

      Count++;
    }

    public bool Remove(string key)
    {
      if (!ContainsKey(key))
      {
        return true;
      }

      int index = GetKeyIndex(key);
      int valueIndex = _buckets[index].FindIndex(pair => pair.Key == key);

      _buckets[index].RemoveAt(valueIndex);
      _keys.Remove(key);

      return true;
    }

    public bool TryGetValue(string key, out T value)
    {
      if (!ContainsKey(key))
      {
        value = default(T);
        return false;
      }

      int index = GetKeyIndex(key);
      value = _buckets[index].First(pair => pair.Key == key).Value;

      return true;
    }

    public T this[string key]
    {
      get
      {
        T value;
        if (!TryGetValue(key, out value))
        {
          throw new KeyNotFoundException();
        }

        return value;
      }

      set { throw new NotImplementedException(); }
    }

    public ICollection<string> Keys
    {
      get { return _keys; }
    }

    public ICollection<T> Values
    {
      get
      {
        return _buckets.Where(list => list != null)
                       .SelectMany(list => list.Select(pair => pair.Value))
                       .ToList();
      }
    }

    #endregion

    private double LoadFactor
    {
      get { return (double) _bucketCount/Capacity; }
    }

    private int Capacity
    {
      get { return _buckets.Length; }
    }

    private void Resize()
    {
      var newSize = (int) (Capacity*1.5);
      var newHashTable = new StringHashTable<T>(newSize);

      foreach (var pair in this)
      {
        newHashTable.Add(pair);
      }

      _buckets = newHashTable._buckets;
      _bucketCount = newHashTable._bucketCount;
    }

    private int GetKeyIndex(string key)
    {
      ulong hash = key.Aggregate((ulong) 5381, (i, c) => (i << 5) + i + c);
      return (int) (hash%(ulong) Capacity);
    }
  }
}