using System;

using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

public class MyDictionary<TKey, UValue> : IEnumerable<KeyValuePair<TKey, UValue>>

{

    private const int DefaultCapacity = 100000;

    private LinkedList<KeyValuePair<TKey, UValue>>[] _values;

    private int _capacity;

​

    public MyDictionary()

    {

        _values = new LinkedList<KeyValuePair<TKey, UValue>>[DefaultCapacity];

    }

​

    public int Count => _values.Length;

​

    public void Add(TKey key, UValue value)

    {

        AddToDictionary(this, key, value);

​

        if (Count < _capacity)

        {

            ResizeCollection();

        }

    }

​

    public bool ContainsKey(TKey key)

    {

        var keyHash = GetHashValue(key);

        var keyValue = _values[keyHash];

        return keyValue != null && keyValue.Any(p => p.Key.Equals(key));

    }

​

    public UValue GetValue(TKey key)

    {

        var keyHash = GetHashValue(key);

        var keyValue = _values[keyHash];

        return keyValue != null

            ? keyValue.First(m => m.Key.Equals(key)).Value

            : default(UValue);

    }

​

    public UValue this[TKey key]

    {

        get

        {

            var keyHash = GetHashValue(key);

            var keyValue = _values[keyHash];

            return keyValue != null

                ? keyValue.FirstOrDefault(p => p.Key.Equals(key)).Value

                : throw new KeyNotFoundException("Keys not found!");

        }

        set

        {

            var keyHash = GetHashValue(key);

            var keyValue = _values[keyHash];

            keyValue = new LinkedList<KeyValuePair<TKey, UValue>>();

            keyValue.AddLast(new KeyValuePair<TKey, UValue>(key, value));

        }

    }

​

    IEnumerator IEnumerable.GetEnumerator()

    {

        return GetEnumerator();

    }

​

    public IEnumerator<KeyValuePair<TKey, UValue>> GetEnumerator()

    {

        return _values

            .Where(v => v != null)

            .SelectMany(v => v)

            .GetEnumerator();

    }

​

    private int GetHashValue(TKey key)

    {

        return Math.Abs(key.GetHashCode()) % _values.Length;

    }

​

    private void ResizeCollection()

    {

        var oldValues = _values;

        _values = new LinkedList<KeyValuePair<TKey, UValue>>[oldValues.Length * 2];

        foreach (var value in oldValues

            .Where(v => v != null)

            .SelectMany(v => v))

            AddToDictionary(this, value.Key, value.Value);

    }

​

    private static void AddToDictionary(MyDictionary<TKey, UValue> dico, TKey key, UValue val)

    {

        var keyHash = dico.GetHashValue(key);

        if (dico._values[keyHash] == null)

        {

            dico._values[keyHash] = new LinkedList<KeyValuePair<TKey, UValue>>();

        }

        var keyPresent = dico._values[keyHash].Any(p => p.Key.Equals(key));

        if (keyPresent)

        {

            throw new Exception("Duplicate key has been found!");

        }

        var newValue = new KeyValuePair<TKey, UValue>(key, val);

        dico._values[keyHash].AddLast(newValue);

        dico._capacity++;

    }

}

public class Program

{

    public static void Main()

    {

        var books = new MyDictionary<string, Book>();

​

        //Add

        Console.WriteLine("[TEST] Add books");

        books.Add("Joe", new Book("Essential C# 8.0", 2023));

        books.Add("Jane", new Book("Visual C Sharp Step by Step", 2018));

        books.Add("Mindy", new Book("Professional C 2012 and .NET 4.5", 2014));

        foreach (var book in books)

            Console.WriteLine(book.ToString());

        Console.WriteLine("");

        //Add existing

        Console.WriteLine("[TEST] Add existing book");

        var exceptionThrown = false;

        try

        {

            books.Add("Joe", new Book("Essential C# 8.0", 2023));

        }

        catch(Exception)

        {

            exceptionThrown = true;

        }

        if (exceptionThrown)

            Console.WriteLine("Exception was thrown");

        else

            throw new Exception("Exception was not thrown");

        Console.WriteLine("");

​

        //Looking for item

        Console.WriteLine("[TEST] Looking for Joe book");

        var book1 = books["Joe"];

        Console.WriteLine(book1.ToString());

        Console.WriteLine("");

        //Contains key

        Console.WriteLine("[TEST] Contains Jane book");

        Console.WriteLine(books.ContainsKey("Jane"));

        Console.WriteLine("");

        //Replace item

        Console.WriteLine("[TEST] Replace Mindy book");

        var book2 = books["Mindy"];

        Console.WriteLine($"Current book: {book2}");

        books["Mindy"] = new Book("How to Code like a God", 2025);

        book2 = books["Mindy"];

        Console.WriteLine($"New  book: {book2}");

        Console.WriteLine("");

​

​

        // Perf

        Console.WriteLine("[TEST] Perf");

        var stopwatch = new Stopwatch();

        var nbrOfIteration = 100000;

        var ids = new MyDictionary<string, string>();

​

        stopwatch.Start();

        for (var i = 0; i < nbrOfIteration; ++i)

        {

            var id = Guid.NewGuid().ToString();

            ids.Add(id, id);

        }

        stopwatch.Stop();

        Console.WriteLine($"Time to add {nbrOfIteration} items: {stopwatch.Elapsed}");

        stopwatch.Reset();

​

        stopwatch.Start();

        foreach(var idKey in ids)

        {

            var idVal = ids[idKey.Key];

            if (idVal != idKey.Key)

                throw new Exception("val != key");

        }

        stopwatch.Stop();

        Console.WriteLine($"Time to read {nbrOfIteration} items: {stopwatch.Elapsed}");

        stopwatch.Reset();

    }

}

​

public class Book

{

    public string Name { get; set; }

    public int Year { get;set; }

​

    public Book(string Name, int Year)

    {

        this.Name = Name;

        this.Year = Year;

    }

​

    public override string ToString()

    {

        return $"{Name} ({Year})";

    }

}

​