Как программист, вы могли использовать Hash maps / Unordered-map в C ++ для хранения пар ключ-значение.
Время, затраченное на Hashmaps / Unordered map в C ++:
- Для вставки O (1)
- Удалить - O (1)
- Найти это O (1)
Давайте выясним, как на самом деле хранятся эти значения.
Кроме того, слышали ли вы об амортизированной временной сложности? Это описано в конце.
Сохранение пары "ключ-значение"
В Hashmap данные ключ-значение хранятся в контейнере (например, в массиве).
Ключ данных сначала хешируется с помощью некоторой хеш-функции.
Предполагать:
- Размер контейнера = n
- Хеш-функция: (клавиша% n)
Пусть n = 5
Давайте сохраним пару "ключ-значение" как {10, 3}, т.е. map [10] = 3
- Здесь ключ = 10
- Ключ хешируется как - ›(10% 5) = 0
Таким образом, контейнер [0] будет хранить пару "ключ-значение" {10, 3}.
Таким образом, если нам нужно сохранить другую пару "ключ-значение", предположим, что {15, 7} т.е. map [15] = 7
- Ключ = 15
- Хешируется как = (15% 5) = 0
Но в контейнере [0] уже есть данные {10, 3}, поэтому возникнет коллизия.
Чтобы избежать этой коллизии, каждый индекс контейнера хранит пары ключ-значение в форме узлов связанного списка, то есть контейнер представляет собой массив ячеек, указывающих на связанные списки.
Каждая ячейка контейнера указывает на связанный список записей «ключ-значение», которые имеют то же значение хэш-функции, что и их ключ.
Помимо ключа и значения, каждый узел связанного списка будет содержать указатель на следующий узел своего собственного связанного списка.
Когда более одного ключа хешируется в один и тот же индекс контейнера «i», сначала проверяется, присутствует ли этот ключ уже в связанном списке контейнера [i] -
- если он присутствует, его значение обновляется
- в противном случае в связанном списке контейнера [i] создается новый узел для хранения новой пары "ключ-значение".
Затраченное время - O (контейнер [i])
Где контейнер [i] - номер. различных ключей, хешированных в индекс i.
Но мы слышали, что временная сложность вставки составляет O (1), верно?
(Сложность времени объясняется в конце)
В случае {15, 7} будет создан другой узел в контейнере [0], в котором будет храниться пара "ключ-значение" {15, 7}.
Поиск ключа
Теперь, если нам нужно найти наличие / значение ключа, мы сначала будем хешировать ключ
Например - поиск ключа 10
- Хешируется как (10% 5) = 0
Затем перейдите к хешированному индексу в контейнере -
т.е. контейнер [0] - здесь мы найдем связанный список, и если в этом связанном списке хранится более одной пары ключ-значение, то это займет время -
- O (контейнер [i]) для поиска
Но это время обычно считается O (1)
Причина. Поскольку размер контейнера обычно велик, а хеш-функция сделана так, что после хеширования не многие ключи перекрываются с одним и тем же контейнером.
Вот почему вставка и удаление элемента также занимают около O (1) времени.
Но что, если наша хеш-функция недостаточно хороша?
Тогда наихудшая временная сложность может быть O (n).
Амортизированное время
Это способ выразить временную сложность, когда алгоритм имеет очень плохую временную сложность только время от времени, помимо временной сложности, которая случается большую часть времени.
Используя это определение в нашем примере, временная сложность, которая происходит -
- Только время от времени / худший случай - O (n) → когда все ключи сталкиваются с одним и тем же индексом контейнера
- В большинстве случаев это O (1) → когда в основном все ключи хешируются в разные индексы контейнера.
Мы можем улучшить эту временную сложность наихудшего случая, изменив способ, которым каждая ячейка контейнера содержит записи.
Если мы используем сбалансированный BST (двоичное дерево поиска) вместо связанного списка, наша временная сложность наихудшего случая может быть улучшена с O (n) до O (log (n)).
Каждый узел пары "ключ-значение" будет выглядеть как -
Это все. Надеюсь, вы хорошо поняли эту концепцию.
Спасибо за чтение! :).
Я хотел бы поблагодарить сэр Баниприт Сингх Рахеджа за рецензирование статьи. : D
