Бесконечный поиск в квадратичном зондировании (хэш-таблицы)
Я думаю, что в хэш-таблицах может возникнуть проблема, если мы будем использовать квадратичное зондирование в следующей ситуации;
Предположим, у нас есть таблица размером 10, и она заполнена, за исключением третьего индекса. Наша хеш-функция, скажем, h(x) = x mod(n)
| 10 | 31 | 42 | no value | 64 | 15 | 6 | 77 | 58 | 19 |
Как я знаю, квадратичное зондирование ищет (индекс + i^2), если происходит столкновение. Например, если мы хотим вставить "40" в этой хеш-таблице он ищет следующие позиции.
0 -> 1 -> 4 -> 9 -> 6 -> 5 -> 6 -> 9 -> 4 -> 1 -> 0 -> 1 -> 4 -> ...
Поэтому он продолжает искать позицию, но у него не будет возможности вставить этот элемент в эту хэш-функцию, потому что n^2 mod (10) никогда не будет равно 3. Так что он будет искать место до бесконечности.
Это самый простой случай, который я мог найти, но могут быть и другие подобные ситуации. Так почему мы используем квадратичное зондирование, даже если оно может иметь такую огромную проблему? Есть ли способ искать и избегать такого рода проблем?