Критикуйте эту реализацию C # Hashmap?

Question

Я написал хеш-карту в C # как упражнение для самостоятельного изучения. Я хотел реализовать цепочку как технику обработки столкновений. Сначала я подумал, что просто использую GetHashCode в качестве алгоритма хэширования, но я быстро обнаружил, что использование чисел, возвращаемых GetHashCode, не всегда будет жизнеспособным (размер int вызывает out of mem, если вы хотите индексировать и массивировать с число и числа могут быть отрицательными :(). Итак, я придумал хитрый метод сужения чисел (см. 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). Более часто используемый (и почти всегда лучший подход) состоит в том, чтобы начинать с начального размера, который либо известен (благодаря знанию предметной области), чтобы он был достаточно большим для всех значений, либо начинал с малого, и размер хэш-таблицы изменялся бы соответствующим образом. С повторным исследованием очевидной мерой необходимости изменения размера является то, сколько повторной проверки было необходимо. Если вы экспериментируете здесь с цепочкой, вам нужно уменьшить средний и максимальный размеры цепей. Это сокращает время поиска в худшем случае и, следовательно, среднее время поиска ближе к O (1) в лучшем случае.

Два наиболее распространенных подхода к такому хешированию (и, следовательно, к исходному размеру таблицы) - это использовать простые числа или степени двойки. Считается, что первый вариант (хотя по этому поводу имеется определенное противоречие) предлагает лучшее распределение ключей, в то время как второй обеспечивает более быстрое вычисление (оба случая выполняют по модулю входной хеш-код, но с числом, известным как степень 2). По модулю можно быстро выполнить как двоичные операции, так и операции. Еще одно преимущество использования степени двойки при объединении в цепочку состоит в том, что можно проверить цепочку, чтобы увидеть, действительно ли изменение размера хеша приведет к разделению цепочки или нет (если у вас есть таблица с 8 значениями и есть цепочка все хэши которых равны 17, 1 или 33, тогда удвоение размера таблицы все равно оставит их в одной цепочке, но увеличение в четыре раза приведет к их перераспределению).

У вас нет метода, предлагающего семантику замены, которая обычно используется в типах словарей .NET (при добавлении произойдет ошибка, если элемент с таким ключом уже есть, но присвоение индекса не будет).

Ваша ошибка при поиске, которая будет пытаться выйти за пределы количества сегментов, не будет иметь смысла для пользователя, которому все равно, существует ли этот сегмент или нет, только для ключа (им не нужно знать, как работает ваша реализация совсем). В обоих случаях, когда ключ не найден, следует выдавать одну и ту же ошибку (System.Collections.Generic.KeyNotFoundException имеет точно правильную семантику, поэтому вы можете использовать ее повторно.).

Использование List довольно тяжело в этом случае. В общем, я бы нахмурился, если бы кто-то сказал, что коллекция BCL была слишком тяжелой, но когда дело доходит до проката ваших собственных коллекций, это обычно либо потому, что (1) вы хотите извлечь уроки из упражнения, либо (2) коллекции BCL не подходят ваши цели. В случае (1) вы должны узнать, как выполнить начатое задание, а в случае (2) вы должны быть уверены, что у List нет ошибок, которые вы обнаружили с помощью Dictionary.

Ваше удаление выдает бессмысленную ошибку для того, кто не знает о деталях реализации, и несовместимую ошибку (если в этом контейнере есть что-то еще, это не то, о чем им следует заботиться). Поскольку удаление несуществующего элемента не является вредным, чаще всего просто возвращать логическое значение, указывающее, присутствовал элемент или нет, и позволить пользователю решить, указывает ли это на ошибку или нет. Также расточительно продолжать поиск по всему ведру после того, как предмет был удален.

Ваша реализация теперь допускает нулевые ключи, что является достаточно разумным (действительно, документация для IDictionary<TKey, TValue> говорит, что реализации могут или не могут сделать это). Однако вы отклоняете их путем возврата NullReferenceException, вызванного попыткой вызова GetHashCode() при нулевом значении, вместо проверки и выдачи ArgumentNullException. Для пользователя получить NullReferenceException предполагает, что сама коллекция была нулевой. Следовательно, это явная ошибка.

Answer 2

1. Метод Remove никогда не должен вызывать исключение.Вы пытаетесь удалить предмет.Нет вреда, если он уже был удален.Все классы коллекций в .Net используют bool в качестве возвращаемого значения, чтобы указать, действительно ли был удален элемент.

2. Не выбрасывать исключение, выбрасывать конкретное.Просмотрите все исключения в пространствах имен Collection, чтобы найти подходящие.

3. Добавьте TryGetValue

4. Используйте KeyValuePair, которая уже является частью .Netвместо создания собственного.

5. Добавьте конструктор, который может определять размер карты.

6. При создании исключений включайте сведения о том, почему оно было выброшено.Например, вместо того, чтобы писать «Этот ключ существует», напишите string.Format («Ключ» {0} 'уже существует », ключ)

Answer 3

Извините, что говорю это, но этот класс не будет работать как HashMap или даже простой словарь.

Прежде всего, значение, возвращаемое из GetHashCode (), не является уникальным. Два разных объекта, например две строки, возможно, может вернуть то же значение хэш-кода. Идея использовать хеш-код в качестве индекса массива просто приводит к потере записи в случае коллизии хеш-кода. Я бы посоветовал прочитать о методе GetHashCode () и о том, как реализовать его из MSDN. Некоторый очевидный пример: если вы получите хеш-код всех возможных значений Int64, начинающихся с 0, хеш-код обязательно будет конфликтовать в какой-то момент.

Другое дело, что поиск для цикла выполняется медленно. Вы должны рассмотреть возможность использования бинарного поиска для поиска. Для этого вы должны в любой момент сохранить пару ключ-значение, отсортированную по ключу, что означает, что вы должны использовать список вместо массива для переменной storage , поэтому при добавлении новой пары ключ-значение вы можете вставьте его в соответствующий индекс.

В конце концов, убедитесь, что когда вы кодируете для реальной карты хеш-функции, вы поняли, что хеш-код может быть одинаковым для разных ключей, и никогда не выполняете поиск с помощью цикла for от 0 до len-1.