7eb0bf1f

Использование цепочек переполнения


Это один из наиболее очевидных способов разрешения коллизий. Если по смыслу в элементах массива хранятся записи типа T, то в данном случае к записи добавляется поле типа ссылки на T. При возникновении коллизии по причине включения новой записи для нового элемента выделяется динамическая память, и он включается в конец линейного списка, который начинается от первичного элемента массива. Если коллизия возникает при поиске ключа, то список переполнения просматривается либо до момента нахождения требуемого ключа, либо до конца, что означает отсутствие искомой записи (рисунок 4.23).


4.23.

Метод цепочек переполнения легко реализуется, понятен, но потенциально приводит к излишним расходам памяти.

Содержание раздела