Словарь <> производительность в последовательном против случайного

Question

Я использую Dictionary для хранения миллионов записей. Числа добавляются в виде последовательных чисел.

Я помню, что некоторые алгоритмы хеширования имели проблемы с последовательным добавлением ключей.

Это относится к .Net?
Если да, то какие у меня варианты? (какая-нибудь аккуратная библиотека?)

Данные довольно статичны после добавления. Стоит ли добавлять данные через рандомизатор?

PS Я уже проверил:

• Производительность словаря C #
• Производительность словаря
• Словарь <> Производительность
• Ключевые показатели для словаря

Answer 1

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

Вы действительно измерили проблему производительности?Если нет, не пытайтесь вносить изменения.Если это так, рассмотрите возможность написания класса, оптимизированного для последовательных индексов.

Answer 2

Словарь может иметь много накладных расходов для такого количества элементов, и он полагается на хорошее распределение хешей для идеальной производительности.

Возможно, вы захотите запустить некоторые тесты в сравнении с другими подходами, возможно ли будет просто выделить массив и использовать ключ в качестве индекса? Например, object [long], если у вас есть только возможные значения от 0 до 1 миллиона, тогда для массива это займет менее 8 МБ и будет намного быстрее, чем для словаря.

Если вы не можете сделать это напрямую, у вас может быть поиск уникального индекса long to int? Например, наличие словаря, который позволяет вам переводить long в int, который постоянно увеличивается, когда появляется новый long, которого вы не видели до того, как ему было назначено место в массиве.

Или, возможно, есть более сложный подход с зубчатыми массивами, такими как object [sequenceInt] [uniqueIndexInt]. Это действительно зависит от того, как вы будете получать доступ к данным позже

Answer 3

Примечание: под «последовательностью» я подразумеваю последовательность чисел, увеличивающихся на единицу.

На самом деле, если бы единственные ключи, добавленные в словарь, были в последовательности (без дубликатов или пробелов), это наилучшая возможная ситуация. В текущей реализации .Net (которая может измениться в любое время, поэтому вы не должны зависеть ни от чего из этого), long.GetGashCode() для всех последовательностей чисел возвращает последовательность чисел. И номер корзины вычисляется по модулю емкости словаря. Это означает, что в этом случае вы гарантированно не столкнетесь.

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

(В приведенном выше примере есть одна маленькая ложь. Для каждого пересечения 32-битной границы последовательность хеш-кодов для последовательности будет иметь пробел в одно число из-за способа реализации long.GetHashCode(). )