Могут ли хеш-таблицы действительно быть O (1)?

Question

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

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

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

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

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

Статья Wikipedia для хеш-таблиц постоянно ссылается на постоянное время поиска и полностью игнорирует стоимость хеш-функции.Это действительно справедливая мера?

---

Редактировать: Подводя итог, что я узнал:

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

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

Answer 1

Здесь у вас есть две переменные, m и n, где m - длина ввода, а n - количество элементов в хэше.

Заявление о производительности поиска O (1) делает как минимум два предположения:

• Ваши объекты можно сравнить по равенству за O (1) раз.
• Будет несколько коллизий хешей.

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

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

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

Answer 2

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

Что? Для хеширования одного элемента требуется постоянное время. Почему это было бы что-то еще? Если вы вставляете n элементов, тогда да, вам нужно вычислить n хешей, и это занимает линейное время ... чтобы найти элемент, вы вычисляете один хеш того, что ищете, тогда найти соответствующее ведро с этим. Вы не пересчитываете хэши всего, что уже есть в хеш-таблице.

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

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

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

---

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

Answer 3

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

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

Answer 4

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

Если ваш ключ имеет n-битное представление, ваша хеш-функция может использовать 1, 2, ... n из этих битов. Думая о хэш-функции, которая использует 1 бит. Оценка O (1) точно. Но вы только разделяете пространство ключей на 2. Таким образом, вы отображаете до 2 ^ (n-1) ключей в одну корзину. с помощью поиска BST это занимает до n-1 шагов, чтобы найти определенный ключ, если он почти заполнен.

Вы можете расширить это, чтобы увидеть, что, если ваша хеш-функция использует K бит, ваш размер ячейки равен 2 ^ (n-k).

так что K-битная хеш-функция ==> не более 2 ^ K эффективных бинов ==> до 2 ^ (n-K) n-битных ключей на бин ==> (n-K) шагов (BST) для разрешения коллизий. На самом деле большинство хеш-функций гораздо менее «эффективны» и требуют / используют больше K бит для создания 2 ^ k бинов. Так что даже это оптимистично.

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

Однако, это НЕ как / когда вы используете хеш-таблицу!

Анализ сложности предполагает, что для n-битных ключей в таблице может быть O (2 ^ n) ключей (например, 1/4 всех возможных ключей). Но большую часть, если не все время, мы используем хеш-таблицу, у нас есть только постоянное количество n-битных ключей в таблице. Если вам нужно только постоянное количество ключей в таблице, скажем, C является вашим максимальным числом, то вы можете сформировать хеш-таблицу из O (C) корзин, которая гарантирует ожидаемое постоянное столкновение (с хорошей хэш-функцией); и хэш-функция, использующая ~ logC из n битов в ключе. Тогда каждый запрос O (logC) = O (1). Вот как люди утверждают, что «доступ к хеш-таблице - O (1)» /

Здесь есть пара уловов - во-первых, сказать, что вам не нужны все биты, может быть только биллинг. Во-первых, вы не можете действительно передать значение ключа хэш-функции, потому что это будет перемещать n бит в памяти, которая равна O (n). Так что вам нужно сделать, например, Передача ссылок. Но вам все еще нужно хранить его где-то, что было операцией O (n); вы просто не выставляете счет за хеширование; Вы общая вычислительная задача не можете избежать этого. Во-вторых, вы выполняете хеширование, находите корзину и находите более 1 ключей; ваша стоимость зависит от вашего метода разрешения - если вы сделаете сравнение на основе (BST или List), у вас будет O (n) операция (ключ возврата n-битный); если вы делаете 2-й хэш, то у вас возникнет та же проблема, если 2-й хэш столкнулся. Таким образом, O (1) не гарантируется на 100%, если у вас нет столкновений (вы можете улучшить шанс, имея таблицу с большим количеством корзин, чем ключей, но все же)

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

Answer 5

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

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

