Методы сортировки и поиска

       

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


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


Рис. 4.23.

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

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