// Educational reference, not a replacement for Dictionary<TKey, TValue>.
// Compatible with modern C#. Compare keys with IEqualityComparer<TKey>,
// never rely on a hash code alone to establish equality.
using System;
using System.Collections.Generic;

public sealed class EducationalHashMap<TKey, TValue> where TKey : notnull
{
    private sealed class Entry
    {
        internal readonly TKey Key;
        internal TValue Value;
        internal Entry(TKey key, TValue value) { Key = key; Value = value; }
    }

    private List<Entry>[] _buckets;
    private readonly IEqualityComparer<TKey> _comparer;
    public int Count { get; private set; }

    public EducationalHashMap(int initialBucketCount = 5, IEqualityComparer<TKey>? comparer = null)
    {
        if (initialBucketCount < 1) throw new ArgumentOutOfRangeException(nameof(initialBucketCount));
        _buckets = CreateBuckets(initialBucketCount);
        _comparer = comparer ?? EqualityComparer<TKey>.Default;
    }

    private static List<Entry>[] CreateBuckets(int count)
    {
        var buckets = new List<Entry>[count];
        for (int i = 0; i < count; i++) buckets[i] = new List<Entry>();
        return buckets;
    }

    private int BucketIndex(TKey key, int bucketCount)
    {
        // A hash can be negative, including int.MinValue. The mask handles both.
        int hash = _comparer.GetHashCode(key);
        return (hash & int.MaxValue) % bucketCount;
    }

    public void Put(TKey key, TValue value)
    {
        if (key is null) throw new ArgumentNullException(nameof(key));
        int index = BucketIndex(key, _buckets.Length);
        foreach (var entry in _buckets[index])
        {
            if (_comparer.Equals(entry.Key, key)) { entry.Value = value; return; }
        }
        // Rehash when the projected average bucket occupancy becomes high.
        if ((long)(Count + 1) * 4 > (long)_buckets.Length * 3)
        {
            if (_buckets.Length > int.MaxValue / 2)
                throw new InvalidOperationException("Bucket capacity exhausted");
            Resize(_buckets.Length * 2 + 1);
            index = BucketIndex(key, _buckets.Length);
        }
        _buckets[index].Add(new Entry(key, value));
        Count++;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        if (key is null) throw new ArgumentNullException(nameof(key));
        foreach (var entry in _buckets[BucketIndex(key, _buckets.Length)])
        {
            if (_comparer.Equals(entry.Key, key)) { value = entry.Value; return true; }
        }
        value = default!;
        return false;
    }

    public bool Remove(TKey key)
    {
        if (key is null) throw new ArgumentNullException(nameof(key));
        var bucket = _buckets[BucketIndex(key, _buckets.Length)];
        for (int i = 0; i < bucket.Count; i++)
        {
            if (!_comparer.Equals(bucket[i].Key, key)) continue;
            bucket.RemoveAt(i); Count--; return true;
        }
        return false;
    }

    private void Resize(int newBucketCount)
    {
        var newBuckets = CreateBuckets(newBucketCount);
        foreach (var bucket in _buckets)
            foreach (var entry in bucket)
                newBuckets[BucketIndex(entry.Key, newBucketCount)].Add(entry);
        _buckets = newBuckets;
    }
}