Obsah
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.
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.