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

Question

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

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

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

можно ли это объяснить?

689 8

c#dictionary hashtable big-o

8 ответов:

Comments

Ничего не найдено.

dasblinkenlight · Accepted Answer · 2016-05-21 05:15:48

the HashFunc сам имеет много операций за кулисами

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

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

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

Paarth · Accepted Answer · 2016-05-20 18:37:43

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

Vidas Vasiliauskas · Accepted Answer · 2016-05-22 10:18:32

Это означает, что независимо от того, какой размер вашей коллекции может быть, это все равно займет почти столько же времени, чтобы получить любой из его членов.

таким образом, Другими словами словарь с 5 членами, скажем, coud займет около 0,002 мс, чтобы получить доступ к одному из них, а также словарь из 25 членов должен принять что-то подобное. Большой o означает алгоритмической сложности по сравнению с размером сбора, а не фактические заявления или функции, выполняемые

Martin C. · Accepted Answer · 2016-05-23 14:32:06

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

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

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

вот почему dictionaryies / карты реализованы по-разному для разных сценариев. Для Java есть несколько различных реализаций, C++ использует красные / черные деревья и т. д. Вы выбрали их на основе количества данных и на основе их лучшей/средней/худшей эффективности выполнения.

twihoX · Accepted Answer · 2016-05-20 19:07:32

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

Ezra · Accepted Answer · 2017-05-23 15:18:01

см. пост что означает" O(1) время доступа"?

количество операций в хэш-функции не имеет значения, если оно занимает одинаковое (постоянное) количество времени для каждого элемента в коллекции. Например, доступ к одному элементу коллекции из 2 элементов .001 мс, а также доступ к одному элементу в коллекции 2,000,000,000 элементов .001 МС. Хотя хэш-функции может содержать сотни, если заявления и несколько проведенные расчеты.

JeReT · Accepted Answer · 2017-05-23 15:03:01

документы:

получение значения с помощью его ключа очень быстро, близко к O (1), потому что T:система.Коллекции.Родовой.Класс Dictionary ' 2 реализован в виде хэш-таблицы.

Так это может быть O(1), но может быть медленнее. Здесь вы можете найти еще один поток, касающийся производительности hashtable:хэш-таблица-почему она быстрее массивов?

Ed Avis · Accepted Answer · 2016-05-20 19:19:36

Как только вы учитываете тот факт, что все большие и большие словари занимают больше памяти, продвигаясь дальше по иерархии кэша и в конечном итоге замедляя пространство подкачки на диске, трудно утверждать, что это действительно O(1). Производительность словаря будет замедляться по мере его увеличения, вероятно, давая o(log N) временную сложность. Не веришь мне? Попробуйте сами с 1, 100, 1000, 10000 и так далее словарных элементов, вплоть до 100 миллиардов, и измерить, сколько времени требуется на практике, чтобы посмотрите на элемент.

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