Asociativní pole - Associative array
Ve vědě o počítačích , jako asociativní pole , mapy , tabulky symbolů , nebo slovník je abstraktní datový typ složený z kolekce z (klíč, hodnota) dvojice tak, že každá možná objeví klíčové nejvýše jednou ve sbírce. Nesmí být zaměňována s asociativními procesory
Operace spojené s tímto datovým typem umožňují:
- přidat pár do sbírky;
- odstranit pár ze sbírky;
- upravit existující pár;
- vyhledejte hodnotu spojenou s konkrétním klíčem.
Implementace asociativních polí představuje problém slovníku , klasický problém počítačové vědy: úkol navrhnout datovou strukturu, která udržuje sadu dat během operací „vyhledávání“, „mazání“ a „vkládání“. Dvě hlavní řešení problému se slovníkem jsou hashovací tabulka a vyhledávací strom . V některých případech je také možné vyřešit problém pomocí přímo adresovaných polí , binárních vyhledávacích stromů nebo jiných specializovanějších struktur.
Mnoho programovacích jazyků obsahuje asociativní pole jako primitivní datové typy a jsou k dispozici v softwarových knihovnách pro mnoho dalších. Obsahově adresovatelná paměť je formou přímé hardwarové podpory pro asociativní pole.
Asociativní pole mají mnoho aplikací včetně takových základních programovacích vzorů, jako je memoizace a vzor dekorátoru .
Název nepochází z asociativní vlastnosti známé v matematice. Vyplývá to spíše z toho, že hodnoty spojujeme s klíči.
Operace
V asociativním poli je asociace mezi klíčem a hodnotou často známá jako „mapování“ a stejné slovo mapování lze také použít k označení procesu vytváření nového přidružení.
Operace, které jsou obvykle definovány pro asociativní pole, jsou:
- Přidat nebo vložit : přidání nového páru do kolekce, mapování nového klíče na jeho novou hodnotu. Argumenty této operace jsou klíč a hodnota.
- Změnit přiřazení : nahraďte hodnotu v jednom z párů, které jsou již v kolekci, mapování stávajícího klíče na novou hodnotu. Stejně jako u vložení jsou argumenty této operace klíčem a hodnotou.
- Odebrat nebo odstranit : Odebrání páru ze sbírky, odpojení daného klíče od jeho hodnoty. Klíčem je argument této operace.
- Vyhledávání : najděte hodnotu (pokud existuje), která je vázána na daný klíč. Argumentem této operace je klíč a hodnota je vrácena z operace. Pokud není nalezena žádná hodnota, vyvolávají některé implementace asociativních polí výjimku , zatímco jiné vytvářejí pár s daným klíčem a výchozí hodnotou typu hodnoty (nula, prázdný kontejner ...).
Často místo přidání nebo opětného přiřazení existuje jedna nastavená operace, která přidá nový pár, pokud již neexistuje, a jinak jej znovu přiřadí.
Asociativní pole mohou navíc zahrnovat i další operace, jako je určení počtu mapování nebo konstrukce iterátoru, který bude smyčkovat všechna mapování. Obvykle pro takovou operaci může být pořadí, ve kterém jsou mapování vrácena, definováno implementací.
Multimap zobecňuje asociativní pole tím, že více hodnot, které mají být spojeny s jedním klíčem. Obousměrný mapa přidruženým abstraktní datový typ, ve kterém mapování fungovat v obou směrech: každá hodnota musí být spojena s jedinečný klíč, a druhý vyhledávací operace trvá hodnotu jako argument a vyhledá klávesu spojenou s touto hodnotou.
Příklad
Předpokládejme, že soubor výpůjček poskytnutých knihovnou je zastoupen v datové struktuře. Každou knihu v knihovně může současně rezervovat pouze jeden čtenář knihovny. Jeden čtenář však může mít možnost vyzkoušet více knih. Proto informace o tom, které knihy jsou vydávány, pro které mohou být čtenáři zastoupeny asociativním polem, ve kterém jsou knihy klíčem a čtenáři hodnotami. Použitím zápisu z Pythonu nebo JSON by datová struktura byla:
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
Vyhledávací operace na klíči „Velká očekávání“ by vrátila „John“. Pokud John vrátí svou knihu, způsobilo by to operaci smazání a pokud by Pat knihu rezervoval, způsobilo by to operaci vložení, což by vedlo k jinému stavu:
{
"Pride and Prejudice": "Alice",
"The Brothers Karamazov": "Pat",
"Wuthering Heights": "Alice"
}
Implementace
U slovníků s velmi malým počtem mapování může mít smysl implementovat slovník pomocí seznamu přidružení , propojeného seznamu mapování. S touto implementací je čas na provedení základních slovníkových operací lineární v celkovém počtu mapování; je však snadné jej implementovat a konstantní faktory jeho doby provozu jsou malé.
Další velmi jednoduchou implementační technikou, použitelnou, když jsou klíče omezeny na úzký rozsah, je přímé adresování do pole: hodnota pro daný klíč k je uložena v buňce pole A [ k ], nebo pokud neexistuje mapování pro k pak buňka uloží speciální sentinelovou hodnotu, která indikuje nepřítomnost mapování. Kromě toho, že je tato technika jednoduchá, je rychlá: každá operace se slovníkem vyžaduje konstantní čas. Požadavek na prostor pro tuto strukturu je však velikost celého prostoru klíčů, takže je nepraktický, pokud není prostor klíčů malý.
Dva hlavní přístupy k implementaci slovníků jsou hashovací tabulka nebo vyhledávací strom .
Implementace hashovací tabulky
Nejčastěji používanou obecnou implementací asociativního pole je hashovací tabulka : pole kombinované s hashovací funkcí, která odděluje každý klíč do samostatného „kbelíku“ pole. Základní myšlenkou hashovací tabulky je, že přístup k prvku pole prostřednictvím jeho indexu je jednoduchá operace s konstantním časem. Proto je průměrná režie operace pro hashovací tabulku pouze výpočtem hashe klíče v kombinaci s přístupem k odpovídajícímu segmentu v poli. Tabulky hash jako takové obvykle fungují v čase O (1) a ve většině situací překonávají alternativy.
Hashovací tabulky musí umět zvládnout kolize : když hashovací funkce mapuje dva různé klíče do stejného segmentu pole. Dva nejrozšířenější přístupy k tomuto problému jsou oddělené řetězení a otevřené řešení . V odděleném řetězení pole neukládá samotnou hodnotu, ale ukládá ukazatel na jiný kontejner, obvykle seznam přidružení , který ukládá všechny hodnoty odpovídající hash. Na druhou stranu, v otevřeném adresování, pokud je nalezena kolize hash, pak tabulka hledá prázdné místo v poli pro uložení hodnoty deterministickým způsobem, obvykle při pohledu na další bezprostřední pozici v poli.
Otevřené adresování má nižší poměr chyb mezipaměti než oddělené řetězení, když je tabulka většinou prázdná. Jakmile se však tabulka zaplní více prvky, výkon otevřeného adresování exponenciálně degraduje. Navíc oddělené řetězení ve většině případů využívá méně paměti, pokud nejsou položky velmi malé (méně než čtyřnásobek velikosti ukazatele).
Implementace stromů
Samovyvažující binární vyhledávací stromy
Dalším běžným přístupem je implementace asociativního pole se samovyvažujícím binárním vyhledávacím stromem , jako je strom AVL nebo červeno-černý strom .
Ve srovnání s hash tabulkami mají tyto struktury výhody i slabiny. Nejhorší výkon self-balancing binárních vyhledávacích stromů je výrazně lepší než u hashovací tabulky, s časovou složitostí ve velkém O zápisu O (log n ). To je na rozdíl od hashovacích tabulek, jejichž nejhorší výkon zahrnuje všechny prvky sdílející jeden segment, což má za následek časovou složitost O ( n ). Navíc, stejně jako všechny binární vyhledávací stromy, samovyvažující binární vyhledávací stromy udržují své prvky v pořádku. Traverzování jeho prvků tedy probíhá podle vzoru od nejmenšího k největšímu, zatímco procházení hashovací tabulky může mít za následek, že jsou prvky ve zdánlivě náhodném pořadí. Hashovací tabulky však mají mnohem lepší průměrnou časovou složitost než samovyrovnávací binární vyhledávací stromy O (1) a jejich nejhorší výkon je při použití dobré hashovací funkce velmi nepravděpodobný .
Stojí za zmínku, že k implementaci segmentů pro hashovací tabulku, která používá oddělené řetězení, lze použít binární vyhledávací strom s vlastním vyvažováním. To umožňuje konstantní vyhledávání průměrných případů, ale zajišťuje výkon O (log n ) v nejhorším případě . To však přináší do implementace extra složitost a může způsobit ještě horší výkon u menších hashovacích tabulek, kde čas strávený vkládáním do stromu a vyvažováním je delší než čas potřebný k provedení lineárního vyhledávání na všech prvcích propojeného seznam nebo podobná datová struktura.
Jiné stromy
Asociativní pole mohou být také uložena v nevyvážených binárních vyhledávacích stromech nebo v datových strukturách specializovaných na určitý typ klíčů, jako jsou radixové stromy , try , Judy pole nebo stromy van Emde Boas , ačkoli schopnost těchto implementačních metod v porovnání s hash tabulkami liší se; například stromy Judy zůstávají indikovány k výkonu s menším množstvím účinnosti než hashovací tabulky, zatímco pečlivě vybrané hashovací tabulky obecně fungují se zvýšenou účinností ve srovnání s adaptivními radixovými stromy, s potenciálně většími omezeními pro typy dat, se kterými mohou pracovat. Výhody těchto alternativních struktur vyplývají z jejich schopnosti zvládat operace nad rámec základních asociativních polí, jako je nalezení mapování, jehož klíč je nejblíže dotazovanému klíči, když dotaz není sám přítomen v sadě mapování.
Srovnání
| Základní struktura dat | Vyhledávání nebo mazání | Vložení | Objednáno | ||
|---|---|---|---|---|---|
| průměrný | nejhorší případ | průměrný | nejhorší případ | ||
| Hash stůl | O (1) | O ( n ) | O (1) | O ( n ) | Ne |
| Samovyvažující binární vyhledávací strom | O (log n ) | O (log n ) | O (log n ) | O (log n ) | Ano |
| nevyvážený binární vyhledávací strom | O (log n ) | O ( n ) | O (log n ) | O ( n ) | Ano |
| Sekvenční kontejner párů klíč – hodnota (např. Seznam přidružení ) |
O ( n ) | O ( n ) | O (1) | O (1) | Ne |
Objednaný slovník
Základní definice slovníku nenařizuje objednávku. K zajištění pevného pořadí výčtu se často používají uspořádané verze asociativního pole. Uspořádaný slovník má dva smysly:
- Pořadí výčtu je pro danou sadu klíčů vždy deterministické seřazením. To je případ stromových implementací, přičemž jedním zástupcem je
<map>kontejner C ++. - Pořadí výčtu je nezávislé na klíči a místo toho je založeno na pořadí vložení. To je případ „uspořádaného slovníku“ v .NET Framework a Pythonu .
S druhým smyslem uspořádaných slovníků se setkáváme častěji. Lze je implementovat pomocí seznamu přidružení nebo překrytím dvakrát propojeného seznamu nad normálním slovníkem. Druhý přístup, který CPython používá před verzí 3.6, má tu výhodu, že zachovává potenciálně lepší složitost jiné implementace. CPython 3.6+ dělá slovníky seřazené rozdělením hashovací tabulky na vložené uspořádané pole kv párů a řídké pole („hashovací tabulka“) indexů.
Jazyková podpora
Asociativní pole lze implementovat v jakémkoli programovacím jazyce jako balíček a mnoho jazykových systémů je poskytuje jako součást své standardní knihovny. V některých jazycích nejsou integrovány pouze do standardního systému, ale mají speciální syntaxi, často využívající předplatné podobné poli.
Vestavěná syntaktická podpora pro asociativní pole byla zavedena v roce 1969 společností SNOBOL4 pod názvem „tabulka“. TMG nabídlo tabulky s řetězcovými klíči a celočíselnými hodnotami. MUMPS vytvořil vícerozměrná asociativní pole, volitelně perzistentní, svou klíčovou datovou strukturu. SETL je podporoval jako jednu z možných implementací sad a map. Většina moderních skriptovacích jazyků, počínaje AWK a zahrnující Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language , Go a Lua , podporuje asociativní pole jako primární typ kontejneru. V mnoha dalších jazycích jsou k dispozici jako funkce knihovny bez speciální syntaxe.
V Smalltalk , Objective-C , .NET , Python , REALbasic , Swift , VBA a Delphi se jim říká slovníky ; v Perlu , Ruby a Seed7 se jim říká hashe ; v C ++ , Java , Go , Clojure , Scala , OCaml , Haskell se jim říká mapy (viz mapa (C ++) , unordered_map (C ++) , a Map); v Common Lisp a Windows PowerShell se jim říká hashovací tabulky (protože oba obvykle používají tuto implementaci); v Maple a Lua se jim říká tabulky . V PHP mohou být všechna pole asociativní, kromě toho, že klíče jsou omezeny na celá čísla a řetězce. V jazyce JavaScript (viz také JSON ) se všechny objekty chovají jako asociativní pole s klíči s hodnotou řetězce, zatímco typy Map a WeakMap berou libovolné objekty jako klíče. V Lua se používají jako primitivní stavební blok pro všechny datové struktury. V aplikaci Visual FoxPro se jim říká Kolekce . Jazyk D má také podporu pro asociativní pole.
Trvalé skladování
Mnoho programů využívajících asociativní pole bude v určitém okamžiku muset tato data uložit v trvalejší podobě, například do počítačového souboru . Běžným řešením tohoto problému je zobecněný koncept známý jako archivace nebo serializace , který vytváří textovou nebo binární reprezentaci původních objektů, které lze zapsat přímo do souboru. To se nejčastěji implementuje v základním objektovém modelu, jako je .Net nebo Cocoa, které obsahují standardní funkce, které převádějí interní data do textové podoby. Program může vytvořit úplnou textovou reprezentaci jakékoli skupiny objektů voláním těchto metod, které jsou téměř vždy již implementovány v základní třídě asociativního pole.
U programů, které používají velmi velké datové sady, není tento druh ukládání jednotlivých souborů vhodný a je vyžadován systém správy databází (DB). Některé systémy DB nativně ukládají asociativní pole serializací dat a následným uložením serializovaných dat a klíče. Jednotlivá pole pak lze načíst nebo uložit z databáze pomocí klíče, na který je odkazujete. Tyto úložiště klíč – hodnota se používají mnoho let a mají historii tak dlouhou jako běžnější relační databáze (RDB), ale nedostatek standardizace mimo jiné omezil jejich použití na určité specializované role. Pro tyto role byly ve většině případů použity RDB, i když ukládání objektů do RDB může být komplikované, problém známý jako nesoulad objektově relační impedance .
Po c. 2010 , potřeba vysoce výkonných databází vhodných pro cloud computing a bližšího sladění vnitřní struktury programů, které je používají, vedla k renesanci trhu s klíčovými hodnotami. Tyto systémy mohou nativně ukládat a načítat asociativní pole, což může výrazně zlepšit výkon v běžných pracovních postupech souvisejících s webem.