Почему мы можем сказать, что сложность hashmap равна O(1)

Я давно использую hashmap и всегда считаю, что его сложность равна O(1).

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

Сегодня я прочитал хеш-функцию, как показано ниже, которая хэширует строку в хеш-код:

unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Очевидно, что цикл while есть, поэтому его сложность равна O(n).

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

Это n — длина ключа. Когда мы говорим об O структур данных, мы имеем в виду, что n — это количество элементов, хранящихся в структуре данных.

tgdavies 18.12.2020 04:29

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

wcochran 18.12.2020 04:29

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

Telescope 18.12.2020 04:32
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
3
799
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

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

В-третьих, это не хеш-карта. Это хэш-функция. Он превращает комплексное значение в числовое для сравнения (более формально, он отображает объекты из пространства размера N в пространство размера M, где N>M). Это не обещает быть O (1), это совершенно отдельная концепция от хэш-карты. Хэш-карта использует хеш-функцию для вставки объектов в очень большой массив и, таким образом, получает время O(1) для чтения и записи, если хэш-функция достаточно хороша, чтобы коллизии были редки. Сама хэш-функция может быть любой сложности, в зависимости от данных и того, как она работает. Строковые хэши обычно имеют значение O (n) в строке, потому что вы хотите попытаться сделать ее уникальной (если вы остановитесь после, скажем, 4 символов, все строки с этими первыми 4 столкнутся).

Другие вопросы по теме