На этом шаге рассмотрим хеш-таблицу - одну из самых полезных базовых структур данных.
Начнем знакомство с хеш-таблицами с примера. Представьте, что вы продавец в магазинчике. Когда клиент покупает товары, вы проверяете их цену по книге. Если записи в книге не упорядочены по алфавиту, то поиск слова "апельсины" в каждой строке займет слишком много времени. Фактически вам придется проводить простой поиск, а для этого нужно проверить каждую запись, а это займет времени О(n). Если же книга упорядочена по алфавиту, вы сможете воспользоваться бинарным поиском, время которого составляет всего O(log n). Но как организовать поиск данных в книге?
Обратимся к структурам данных. Пока вам известны две структуры данных: массивы и списки. Книгу можно реализовать в виде массива:
Каждый элемент массива на самом деле состоит из двух элементов: названия товара и его цены. Если отсортировать массив по имени, вы сможете провести по нему бинарный поиск для определения цены товара. Это означает, что поиск будет выполняться за время O(log n). Но нам нужно, чтобы поиск выполнялся за время О(1). В этом вам помогут хеш-функции.
На следующем шаге рассмотрим понятие хеш-функции.
