Несоответствия в Big-O удаления из ArrayList и хеш-таблицы?

Это объясняется здесь. Ключевым моментом является то, что количество значений в динамическом массиве поддерживается на постоянном уровне.

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

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

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

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

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

Когда вы говорите о сложности алгоритма, на самом деле вам нужно обсуждать конкретную реализацию.

• Не существует класса Java, который называется «Хеш-таблица» (очевидно!) или «Хэш-таблица».

• Существуют классы Java с именами HashMap и Hashtable, и в них действительно есть удаление O(1).

Но они не работают так, как вы думаете (все?) работают хеш-таблицы. В частности, HashMap и Hashtable организованы как массив указателей на «цепочки».

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

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

^{Это рассуждение не работает, если хеш-функция не распределяет ключи равномерно. Это приводит к ситуации, когда возникает много коллизий хэшей. Действительно, наихудший случай — это когда все ключи имеют одинаковое хеш-значение и все они оказываются в одной хеш-цепочке со всеми N записями. В этом случае удаление включает в себя поиск цепочки с N элементами... и это делает ее O(N).}

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