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

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

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

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

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

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

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

Изменить: обобщить то, что я узнал:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

поэтому K-битная хеш-функция ==> не более 2 ^ K эффективных бинов ==> до 2 ^ (nK) n-битных ключей на бункер ==> (nK) шагов (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-битный); если вы делаете второй хеш, у вас такая же проблема, если у второго хеша есть столкновение.

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

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).

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

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

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

Скопировано отсюда

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

A. Значение на целое число меньше размера хеш-таблицы. Следовательно, значение является его собственным хешем, поэтому хеш-таблицы нет. Но если бы он был, это было бы 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 Hans комментирует мой ответ, который также упоминается выше :

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

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

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

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