using System;

using System.Linq;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var hashTable = new DynamicHashtable<int>();

        hashTable.Add("one", 1);

        hashTable.Add("two", 2);

        hashTable.Add("three", 3);

        hashTable.Add("four", 4);

        hashTable.PrintAll();

        var one = hashTable.Get("one");

        var two = hashTable.Get("two");

        var three = hashTable.Get("three");

        var four = hashTable.Get("four");

        Console.WriteLine($"One: {one}");

        Console.WriteLine($"Two: {two}");

        Console.WriteLine($"Three: {three}");

        Console.WriteLine($"Four: {four}");

    }

}

​

public class Node<T>

{

    public int Hash {get;set;}

    public string Key {get;set;}

    public T Value {get;set;}

    public Node<T> Next {get;set;}

}

​

public class DynamicHashtable<T>

{

    private readonly IList<Node<T>> buckets;

    public DynamicHashtable()

    {

        buckets = new List<Node<T>>();

    }

    public void PrintAll()

    {

        foreach(var head in buckets)

        {

            var currentHead = head;

            if(currentHead == null)

            {

                Console.WriteLine("Nothing found in this bucket");

                continue;

            }

            Console.WriteLine($"Head Element {currentHead.Key} : {currentHead.Value}");

            while(currentHead.Next != null)

            {

                currentHead = currentHead.Next;

                Console.WriteLine($"Child Element {currentHead.Key} : {currentHead.Value}");

            }

        }

    }

    public void Add(string key, T toAdd)

    {

        if(!ValidateKey(key))

        {

            throw new Exception("Cannot use an empty key!");

        }

        var bucketHash = GetBucketHash(key);

        var targetBucket = buckets.SingleOrDefault(b => b.Hash == bucketHash);

        var newNode = new Node<T> 

        {

            Hash = bucketHash,

            Key = key,

            Value = toAdd,

            Next = null

        };

        if(targetBucket == null)

        {

            // brand new key, start a new bucket

            Console.WriteLine($"Brand new key {bucketHash} for value: {toAdd}");

            buckets.Add(newNode);

        }

        else

        {

            Console.WriteLine($"Existing key {bucketHash} for value: {toAdd}");

            var lastChild = GetLastBucketChild(targetBucket);

            lastChild.Next = newNode;

        }

    }

    public T Get(string key)

    {

        if(!ValidateKey(key))

        {

            throw new Exception("Cannot use an empty key!");

        }

        var node = GetNodeByKey(key);

        if(node == null)

        {

            throw new Exception("Cannot find any node by that key!");

        }

        return node.Value;

    }

    private Node<T> GetNodeByKey(string key)

    {

        var bucketHash = GetBucketHash(key);

        var currentNode = buckets[bucketHash];

​

        while(currentNode != null)

        {

            if(currentNode.Key == key)

            {

                return currentNode;

            }

            currentNode = currentNode.Next;

        }

        return null;

    }

    private Node<T> GetLastBucketChild(Node<T> bucketStart)

    {

        var lastNode = bucketStart;

        while(lastNode.Next != null)

        {

            lastNode = lastNode.Next;

        }

        return lastNode;

    }

    private int GetBucketHash(string key)

    {

        Console.WriteLine($"Provided key: {key}; hashcode: {key.GetHashCode()}; buckets length: {buckets.Count}");

        var computedHashcode = buckets.Count == 0 ? 0 : Math.Abs(key.GetHashCode() % buckets.Count);

        Console.WriteLine($"Provided key: {key} computed hashcode: {computedHashcode}");

        return computedHashcode;

    }

    private bool ValidateKey(string key)

    {

        return !string.IsNullOrWhiteSpace(key);

    }

}