3)Hash-таблицы(Таблицы с перемешиванием).

Hash-таблицы с цепочками. Функция хеширования h(<Object>) служит для вычисления индекса в массиве указателей. Объект <Object> встраивается в линейный список. Адрес начала списка – в соответствующем элемента массива.

Hash-таблица с открытой адресацией. Адрес объекта <Object> - в соответствующем элементе массива указателей. Возможны коллизии, если получается одинаковый результат хеширования для двух и более различных объектов. Для разрешения коллизий (т.е. для поиска свободного элемента в массиве указателей) применяются специальные алгоритмы