c# - 批评这个 C# Hashmap 实现？

Question

我用 C# 编写了一个 hashmap 作为自学练习。我想将链接作为一种碰撞处理技术来实现。起初我以为我会简单地使用 GetHashCode 作为我的哈希算法，但我很快发现使用 GetHashCode 返回的数字并不总是可行的(如果你想通过索引和数组，int 的大小会导致内存不足) number 和 numbers 可以是负数 :()。所以，我想出了一个缩小数字的 kludgey 方法(参见 MyGetHashCode)。

有没有人对这个实现(哈希函数和一般)有任何指示/提示/批评？提前致谢!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace HashMap
{
    class Program
    {

        public class MyKVP<T, K>
        {
            public T Key { get; set; }
            public K Value { get; set; }
            public MyKVP(T key, K value)
            {
                Key = key;
                Value = value;
            }
        }


        public class MyHashMap<T, K> : IEnumerable<MyKVP<T,K>>
            where T:IComparable
        {

            private const int map_size = 5000;
            private List<MyKVP<T,K>>[] storage;
            public MyHashMap()
            {
                storage = new List<MyKVP<T,K>>[map_size];
            }

            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
            {
                return GetEnumerator();
            }
            public IEnumerator<MyKVP<T, K>> GetEnumerator()
            {
                foreach (List<MyKVP<T, K>> kvpList in storage)
                {
                    if (kvpList != null)
                    {
                        foreach (MyKVP<T, K> kvp in kvpList)
                        {
                            yield return kvp;
                        }
                    }
                }
            }


            private int MyGetHashCode(T key)
            {
                int i = key.GetHashCode();
                if (i<0) i=i*-1;
                return i / 10000;
            }

            public void Add(T key, K data)
            {
                int value = MyGetHashCode(key);

                SizeIfNeeded(value);

                //is this spot in the hashmap null?
                if (storage[value] == null)
                {
                    //create a new chain
                    storage[value] = new List<MyKVP<T, K>>();
                    storage[value].Add(new MyKVP<T, K>(key, data));
                }
                else
                { 
                    //is this spot taken?
                    MyKVP<T, K> myKvp = Find(value, key);
                    if (myKvp != null) //key exists, throw
                    {
                        throw new Exception("This key exists. no soup for you.");
                    }

                    //if we didn't throw, then add us
                    storage[value].Add(new MyKVP<T, K>(key, data));
                }

            }

            private MyKVP<T, K> Find(int value, T key)
            {
                foreach (MyKVP<T, K> kvp in storage[value])
                {
                    if (kvp.Key.CompareTo(key) == 0)
                    {
                        return kvp;
                    }
                }

                return null;
            }

            private void SizeIfNeeded(int value)
            {
                if (value >= storage.Length)
                {
                    List<MyKVP<T, K>>[] temp = storage;
                    storage = new List<MyKVP<T, K>>[value+1];
                    Array.Copy(temp, storage, temp.Length);
                }
            }

            public K this[T key]
            {

                get 
                {
                    int value = MyGetHashCode(key);
                    if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
                    MyKVP<T, K> myKvp = Find(value, key);
                    if (myKvp == null) throw new Exception("key does not exist");
                    return myKvp.Value;
                }
                set 
                {
                    Add(key, value);
                }
            }


            public void Remove(T key)
            {
                int value = MyGetHashCode(key);
                if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
                if (storage[value] == null) { throw new IndexOutOfRangeException("Key does not exist."); }

                //loop through each kvp at this hash location
                MyKVP<T, K> myKvp = Find(value, key);
                if (myKvp != null)
                {
                    storage[value].Remove(myKvp);
                }
            }
        }

        static void Main(string[] args)
        {
            MyHashMap<string, int> myHashMap = new MyHashMap<string, int>();
            myHashMap.Add("joe", 1);
            myHashMap.Add("mike", 2);
            myHashMap.Add("adam", 3);
            myHashMap.Add("dad", 4);

            Assert.AreEqual(1, myHashMap["joe"]);
            Assert.AreEqual(4, myHashMap["dad"]);
            Assert.AreEqual(2, myHashMap["mike"]);
            Assert.AreEqual(3, myHashMap["adam"]);

            myHashMap.Remove("joe");

            try 
            {
                if (myHashMap["joe"] == 3) { }; //should throw 
            }
            catch (Exception) 
            {
                try { myHashMap.Add("mike",1); }
                catch (Exception) {

                    foreach (MyKVP<string, int> kvp in myHashMap)
                    { 
                        Console.WriteLine(kvp.Key + " " + kvp.Value.ToString());
                    }


                    return;
                }

            }

            throw new Exception("fail");
        }
    }
}

Answer 1

您的散列方法是固定范围的。这意味着单个项目可能会导致创建 214748 个桶(如果它的哈希码重新哈希为 214747)。一种更常用(并且几乎总是更好的方法)是从已知的初始大小开始(由于领域知识)对于所有值都足够大，或者从小开始并让 hashmap 根据需要调整自身大小。通过重新探测，需要调整大小的明显衡量标准是需要多少重新探测。使用您在这里试验的链接，您将希望降低平均和最大链大小。这可以减少最坏情况下的查找时间，因此您的平均查找时间更接近最佳情况下的 O(1)。

这种散列(以及初始表大小)的两种最常见方法是使用质数或 2 的幂。前者被认为(尽管在这一点上有一些争论)提供更好的 key 分布，而后者允许更快的计算(这两种情况都对输入哈希进行模运算，但已知数字是 2 的幂，模可以作为二进制与运算快速完成)。在链接时使用 2 的幂的另一个优点是，可以测试链以查看调整散列大小是否真的会导致该链被拆分(如果您有一个 8 值表并且有一个链其哈希值全部为 17、1 或 33，那么将表大小加倍仍会将它们留在同一链中，但将其增加四倍将重新分配它们。

您没有提供替换语义的方法，这在 .NET 字典类型中很常见(如果已经存在具有该键的项目，添加将出错，但分配给索引则不会)。

您在尝试超出存储桶数量的检索时出现的错误对用户来说毫无意义，他们不关心存储桶是否存在，只关心 key (他们不需要知道您的实现是如何工作的根本)。找不到 key 的两种情况都应该抛出相同的错误(System.Collections.Generic.KeyNotFoundException 具有完全正确的语义，因此您可以重用它。)。

使用 List在这种情况下相当重。一般来说，我不赞成任何人说 BCL 集合太重，但是当涉及到滚动你自己的集合时，通常是因为(1)你想从练习中学习或者(2)BCL 集合不适合你的目的。在情况 (1) 中，您应该学习如何完成您开始的工作，在情况 (2) 中，您需要确保 List没有你发现的任何失败 Dictionary .

您的删除既会为不了解实现细节的人抛出一个无意义的错误，也会抛出一个不一致的错误(他们不应该关心该桶中是否存在其他东西)。由于删除不存在的项目并无害处，因此更常见的是仅返回一个 bool 值来指示该项目是否存在，并让用户决定这是否表示错误。在删除项后继续搜索整个桶也是一种浪费。

您的实现现在允许空键，这很合理(事实上，IDictionary<TKey, TValue> 的文档说实现可能会也可能不会这样做)。但是，您拒绝它们的方式是让 NullReferenceException试图调用 GetHashCode() 引起的返回 null，而不是检查并抛出 ArgumentNullException .为用户接收 NullReferenceException表明集合本身为空。因此，这是一个明显的错误。