BD-2st-1.2-w06.tresc-1.1-Slajd33
Łańcuchowanie
Technika łańcuchowania polega na przechowywaniu w szczelinie dodatkowo wskaźnika do tzw. obszaru przepełnienia (ang. overflow space). Służy on do przechowywania wszystkich rekordów ulegających kolizji w danej szczelinie. Rekordy w obszarze przepełnienia tworzą listę.
Rozważmy rysunek ze slajdu. Przyjmijmy, że pierwszy rekord ("rekord 1") jest umieszczany w szczelinie o adresie 1, zgodnie z pewną funkcją haszową. Kolejny rekord ulega kolizji w szczelinie 1 i jest umieszczany w obszarze przepełnienia o adresie M ("rekord 2 - kolizja"). We wskaźniku do obszaru przepełnienia szczeliny 1 jest umieszczany adres szczeliny przechowującej pierwszy rekord z kolizji, czyli adres M. Przyjmijmy dalej, że kolejny rekord ulega kolizji w szczelinie 1 i jest on umieszczany w kolejnej wolnej szczelinie obszaru przepełnienia. W naszym przypadku jest to "rekord 3 - kolizja" umieszczony w szczelinie M+1. Adres tej szczeliny jest zapisywany w polu wskaźnika do obszaru przepełnienia szczeliny M.
NULL w polu wskaźnika do obszaru przepełnienia oznacza brak wskaźnika.
