Я давно использую 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) или даже хуже?
Независимо от того, используете ли вы открытое или закрытое хеширование, вам необходимо разрешать коллизии. При рассмотрении наихудшего случая это вообще не выполняется за постоянное время. Если вы знаете что-то особенное о ключах, вы можете много раз создать идеальный хэш, но в общем случае это не так.
Средняя временная сложность вставки, удаления и поиска в хэш-карте составляет O(1)
на элемент, в худшем случае — O(N)
для всех трех вышеперечисленных операций. Когда хеш-функция зависит от размера элемента (что происходит со строками в предоставленном коде), средняя временная сложность O(1)
не применяется, поскольку сама хеш-функция будет иметь временную сложность больше, чем O(1)
. Другими словами, ответ на ваш ответ — да, если хеш-функция не O(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 столкнутся).
Это n — длина ключа. Когда мы говорим об O структур данных, мы имеем в виду, что
n
— это количество элементов, хранящихся в структуре данных.