Associativ array

En associativ array  är en abstrakt datatyp ( ett gränssnitt till ett datalager) som låter dig lagra par av formen "(nyckel, värde)" och stöder operationerna för att lägga till ett par, samt att söka och ta bort ett par genom att nyckel:

• INSERT(nyckel, värde)
• FIND(nyckel)
• REMOVE(nyckel)

Det antas att en associativ array inte kan lagra två par med samma nycklar.

I ett par kallas värdet för det värde som är associerat med nyckeln . Var  är nyckeln , a  är värde . Semantiken och namnen på ovanstående operationer kan skilja sig åt i olika associativa array-implementeringar.

Operationen FIND(key) returnerar värdet som är associerat med den givna nyckeln, eller något speciellt UNDEF-objekt som indikerar att det inte finns något värde associerat med den givna nyckeln. De andra två operationerna returnerar ingenting (förutom kanske om operationen lyckades eller inte).

Ur gränssnittets synvinkel är det bekvämt att betrakta en associativ array som en vanlig array , där inte bara heltal utan också värden av andra typer, såsom strängar, kan användas som index.

Stöd för associativa arrayer finns i många tolkade programmeringsspråk på hög nivå som Perl , PHP , Python , Ruby , Tcl , JavaScript [1] och andra. För språk som inte har inbyggda associativa arrayer finns det många implementeringar i form av bibliotek .

Ett exempel på en associativ array är en telefonkatalog: i det här fallet är värdet kombinationen av " Fullständigt namn + adress", och nyckeln är telefonnumret, ett telefonnummer har en ägare, men en person kan ha flera nummer .

De tre huvudoperationerna kompletteras ofta av andra, de mest populära tilläggen är:

• CLEAR  - radera alla poster
• VARJE  - "kör" genom alla lagrade par,
• MIN  - hitta paret med det lägsta nyckelvärdet,
• MAX  - hitta paret med det maximala nyckelvärdet.

I de två sista fallen är det nödvändigt att jämförelseoperationen definieras på tangenterna.

Associativa arrayimplementationer

Det finns många olika implementeringar av en associativ array.

Den enklaste implementeringen kan baseras på en vanlig array vars element är (nyckel, värde) par. För att påskynda sökoperationen kan du sortera elementen i denna array efter nyckel och utföra en binär sökmetod . Men detta kommer att öka exekveringstiden för operationen att lägga till ett nytt par, eftersom det kommer att vara nödvändigt att "skjuta isär" elementen i arrayen för att placera en ny post i den resulterande tomma cellen.

De mest populära implementeringarna är baserade på olika sökträd . Så, till exempel, i standard -STL- biblioteket för C++-språket implementeras kartbehållaren på basis av ett röd-svart träd . Språken D , Java , Ruby , Tcl , Python använder en av varianterna av hashtabellen . Det finns andra implementeringar också.

Varje implementering har sina egna fördelar och nackdelar. Det är viktigt att alla tre operationerna utförs både i genomsnitt och i värsta fall över tiden , där  är det aktuella antalet lagrade par. För balanserade sökträd (inklusive röd-svarta träd) är detta villkor uppfyllt.

I implementeringar baserade på hashtabeller uppskattas den genomsnittliga tiden som , vilket är bättre än i implementeringar baserade på sökträd. Men detta garanterar inte en hög hastighet för exekvering av en enda operation: tiden för INSERT- operationen uppskattas i värsta fall som . INSERT - operationen tar lång tid när fyllningsfaktorn blir hög och hashtabellindexet behöver byggas om.

Hash-tabeller är också dåliga eftersom de inte kan användas för att implementera snabba ytterligare MIN, MAX-operationer och en algoritm för att kringgå alla lagrade par i stigande eller fallande nycklarordning.

Anteckningar

1. ↑ I JavaScript stöder objekt skapandet av egenskaper med en godtycklig (sträng) nyckel, så de implementerar också de grundläggande egenskaperna för en associativ array. Se: Objekt som associativa arrayer . JavaScript handledning . Datum för åtkomst: 20 december 2012. Arkiverad från originalet 23 december 2012. (obestämd)

Länkar

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