GetHashCode и Buckets

Я пытаюсь лучше понять, как работают хэны HashSet<T> делать работу и почему они являются исполнителями. Я обнаружил следующую статью, реализуя простой пример со списком http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/.

Насколько я понимаю эту статью (и я тоже так думал раньше), список корзин сам группирует определенное количество элементов в каждой корзине. Одно ведро представлено хеш-кодом, а именно GetHashCode который вызывается на элементе. Я думал, что лучшая производительность основана на том факте, что меньше элементов, чем элементов.

Теперь я написал следующий наивный тест-код:

    public class CustomHashCode
    {
        public int Id { get; set; }

        public override int GetHashCode()
        {
            //return Id.GetHashCode(); // Way better performance
            return Id % 40; // Bad performance! But why?
        }


        public override bool Equals(object obj)
        {
            return ((CustomHashCode) obj).Id == Id;
        }

    }

А вот профилировщик:

    public static void TestNoCustomHashCode(int iterations)
    {

        var hashSet = new HashSet<NoCustomHashCode>();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Add(new NoCustomHashCode() { Id = j });
        }

        var chc = hashSet.First();
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Contains(chc);
        }
        stopwatch.Stop();

        Console.WriteLine(string.Format("Elapsed time (ms): {0}", stopwatch.ElapsedMilliseconds));
    }

Моя наивная мысль была такова: давайте уменьшим количество сегментов (с простым модулем), которые должны повысить производительность. Но это ужасно (в моей системе это занимает около 4 секунд с 50000 итерациями). Я также подумал, что если я просто верну Id в качестве хэш-кода, производительность будет плохой, так как я получу 50000 блоков. Но дело обстоит наоборот, я думаю, что я просто создал тоны так называемых столкновений вместо того, чтобы что-то улучшать. Но опять же, как работают списки ведра?

Источник

3 ответа

Решение

Contains проверьте в основном:

  1. Получает хеш-код элемента.
  2. Находит соответствующий сегмент - это прямой поиск в массиве на основе хеш-кода элемента.
  3. Если корзина существует, пытается найти элемент в корзине - это перебирает все элементы в корзине.

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

Вы, вероятно, уменьшили объем памяти хэш-набора; Вы, возможно, даже сократили время вставки, хотя я сомневаюсь в этом. Вы не сократили время проверки существования.

Источник

Просто HashSet<T> может быть реализовано так (просто эскиз, не компилируется)

class HashSet<T>
{
    struct Element
    {
        int Hash;
        int Next;
        T item;
    }

    int[] buckets=new int[Capacity];
    Element[] data=new Element[Capacity];

    bool Contains(T item)
    {
        int hash=item.GetHashCode();
        // Bucket lookup is a simple array lookup => cheap
        int index=buckets[(uint)hash%Capacity];
        // Search for the actual item is linear in the number of items in the bucket
        while(index>=0)
        {
           if((data[index].Hash==hash) && Equals(data[index].Item, item))
             return true;
           index=data[index].Next;          
        }
        return false;
    }
}

Если вы посмотрите на это, стоимость поиска в Contains пропорционально количеству предметов в ведре. Таким образом, наличие большего количества сегментов делает поиск более дешевым, но как только количество сегментов превышает количество элементов, выигрыш от дополнительных блоков быстро уменьшается.

Наличие различных хеш-кодов также служит для раннего сравнения объектов внутри корзины, избегая потенциально дорогостоящих Equals звонки.

Короче GetHashCode должно быть максимально разнообразным. Это работа HashSet<T> уменьшить это большое пространство до соответствующего количества ведер, которое приблизительно равно количеству предметов в коллекции (как правило, с коэффициентом два).

Источник

Уменьшение количества сегментов не увеличит производительность. На самом деле, GetHashCode метод Int32 возвращает само целочисленное значение, которое идеально подходит для производительности, так как будет производить как можно больше сегментов.

То, что дает производительность хэш-таблицы, - это преобразование ключа в хеш-код, что означает, что он может быстро устранить большинство элементов в коллекции. Единственные предметы, которые он должен рассмотреть, это те, которые находятся в одном ведре. Если у вас мало ведер, это означает, что он может уменьшить количество предметов.

Худшая возможная реализация GetHashCode заставит все предметы идти в одном ведре:

public override int GetHashCode() {
  return 0;
}

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

Источник
Другие вопросы по тегам