Hashtable и свои объекты в качестве ключа

#c_sharp

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

using System;
using System.Collections.Generic;
using System.Collections;
class a
{
    static void Main()
    {
        Hashtable ht = new Hashtable();
        ht.Add(new b(1),"ds");
        ht.Add(new b(2),"dsa");
        Console.WriteLine(ht[new b(1)]);
    }
}
class b
{
    public int x;
    public b(int y)
    {
        x = y;
    }
    public override int GetHashCode()
    {
        return new Random().Next();
    }
    public override bool Equals(object obj)
    {
        return ((b)obj).x == this.x;
    }
}


Но "мистика" начинается дальше, я было подумал, что раз он таким образом работает(то
есть находит по ключу строку), то вообще в своем классе можно не переопределять метод
GetHashCode, если при совершенно случайных числах, выдается правильный результат. Я
благополучно закоментировал переопределение этого метода, но тогда все перестало работать,
то есть перестал находить элементы по ключу. И тут возник вопрос, зачем ему вообще
нужен метод GetHashCode для поиска по ключу, если в Equals весь алгоритм сравнения
описан ? Перед всеми этими манипуляциями, е решил , что эта коллекция вообще не использует
Equals моего класса для сравнения у себя элементов, однако, оказалось, что если не
переопределять Equals то поиск по ключу тоже не происходит. Почему так ?
Еще неразбериха в том, почему если при указанной выше реализации GetHashCode добавить
два элемента таким образом 

Hashtable ht = new Hashtable();
        ht.Add(new b(1),"ds");
        ht.Add(new b(1),"dsa");
        Console.WriteLine(ht[new b(1)]);


то будет исключение, что уже данный объект был добавлен. Ведь хешкоды у них разные ??

Получается очень интересная ситуация, если в этом коде

class a
{
    static void Main()
    {
        Hashtable ht = new Hashtable();
        ht.Add(new b(1), "ds");
        ht.Add(new b(2), "dsa");
        Console.WriteLine(ht[new b(1)]);
    }
}
class b
{
    public int x;
    public b(int y)
    {
        x = y;
    }
    public override int GetHashCode()
    {
        //System.Threading.Thread.Sleep(1000);
        return new Random().Next();
    }
    public override bool Equals(object obj)
    {
        return ((b)obj).x == this.x;
    }
}


заменить ht.Add(new b(2), "dsa"); на ht.Add(new b(1), "dsa"); то выходит эксепшн
о том, что такой элемент уже есть (хотя если не изменять то все ок). Это при том что
генерируются разные числа которые вообще никак не зависят от аргумента. Однако если
после изменения расскоментировать //System.Threading.Thread.Sleep(1000); тогда все
работает логично
    

Ответы

Ответ 1

Это происходит потому, что семя для объекта класса Random зависит от текущего времени
и не успевает смениться между двумя вызывами GetHashCode(), из-за чего new Random().Next()
возвращает одинаковые значения: попробуйте поставить стоп-точки или сменить генератор
на статический счётчик, и словить исключение уже не получится.


Ответ 2

Возврат разных значений при каждом вызове GetHashCode — худшее, что только возможно
представить. Так делать нельзя. Если вы написали тест, в котором система ведёт себя
«как ожидается», это не очень хороший тест. В реальном коде ожидайте проблем.

Наверняка со сменой хэшкода вы просто не сможете найти элемент в HashTable.

Если вы сделали что-то, что запрещено документацией, и оно работает здесь и сейчас,
не стоит ожидать, что оно будет работать и в будущем. Если ваш код перестанет работать
по каким-то причинам, виноваты будете вы и только вы.

Поэтому лучше всегда играть по правилам.



По поводу того, что происходит.

Хэш-таблица устроена следующим образом. Все данные разделены на несколько «ящиков»
(buckets). Ящик выбирается в зависимости от хэшкода. При добавлении элемента, сначала
вычисляется хэшкод, находится нужный ящик, и дальнейшие операции ограничиваются этим
ящиком. Затем, элементы из ящика сравниваются с данным элементом при помощи Equals(object),
и если они все не равны, то элемент не найден и происходит добавление.¹

То же самое происходит и при удалении.

Это означает, что если вы пытаетесь удалить объект, то он будет искаться только в
«ящике», соответствующем его хэшкоду. Если вдруг хэшкод объекта меняется, никто не
переложит его автоматически в другой ящик. Поэтому при смене хэшкода алгоритм поиска
будет искать его в неверном ящике, не найдёт, и не сможет удалить.

Обратите внимание, что Hashtable — устаревший класс, пользоваться им не надо. Нужно
использовать Dictionary. В этом случае у вас кроме Equals(object) используется
и интерфейс IEquatable, так что если вас заботит производительность, имеет смысл
его имплементировать.



¹ Отсюда жёсткое требование о том, что равные (по Equals) объекты обязаны иметь одинаковый
хэшкод.


Ответ 3

Чтобы добиться уникальности генератора:

var rnd = new Random((int)DateTime.Now.Ticks);


Для вашего примера работает.

Вместо HashTable лучше использовать типобезопасную релизацию Dictionary.