3.8. Zobrazení

Obsah

3.8.1. Reprezentace seznamem
3.8.2. Reprezentace množinou dvojic
3.8.3. Tabulka s rozptýlenými položkami
3.8.4. Tabulka s řetězením synonym
3.8.5. Tabulka s otevřeným adresováním
3.8.6. Úlohy k řešení

Datový typ zobrazení (map) je založen na matematickém pojmu zobrazení, které prvkům z množiny vzorů přiřazuje (nejvýše jeden) prvek z množiny obrazů. Tento datový typ se v mnoha programovacích jazycích označuje také jako asociativní pole; množina vzorů pak odpovídá datovému typu indexu pole a množina obrazů datovému typu hodnoty uložené na zadaném indexu. Proti "obyčejnému" poli nabízí asociativní pole zobecnění v tom smyslu, že typem indexu může být libovolný datový typ, nad kterým je definována alespoň operace porovnání. Z hlediska implementace to ale většinou znamená, že nemůžeme jednoduchou matematickou úpravou hodnoty indexu získat jednoznačně umístění požadovaného prvku, a je tedy nutné pro zpřístupnění prvku využít nějaké formy vyhledávání. To, co nás pak bude zajímat nejvíce, je rychlost, s jakou jsme schopni prvek se zadaným indexem vyhledat, případně uložit.

Příklad: Nejčastěji se asociativních polí využívá ve spojení s indexem typu řetězec znaků. Můžeme pak v některých jazycích používat konstrukce jako
prevod["Po"] = "Pondělí"; 
prevod["Ut"] = "Úterý"; 
...
nazev_dne = prevod[den];

Asociativní pole můžeme chápat také jako vyhledávací tabulku, jejíž řádky jsou označeny indexy (klíči) a ve sloupci jsou uložena odpovídající data. Takovou tabulku pak můžeme implementovat mnoha způsoby, lišícími se od sebe zejména časovou a paměťovou složitostí. Jedná se například o varianty založené na následujících principech:

Vyhledávací tabulku můžeme zjednodušeně popsat následujícím rozhraním:

interface Map { 
   Object put(Object key, Object value); 
   Object get(Object key); 
   Object remove(Object key); 
}

Metoda put() vkládá hodnotu se zadaným klíčem do tabulky a vrací předchozí hodnotu svázanou s tímto klíčem nebo null, pokud tento klíč v tabulce ještě nebyl. Metoda get() vyhledá hodnotu podle klíče, případně při neúspěšném hledání vrátí hodnotu null. Metoda remove() odstraní z tabulky hodnotu se zadaným klíčem, pokud existovala, a vrátí hodnotu svázanou s odstraněným klíčem nebo null, pokud klíč v tabulce nebyl. V dalších odstavcích si ukážeme možné přístupy k implementaci takovéto tabulky.