На предыдущем занятии мы разобрали, что такое хеш-функция. Сейчас мы продолжим изучать как внутри устроены контейнеры unordered map и unordered set. Они основаны на так называемых хеш-таблицах. Давайте рассмотрим как хеш-таблица устроена. Она состоит из нескольких корзин, по которым складываются объекты, и, как мы уже знаем из прошлого занятия, для получения индекса корзины применяется хеш-функция. Это все выглядит очень просто, пока мы не вспомним о существовании коллизии. Напомним, коллизия - это когда корзина уже занята другим объектом. Попытаемся добавить в хеш-таблицу автомобильный номер, для которого хеш-функция выдает индекс корзины 227, но эта корзина уже занята другим номером с другими буквами и из другого региона. Что же делать? Не нужно бояться. Существует несколько способов разрешения коллизий, и один из наиболее распространённых - метод цепочек. Этот метод заключается в том, что вместо самих объектов в корзинах хранятся списки объектов. При попытке вставить объект в корзину, сначала проверяется, нет ли его уже в списке, и если нет, то объект добавляется. Таким образом, в случае возникновения коллизий в корзине оказывается более одного объекта. Давайте ещё раз повторим, как устроены цепочки. Мы берём новый автомобильный номер. Функция говорит, что индекс для него равен 227. Затем мы понимаем, что корзина уже не пуста, в ней уже лежат какие-то номера. В результате мы складываем новый номер в эту же корзину в конец списка. Таким образом, цепочки могут удлинятся и удлинятся при вставках, но обычно на практике такие цепочки не становятся слишком длинными. Те хеш-таблицы, которые широко распространены, устроены таким образом, чтобы цепочки оставались короткими, но подробное рассмотрение этого механизма поддержки коротких цепочек, к сожалению, выходит за рамки нашего курса. Сейчас мы рассмотрели, что происходит при вставке объекта в хеш-таблицу. Другие операции - поиск, удаление - работают похожим образом. Все операции состоят из двух основных этапов: сначала с помощью хеш-функции для объекта вычисляется индекс корзины, и, если корзина не пуста, происходит поиск объекта по списку последовательно, сравнивая его со всеми имеющимися. Теперь давайте поговорим о сложности операций в хеш-таблицах, таких как вставка, поиск и удаление. Это сложность складывается из двух основных слагаемых: первая из них - это вычисления хеш-функции. На практике используются хеш-функции, которые вычисляются очень быстро, за константное время. Второе слагаемое - это поиск объекта в корзине. Если цепочки короткие, то можем считать, что время тоже константное, и, как мы уже отметили, на практике используется реализации хеш-таблиц, поддерживающие короткие цепочки. Итак, в этом видео мы узнали, что в основе unordered контейнеров лежат хеш-таблицы и рассмотрели, как они работают. Собственно unordered set хранит в хеш-таблице ключи, а unordered map хранится в них пары "ключ - значение". Также мы разобрались, почему основные операции в этих контейнерах работают в среднем за константное время. На следующем занятии мы рассмотрим, как устроены обычные контейнеры map и set.