Я вижу удивительную путаницу вокруг этой темы в других ответах и ​​комментариях и постараюсь исправить некоторые из них в этом длинном ответе.

Рассуждая о худшем случае

Существуют различные типы анализа наихудших случаев. Анализ, который большинство ответов дали здесь до сих пор , это не худший случай, а скорее средний случай [ 2 ]. Средний случай Анализ имеет тенденцию быть более практичным. Может быть, ваш алгоритм имеет один плохой входной сигнал в худшем случае, но на самом деле хорошо работает для всех других возможных входных данных. Итог, ваше время выполнения зависит от набора данных , на котором вы работаете.

Рассмотрим следующий псевдокод метода get хеш-таблицы. Здесь я предполагаю, что мы обрабатываем коллизии цепочкой, поэтому каждая запись таблицы представляет собой связанный список из (key,value) пар. Мы также предполагаем, что количество сегментов m фиксировано, но равно O(n), где n - количество элементов на входе.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

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

(1) Вы передаете алгоритм хэш-таблицы злоумышленнику.

(2) Противник может изучить его и подготовиться столько, сколько он хочет.

(3) Наконец, противник дает вам ввод размера n для вставки в таблицу.

Вопрос: как быстро ваша хеш-таблица на входе противника?

На шаге (1) злоумышленник знает вашу хэш-функцию; на этапе (2) злоумышленник может создать список из n элементов с таким же hash modulo m, например, случайное вычисление хэша группы элементов; и затем в (3) они могут дать вам этот список. Но, о чудо, поскольку все элементы n хешируются в одном и том же сегменте, вашему алгоритму потребуется O(n) время для обхода связанного списка в этом сегменте. Независимо от того, сколько раз мы повторяем вызов, противник всегда побеждает, и вот каков ваш алгоритм, наихудший случай O(n).

Почему хеширование является O (1)?

В предыдущем испытании нас оттолкнуло то, что противник очень хорошо знал нашу хэш-функцию и мог использовать это знание для создания наихудшего возможного ввода. Что, если вместо того, чтобы всегда использовать одну фиксированную хеш-функцию, у нас фактически был набор хеш-функций, H, который алгоритм может произвольно выбирать во время выполнения? Если вам интересно, H называется универсальным семейством хеш-функций [ 3 ]. Хорошо, давайте попробуем добавить к этому случайность .

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

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Если мы попробуем выполнить вызов еще раз: с шага (1) злоумышленник может узнать все хеш-функции, которые есть в H, но теперь конкретная хеш-функция, которую мы используем, зависит от r. Значение r является частным для нашей структуры, противник не может ни проверять его во время выполнения, ни прогнозировать его заранее, поэтому он не может составить список, который всегда плох для нас. Предположим, что на шаге (2) злоумышленник выбирает одну функцию hash из H в случайном порядке, затем он создает список n столкновений под hash modulo m и отправляет его на шаг (3), скрестив пальцы, чтобы во время выполнения H[r] будет таким же, hash они выбрали.

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

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

---

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

Answer 6

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

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

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

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

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

Рассмотрим телефонную книгу: у вас могут быть довольно длинные имена, но независимо от того, содержит ли книга 100 имен или 10 миллионов, средняя длина имени будет довольно последовательной, и это худший случай в истории. .

Мировой рекорд Гиннеса по самому длинному имени, которое когда-либо использовалось кем-либо, был установлен Адольфом Блейном Чарльзом Дэвидом Эрлом Фредериком Джеральдом Хьюбертом Ирвином Джоном Кеннетом Ллойдом Мартином Неро Оливером Полом Куинси Рэндольфом Шерманом Томасом Ункасом Виктором Уильямом Ксерксом Янси Вольфешлегельштайнхаузенбергердорф, старший

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

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

