Asociativní pole

Asociativní pole  je abstraktní datový typ ( rozhraní k datovému úložišti), který vám umožňuje ukládat páry ve tvaru „(klíč, hodnota)“ a podporuje operace přidání páru, stejně jako vyhledávání a mazání páru pomocí klíč:

• INSERT(klíč; hodnota)
• NAJÍT (klávesa)
• ODSTRANIT (klávesa)

Předpokládá se, že asociativní pole nemůže uložit dva páry se stejnými klíči.

V páru se hodnota nazývá hodnota spojená s klíčem . Kde  je klíč , a  je hodnota . Sémantika a názvy výše uvedených operací se mohou v různých implementacích asociativních polí lišit.

Operace FIND(key) vrátí hodnotu přidruženou k danému klíči nebo nějaký speciální objekt UNDEF indikující, že k danému klíči není přiřazena žádná hodnota. Další dvě operace nevrací nic (snad kromě toho, zda byla operace úspěšná nebo ne).

Z hlediska rozhraní je vhodné považovat asociativní pole za běžné pole , ve kterém lze jako indexy použít nejen celá čísla, ale i hodnoty jiných typů, jako jsou řetězce.

Podpora pro asociativní pole se nachází v mnoha interpretovaných programovacích jazycích na vysoké úrovni , jako je Perl , PHP , Python , Ruby , Tcl , JavaScript [1] a další. Pro jazyky, které nemají vestavěná asociativní pole, existuje mnoho implementací ve formě knihoven .

Příkladem asociativního pole je telefonní seznam: v tomto případě je hodnotou kombinace „ Celé jméno + adresa“ a klíčem je telefonní číslo, jedno telefonní číslo má jednoho vlastníka, ale jedna osoba může mít několik čísel. .

Tyto tři hlavní operace jsou často doplněny dalšími, přičemž nejoblíbenějšími rozšířeními jsou:

• VYMAZAT  - vymazání všech záznamů
• KAŽDÝ  - "proběhnout" všechny uložené páry,
• MIN  - najděte pár s minimální hodnotou klíče,
• MAX  - najděte pár s maximální hodnotou klíče.

V posledních dvou případech je nutné, aby byla operace porovnání definována na klávesách.

Implementace asociativních polí

Existuje mnoho různých implementací asociativního pole.

Nejjednodušší implementace může být založena na pravidelném poli, jehož prvky jsou dvojice (klíč, hodnota). Chcete-li urychlit operaci vyhledávání, můžete prvky tohoto pole seřadit podle klíče a provést binární metodu vyhledávání . To však prodlouží dobu provádění operace přidání nového páru, protože bude nutné „odstrčit“ prvky pole, aby bylo možné umístit nový záznam do výsledné prázdné buňky.

Nejoblíbenější implementace jsou založeny na různých vyhledávacích stromech . Takže například ve standardní knihovně STL jazyka C++ je mapový kontejner implementován na základě červeno-černého stromu . Jazyky D , Java , Ruby , Tcl , Python používají jednu z variant hash tabulky . Existují i ​​další implementace.

Každá implementace má své výhody a nevýhody. Je důležité, aby všechny tři operace byly provedeny jak v průměru, tak v nejhorším případě v čase , kde  je aktuální počet uložených párů. Pro vyvážené vyhledávací stromy (včetně červeno-černých stromů) je tato podmínka splněna.

V implementacích založených na hashovacích tabulkách se průměrný čas odhaduje jako , což je lepší než u implementací založených na vyhledávacích stromech. To však nezaručuje vysokou rychlost provádění jedné operace: čas operace INSERT se odhaduje v nejhorším případě jako . Operace INSERT trvá dlouho, když se faktor plnění zvýší a index hashovací tabulky je třeba znovu sestavit.

Hashovací tabulky jsou také špatné, protože je nelze použít k implementaci rychlých dodatečných operací MIN, MAX a algoritmu pro obcházení všech uložených párů ve vzestupném nebo sestupném pořadí klíčů.

Poznámky

1. ↑ V JavaScriptu objekty podporují vytváření vlastností s libovolným (řetězcovým) klíčem, takže také implementují základní vlastnosti asociativního pole. Viz: Objekty jako asociativní pole . Výuka JavaScriptu . Datum přístupu: 20. prosince 2012. Archivováno z originálu 23. prosince 2012. (neurčitý)

Odkazy

• NIST's Dictionary of Algorithms and Data Structures: Associative Array
• NIST's Dictionary of Algorithms and Data Structures: Association List