自实现字典，但以自定义类作为关键

Question

我正在做一个练习来帮助我理解和学习泛型的使用，以及对接口和接口继承的理解。这是通过实现和使用我自己的类来完成的。

我认为我已经1成功完成了部分工作（遵循教程），并且能够毫无问题地进行散列并添加到我的字典中。如果解决方案中有我遗漏的部分，1请随时告诉我。

第二部分是主要问题。根据我的理解，我应该让钥匙是 一个城市的latitude和。longitude我自己的 Dictionary 实现Dict是这样的，Dict<K, V>所以键不可能有 2 个值。

我认为这就是struct可以进来并传递 mystruct作为密钥，同时存储latitude和 的值的地方longitude。

下面我将尝试概述练习描述和要求，以使我的问题更容易理解。

---

该练习有 2 个部分

第1部分

在这一部分中，您将创建自己的类来实现 IDictionary<K,V>。

为了实现 IDictionary<K,V> 您必须实现 ICollection 和 IEnumerable 接口。

不允许您使用C#Dictionary 实现作为委托，因为这会使练习变得无关紧要。

第2部分

我们希望使用最近创建的 Dictionary 类将纬度和经度值映射到其匹配的城市。

键本身应该是一个表示由 a和 aGeoLocation组成的类。制作所有必要的函数和运算符重载，以便可以使用此类作为 Dictionary 类的键latitudelongitude

---

代码

字典：

 public class Dict<K, V>:IEnumerable<KeyValuePair<K,V>>
    {
        private const int INI_Size = 16;
        LinkedList<KeyValuePair<K, V>>[] values;

        public Dict()
        { 
            this.values = new LinkedList<KeyValuePair<K, V>>[INI_Size];
        }

        public int Count { get; private set; }
        public int Capacity
        {
            get
            {
                return this.values.Length;
            }
        }

        public void Add(K key, V value)
        {
            var hash = this.HashKey(key);

            if(this.values[hash]== null)
            {
                this.values[hash] = new LinkedList<KeyValuePair<K, V>>();
            }

            var keyExistsAlready = this.values[hash].Any(p => p.Key.Equals(key));

            if (keyExistsAlready)
            {
                throw new InvalidOperationException("key already exist");
            }

            var pair = new KeyValuePair<K, V>(key, value);
            this.values[hash].AddLast(pair);
            this.Count++;

            if (this.Count >= this.Capacity * 0.75)
            {
                this.ResizeAndReAddValues();
            }
        }

        public V Find (K key)
        {
            var hash = this.HashKey(key);
            if(this.values[hash] == null)
            {
                return default(V);
            }
            var collection = this.values[hash];
            return collection.First(p => p.Key.Equals(key)).Value;
        }

        public bool ContainsKey(K key)
        {
            var hash = HashKey(key);

            if (this.values[hash] == null)
            {
                return false;
            }

            var collection = this.values[hash];
            return collection.Any(pair => pair.Key.Equals(key));
        }

        private int HashKey(K key)
        {
            var hash = Math.Abs(key.GetHashCode()) % this.Capacity;
            return hash;
        }

        private void ResizeAndReAddValues()
        {
            var cachedValues = this.values;
            this.values = new LinkedList<KeyValuePair<K, V>>[2 * this.Capacity];
            this.Count = 0;
            foreach (var collection in cachedValues)
            {
                if (collection != null)
                {
                    foreach (var value in collection)
                    {
                        this.Add(value.Key, value.Value);
                    }
                }
            }
        }

        public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
        {
            foreach(var collection in this.values)
            {
                if (collection != null)
                {
                    foreach (var value in collection)
                    {
                        yield return value;
                    }
                }
            }
        }

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

地理位置：

 public struct GeoLocation
    {
        public float X;
        public float Y;

        public GeoLocation(float x, float y)
        {
            X = x;
            Y = y;
        }
    }

---

我的思考过程

如果我使用已经实现Dictionary的System.Collections.Generic

var dict = new Dictionary<GeoLocation, string>() {
    [new GeoLocation(12, 78)] = "Paris",
    [new GeoLocation(98, -18)] = "Frankfurt"
};
        //test for part 1 (works)
       /* var d = new Dict<int, string>
        {
            { 10, "Washington" }
        };*/

这是可能的，我会对我的实现做同样的事情还是解决方案与我想象的完全不同？

另一件要补充的事情是，正如我之前所说，如果我的实现也有部分错误，1请告诉我，因为我正在尝试通过编码和提问来理解事物。

Answer 1

我不会给你一个即插即用的答案，因为这是一个练习，我发现为你解决它是有问题的。

我将为您提供一些应该足够的提示，以及对您的代码的一些反馈。

首先：

实现 IDictionary<TK, TV> 以免费获取您帖子中提到的语法（以及每个人都知道如何在 C# 中使用的标准化 API）。

一些一般提示：

• 隐藏实施细节（pm100 也提到过）
• 单元测试实现，特别是针对边缘情况（请务必编写测试！）
• 使用现代 C#：

private int HashKey(TKey key)
{
    var hash = Math.Abs(key.GetHashCode()) % this.Capacity;
    return hash;
}

可能

private int HashKey(TKey key)
    => Math.Abs(key.GetHashCode()) % this.Capacity;

和

public bool IsReadOnly 
{
    get { return false; }
}

可能

public bool IsReadOnly => false;

// or

public bool IsReadOnly { get; } = false;

一些更具体的提示：

字典中使用的键（这是一种简化，但通常是最相关的两个）根据两个属性进行行为：

• 相等：字典使用比较（例如 equals 方法或 == 运算符）来确定两个元素（类型为 key）是否相等
• 散列：密钥必须实现满足以下条件的散列函数：
  • 当 Equals 返回 true 时，该GetHashCode函数必须为那些被视为“相等”的对象返回相同的哈希码
  • GetHashCode对于许多不相等的对象可能返回相同的值。这很好——如果有很多碰撞，可能会损害性能，但对于一组相同的对象来说，它不能是唯一的。微软表示：

不要通过测试哈希码是否相等来确定两个对象是否相等。

因此，在通过哈希码找到候选者后，必须检查是否相等。您已经在 find 方法中正确执行了此操作。

因此：为您的密钥正确实施散列和相等。C# 中的默认值是（对于您自己的类）引用相等。覆盖用作键的类型的相等函数和散列函数。

结构很有趣，因为它们默认按值进行比较，并且 GetHashCode 的行为方式对您有用。现代方法是使用记录（或记录结构）来免费获取相等性和哈希码。我建议您充分理解这两个概念，以便手动实现它们，以避免将来可能出现的误解和错误！