Хэширование. Способы разрешения коллизий

Выработанная хэш-функция не гарантирует, что все элементы массива будут заполнены соответствующими ключами. Даёт превосходные результаты при заранее известными не очень большого набора ключей в случае динамического исключения или включения ключей. Коллизия – если ключом является последовательность символов, то при применении хэш-функции возникает большая вероятность выработки одного и того же значения для ключей отличающихся небольшим числом символов. Коллизия заключается в том что при попытке занести в таблицу с новым ключом, мы наталкиваемся что элемент уже занят. Одним из выходов является выработка новой хэш-функции увеличенного размера массива и расстановка заново всех элементов массива.

Группы методов: 1) Методы прямой адресации (Ключ, появление которого вызвало коллизию, помещён в один их свободных элементов хэш-таблицы). 2) Методы цепочек (записи, для ключей которого выработано одиночное значение хэш-функцией связывается в линейный список).

1) Линейное зондирование.

Идея Линейного зондирования состоит в том, что сталкиваясь с коллизией при включении записи, мы последовательно рассматриваем массив в поиске первого не занятого элемента, если обнаруживаем, то соответственно в него записывается запись.

Если все элементы массива заняты, то требуется его расширение и новая расстановка элементов.

Если коллизия обнаруживается при поиске, то последовательно рассматриваются следующие элементы массива, пока не будет найдена запись с указанным ключом, либо если не наткнешься на свободный элемент массива.

Достоинство: Его простота, а недостаток состоит в том, что при разрешении коллизии, вторичные элементы массива (прямо не указанные хэш-функцией) обычно сосредоточены в первичных элементах. Заполнение происходит не равномерно => увеличенное число коллизий.

2) Двойное хэширование.

Этот метод применяют для обеспечения равномерного распределения ключей в хэш-таблице. Если при включении или поиска в хэш-таблице происходит коллизия, то к ключу применяется вторичная хэш-функция, значения которой указывают циклическое смещение в массиве от текущего индекса к элементу, который следует включать или в котором искать необходимую запись.

Цепочки переполнения.

Если в элементах массива хранятся записи типа Т, то соответственно к этой записи добавляется поле типа ссылки на Т. При возникновении коллизии по причине включения новой записи. Для нового элемента выдаётся динамическая память, и он включается в конец линейного списка, который начинается от первичного элемента массива.

Если при поиске ключа, то список переполнения ключа до момента требуемого ключа либо до конца, что означает отсутствие ключа.

Приводит к излишним расходам памяти.