Заметки:
- Хеш-функция — это функция, которая получает любые данные и возвращает число.
- Она обязательно должна быть последовательной и всегда возвращать одно число для одинаковых данных. Например, если мы постоянно передаем Барсика, то для него всегда будет возвращаться один номер квартиры, а не разные.
- Разным данным соответствуют разные числа. Если мы передаем Барсика, то получим в ответ номер квартиры 4. Если передаем Мурзика, то в ответ никак не можем получить 4 (можем, но об этом позже).
- Хеш-функция знает размер массива и возвращает только действительные индексы. Грубо говоря, мы всегда знаем сколько квартир в доме заполнено котами.
- Если соединить хеш-функцию и массив, то получаем хеш-таблицу. В таблицах определяется место хранения элементов при помощи хеш-функций.
- Хеш-таблицы работают очень быстро и это их главный плюс. Почему работают быстро? Там используются массивы для хранения данных, поэтому обращение к элементам быстрое. Про массивы глава здесь: https://zen.yandex.ru/media/android_junior/grokaem-algoritmy-massivy-i-sviazannye-spiski-chast-3-61a7d94a9d60417bd77ba7c4
- Хеш-таблица состоит из ключей и значений (это как номер квартиры и котики, которые в ней живут). Она идеально подходит, если хотим создать связь, отображающую один объект на другой или найти значение в списке. Также хеш-таблицы часто используют для кэширования.
- Чуть выше я писала, что одному котику соответствует один номер квартиры, но в реальности так бывает не всегда.
- Коллизия — двум ключам назначается один элемент массива (два котика живут в одной квартире). В итоге создается связанный список и, увы, тогда плюсы хеш-таблицы сводятся на нет и поиск замедляется.
- Выбор хеш-функции очень важен. Ключи должны распределяться равномерно по всему хешу.
- Если списки слишком длинные, то работа сильно замедляется (если котиков в одной квартире слишком много, то искать котика становится сложнее).
Теперь самое интересное. Время:
Напомню, что О(1) — не моментальное время, а одинаковое всегда. Поиск в массиве с одним элементом и с миллиардом займет одинаковое время.
Мы видим, что поиск в таблицах не уступает массивам, а вставка и удаление быстры как в связанных списках.
Но в худшем способе все плохо, поэтому важно избегать коллизий (когда много котиков в одной квартире).
Коэффициент заполнения вычисляется по формуле: количество элементов в хеш-таблице делим на общее количество элементов (всех котиков делим на количество квартир в доме).
Коэффициент заполнения больше 1 означает, что количество элементов превышает доступное место в массиве (например: 100 котиков, а квартир всего 80. Значит какие-то котики живут вместе).
С ростом коэффициента заполнения приходится изменять размер таблицы. Расширение начинается с создания нового массива, который обычно вдвое больше предыдущего. Потом переносим элементы.
Чем меньше коэффициент заполнения, тем таблица работает более эффективно. В этом случае маленькая вероятность, что два котика будут жить в одной квартире, а значит не будет списков и поиск будет работать за О(1).
Правило: изменяйте размер, когда коэффициент заполнения превышает 0.7
Изменение размеров занимает много времени, поэтому оно не должно быть часто.
