Сложность времени для операций таблицы Hash - O (1) или O (N)?

Question

При ответе на вопросы алгоритма структуры данных, если мы используем Hashtable (скажем, тот, что в структуре данных Java), чтобы решить вопрос, рассмотрим ли мы базовую сложность Hashtable или можем ли мы смело считать ее O (1)?

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

Answer 1

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

Вставка значения:

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

Поиск значения:

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

Признавая основную сложность:

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

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