Zdrojový kód: INCLUDE\UTIL\HASH.INC, UTIL\HASH.ASM
HASH - Hashovaný seznam
V některých případech jsme postaveni před následující úkol - máme rozsáhlý seznam položek, každou položku můžeme charakterizovat nějakou hodnotou, potřebujeme rychle vyhledat položku s určitou hodnotou. Typickým příkladem je disková cache - máme sadu bufferů s uschovaným obsahem sektoru, každý buffer je charakterizován číslem sektoru na disku. Vyhledání bufferu s daným číslem sektoru sekvenčním postupem (postupné zkoušení všech bufferů) by byla značně časově náročná operace. Na uložení bufferů do pole, jehož indexem by bylo číslo sektoru, by nám nestačila paměť. V těchto případech použijeme hashovaný seznam.
V hashovaném seznamu ukládáme položky do pole s pevnou velikostí, indexem v poli však není skutečná hodnota prvku, ale jeho zkrácená verze - hashovací klíč. Například z 32-bitového čísla sektoru získáme 1-bajtový hashovací klíč součtem všech 4 bajtů čísla sektoru. Je zřejmé, že v takovém případě bude více prvků se stejným hashovacím klíčem. Proto v každé pozici pole nebude uložen jeden prvek, ale seznam prvků se stejným hashovacím klíčem. Jedná se tedy o kompromis mezi prohledáváním dlouhého seznamu prvků a rozměrným indexovým polem.
K sestavení hashovaného seznamu bychom mohli využít dvojitě linkovaný seznam LIST, který je uzavřen do kruhu. Tím by ale značně vzrostly paměťové nároky na záhlaví seznamu, protože každá položka záhlaví vyžaduje 2 ukazatele (to je 8 bajtů). Vzhledem k rozměrům záhlaví hashovaného seznamu by takový seznam byl paměťově dost náročný. Proto použijeme pozměněnou variantu seznamu. Prvky seznamu budou opět obsahovat ukazatele na následující a předešlou položku. Přesněji řečeno ukazatel na předešlou položku bude ukazovat na ukazatel následující položky v předešlé položce, ale vzhledem k tomu, že ukazatel na následující položku je umístěn na začátku popisovače, je význam ukazatele stejný. Hlavní změna spočívá v tom, že seznam není kruhově uzavřený, ale je zakončen nulovým ukazatelem na následující položku. Díky tomu nemusí položka záhlaví seznamu obsahovat ukazatel na předešlou položku a může být tedy jen 4-bajtová.
Inicializace popisovače seznamu
Nahrazení položky seznamu jinou položkou
