Вспомним про хеш Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определенным алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Результат преобразования называется хешем. Хеш-функции применяются в следующих случаях: Контрольная сумма MD5 —  алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института в 1991 году...

Заметки: Теперь самое интересное. Время: Напомню, что О(1) — не моментальное время, а одинаковое всегда. Поиск в массиве с одним элементом и с миллиардом займет одинаковое время. Мы видим, что поиск в таблицах не уступает массивам, а вставка и удаление быстры как в связанных списках. Но в худшем способе все плохо, поэтому важно избегать коллизий (когда много котиков в одной квартире). Коэффициент заполнения вычисляется по формуле: количество элементов в хеш-таблице делим на общее количество элементов (всех котиков делим на количество квартир в доме)...