Я вижу, как вы можете получить доступ к своей коллекции по ключу. Однако сама хэш-функция имеет множество операций за кулисами, не так ли?
Предполагая, что у вас хорошая хеш-функция, которая очень эффективна, все равно может потребоваться много операций.
Можно ли это объяснить?
HashFuncсам имеет много операций за кулисами
Это, безусловно, так. Однако количество этих операций зависит от размера ключа, а не от размера хеш-таблицы, в которую вставлен ключ: количество операций для вычисления хэш-функции одинаково для ключа в таблице с десятью или с десятью тысячами записей.
Вот почему вызов хэш-функции часто рассматривается как O (1). Это отлично работает для ключей фиксированного размера (целые значения и строки фиксированной длины). Он также обеспечивает приличное приближение для клавиш с переменным размером с практическим верхним пределом.
В общем случае, время доступа хэш-таблицы равно O (k), где k - верхний предел размера хэш-ключа.
O(1) не означает мгновенного. O(1) означает постоянную, независимо от размера данных. Хеш-функция занимает определенное количество времени, но это количество времени не масштабируется с размером коллекции.
Это означает, что независимо от того, какой размер вашей коллекции может быть, для получения любого из его членов все равно потребуется почти столько же времени.
Так что, другими словами, словарь с 5 членами позволит сказать, что coud занимает около 0.002 мс для доступа к одному из них, а также словарь из 25 членов должен брать что-то подобное. Big O означает алгоритмическую сложность по размеру коллекции вместо фактических выполняемых операций или выполняемых функций.
Если словарь/карта реализована как HashMap, она имеет наилучшую сложность в случае O(1), так как в лучшем случае она требует точно вычисления хэш-кода ключевого элемента для извлечения, если не являются ключевыми столкновениями.
Хэш-карта может иметь худшую сложность во время выполнения O(n), если у вас много ключевых столкновений или очень плохая хеш-функция, поскольку в этом случае она ухудшает линейное сканирование всего массива, который выполняется данные.
Кроме того, O(1) не означает мгновенно, это означает, что он имеет постоянную сумму. Поэтому выбор правильной реализации для словаря может также зависеть от количества элементов в коллекции, поскольку наличие очень высоких постоянных затрат для функции будет намного хуже, если будет всего несколько записей.
То, почему словари/карты реализуются по-разному для разных сценариев. Для Java существует несколько различных реализаций, С++ использует красные/черные деревья и т.д. Вы выбрали их на основе количества данных и на основе их лучшей/средней/наихудшей производительности исполнения.
См. сообщение Что такое "время доступа O (1)" ) значит?
Число операций в хеш-функции не имеет значения, если оно принимает одинаковое (постоянное) количество времени для КАЖДОГО элемента в коллекции. Например, доступ к одному элементу в коллекции из 2 элементов занимает 0,001 мс, но также доступ к одному элементу в коллекции из 2 000 000 000 элементов занимает 0,001 мс. Хотя хэш-функция может содержать сотни операторов if и нескольких вычислений.
из документов:
Получение значения с помощью его ключа очень быстро, близко к O (1), потому что класс T: System.Collections.Generic.Dictionary`2 реализуется как хеш-таблица.
Таким образом, это может быть O (1), но может быть медленнее. Здесь вы можете найти еще одну тему, касающуюся производительности хеш-таблицы: Hash table - почему это быстрее, чем массивы?
Как только вы позволяете себе, что все больше и больше словарей занимают больше памяти, идя дальше вниз по иерархии кеша и, в конечном счете, чтобы замедлить пространство подкачки на диске, трудно утверждать, что это действительно O (1). Производительность словаря будет становиться все медленнее, поскольку она становится больше, вероятно, учитывая сложность времени O (log N). Не верьте мне? Попробуйте это для себя с помощью 1, 100, 1000, 10000 и т.д. Элементов словаря, до 100 миллиардов, и измерьте, сколько времени требуется на практике для поиска элемента.
Однако, если вы сделаете упрощающее предположение, что вся память в вашей системе является оперативной памятью и к ней можно получить доступ в постоянное время, вы можете утверждать, что словарь - это O (1). Это предположение является обычным явлением, даже если это не совсем верно для любой машины с диска подкачки, и по-прежнему довольно спорно в любом случае, с учетом различных уровней кэш-памяти процессора.