Также возможно создать хэш из объема ключевых данных фиксированного размера. Например, Microsoft Visual C ++ поставляется с реализацией стандартной библиотеки std::hash<std::string>, которая создает хэш, включающий всего десять байтов, равномерно распределенных по строке, поэтому, если строки изменяются только при других индексах, вы получаете коллизии (и, следовательно, на практике не O ( 1) поведения на стороне поиска после столкновения), но время создания хэша имеет жесткую верхнюю границу.

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

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

Например, при коэффициенте загрузки 1,0 средняя длина этих линейных поисков в среднем составляет ~ 1,58 независимо от количества ключей (см. мой ответ здесь ). Для закрытого хеширования это немного сложнее, но не намного хуже, когда коэффициент загрузки не слишком высок.

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

Этот вид упускает суть. Любой тип ассоциативной структуры данных в конечном итоге должен иногда выполнять операции с каждой частью ключа (неравенство может иногда определяться только из части ключа, но равенство обычно требует рассмотрения каждого бита). Как минимум, он может хешировать ключ один раз и сохранять хеш-значение, и если он использует достаточно сильную хеш-функцию - например, 64-битный MD5 - он может практически игнорировать даже возможность хеширования двух ключей к одному и тому же значению (компания, в которой я работал, сделала именно это для распределенной базы данных: время генерации хеша было все же незначительным по сравнению с сетевыми передачами в глобальной сети). Таким образом, нет смысла беспокоиться о затратах на обработку ключа: это присуще хранению ключей независимо от структуры данных, и, как сказано выше, в среднем не ухудшается при наличии большего количества ключей.

Что касается достаточно больших хеш-таблиц, приводящих к коллизиям, то здесь тоже не хватает смысла. Для отдельной цепочки у вас все равно будет постоянная средняя длина цепи столкновений при любом данном коэффициенте нагрузки - она ​​выше, когда коэффициент нагрузки выше, и эта зависимость нелинейная. Пользователь SO Ганс комментирует мой ответ, также связанный выше , что:

средняя длина ковша, обусловленная непустыми ковшами, является лучшим показателем эффективности. Это / (1-e ^ {- a}) [где a - коэффициент загрузки, e = 2,71828 ...]

Таким образом, коэффициент загрузки в одиночку определяет среднее количество сталкивающихся ключей, которые вы должны искать во время операций вставки / удаления / поиска. Для раздельной цепочки он не просто становится постоянным при низком коэффициенте нагрузки - он всегда постоянный. Однако для открытой адресации ваше утверждение имеет некоторую обоснованность: некоторые сталкивающиеся элементы перенаправляются в альтернативные сегменты и могут затем мешать операциям с другими ключами, поэтому при более высоких коэффициентах нагрузки (особенно> 0,8 или 0,9) длина цепочки столкновений становится значительно хуже.

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

Что ж, размер таблицы должен приводить к нормальному коэффициенту загрузки, учитывая выбор хеширования или отдельного сцепления, но также если хеш-функция немного слабая и ключи не очень случайные, с простым числом сегментов часто помогает уменьшить коллизии (hash-value % table-size затем оборачивается так, что изменения только одного или двух старших разрядов в хеш-значении по-прежнему разрешаются, чтобы сегменты распределялись псевдослучайно по различным частям хеш-таблицы).

Answer 7

Кажется, основываясь на обсуждении здесь, что если X - это верхний предел (# элементов в таблице / # бинов), то лучшим ответом будет O (log (X)), при условии эффективной реализации поиска бина.

Answer 8

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

1. Если ваша установка статична, то хеширование FKS даст вам гарантию на худший случай O (1) . Но, как вы указали, ваши настройки не являются статичными.
2. Если вы используете хеширование Cuckoo, тогда запросы и удаления будут O (1) в худшем случае, но вставка ожидается только O (1) . Хеширование кукушки работает довольно хорошо, если у вас есть верхняя граница для общего количества вставок и вы установите размер таблицы примерно на 25% больше.

Скопировано с здесь