Een gegevensstructuur kiezen
Bij 1023 sleutels doet lineair zoeken naar een ontbrekende sleutel 1023 vergelijkingen, binair zoeken 10 en een hashtabel met 1023 buckets in het lab hoogstens 6.
Begin bij de vragen die je gaat stellen
Geen structuur is overal het beste in. Elke structuur maakt sommige bewerkingen goedkoop door andere duur te maken. Kies dus door op te sommen wat je programma het vaakst doet. MIT 6.006 splitst de mogelijkheden in twee interfaces. Een reeks bewaart items in een door jou bepaalde volgorde (eerste, tweede, derde) en je vraagt items op positie. Een verzameling bewaart items op sleutel en je vraagt of een sleutel aanwezig is, naar de kleinste sleutel of de volgende na een gegeven sleutel. Een verzameling zonder volgordevragen heet een woordenboek.
Enkele gebruikelijke situaties en de gebruikelijke keuze:
- Items op positie lezen, achteraan toevoegen: een dynamische array (een JavaScript-array).
- Ongedaanmaakgeschiedenis, haakjes koppelen, diepte-eerst zoeken: een stapel, een array die alleen aan het einde wordt gebruikt.
- Taken op aankomstvolgorde, breedte-eerst zoeken: een wachtrij, met een head-index of ringbuffer in plaats van shift op een lange array.
- Dingen op naam of id opzoeken: een hashtabel, in JavaScript Map of Set.
- Sleutels gesorteerd houden tijdens invoegen en verwijderen, de volgende sleutel opvragen: een gebalanceerde binaire zoekboom.
- Veel invoegen en verwijderen op een plek die je al hebt: een gelinkte lijst.
Dezelfde zoekactie in vijf structuren
In het lab hieronder sla je dezelfde sleutels op vijf manieren op en tel je vergelijkingen om er één te vinden. Het zijn 15, 127 of 1023 willekeurige gehele getallen. De ongesorteerde array gebruikt lineair zoeken, de gesorteerde array binair zoeken. De gebalanceerde boom is gebouwd door middelste sleutels eerst in te voegen en is dus zo laag mogelijk. De andere boom is gebouwd uit gesorteerde sleutels en is dus een keten. De hashtabel heeft evenveel buckets als sleutels en telt 1 voor h(k) berekenen.
Sleep om te draaien. Scroll of knijp om te zoomen.
Met 15 sleutels zijn de verschillen klein: lineair zoeken vraagt gemiddeld 8 vergelijkingen en binair zoeken ongeveer 3.3. Met 1023 sleutels niet. Lineair zoeken vraagt gemiddeld 512 en bij een ontbrekende sleutel 1023, terwijl binair zoeken en de gebalanceerde boom nooit meer dan 10 vragen. De ketenboom is even slecht als lineair zoeken. De hashtabel blijft bij elke grootte gemiddeld tussen 2.3 en 2.5 doordat de ketens kort blijven. Het slechtste geval voor 1023 sleutels was in dit lab 6. Daarom is Map de standaardkeuze voor opzoeken en zijn gesorteerde structuren pas de moeite waard als je ook volgorde nodig hebt.
| Op positie | Haal item i op | Vooraan invoegen of verwijderen |
|---|---|---|
| Dynamische array | 1 | n |
| Gelinkte lijst | n | 1 |
| Gesorteerde array | 1 | n |
| Op sleutel | Zoeken | Invoegen | Volgende sleutel |
|---|---|---|---|
| Array of lijst | n | n | n |
| Gesorteerde array | log n | n | log n |
| Hashtabel | gemiddeld 1 | gemiddeld 1 | n |
| Gebalanceerde BST | log n | log n | log n |
Elke cel in deze twee tabellen is de groeisnelheid van de kosten voor n items, volgens de tabellen in de MIT-collegenotities 2, 4 en 7. Hashtabellen en zoekbomen staan alleen in de tweede tabel omdat ze op sleutel werken, niet op positie. In een ongesorteerde array of lijst kost een sleutel invoegen n, omdat je eerst moet controleren of die nog niet aanwezig is. De gesorteerde array zoekt snel maar moet waarden verplaatsen om ruimte voor een nieuwe sleutel te maken.
Map of object?
JavaScript-programma's gebruiken vaak een gewoon object als woordenboek en schrijven prices["apple"]. MDN noemt redenen om Map te verkiezen als sleutels uit gegevens komen: een object heeft een prototype en dus standaardsleutels die met de jouwe kunnen botsen; een Map accepteert elke waarde als sleutel, niet alleen strings en symbolen; de grootte is één eigenschap, map.size; en je doorloopt hem in invoegvolgorde. Objecten blijven de natuurlijke keuze voor records met een vaste reeks benoemde velden.
- 1953: Het IBM-memorandum van H. P. Luhn stelt hashing naar buckets met ketens voor.
- Rond 1956: De IPL van Newell, Shaw en Simon brengt gelinkte lijsten.
- 1957: Bauer en Samelson vragen patent op de stapelmethode aan; Fortran verschijnt met arrays.
- 1962: Adelson-Velsky en Landis publiceren de AVL-boom, de eerste gebalanceerde zoekboom.
- 2015: ECMAScript 2015 voegt Map en Set toe aan JavaScript.
- Hoeveel vergelijkingen doet lineair zoeken naar een ontbrekende sleutel tussen 1023 sleutels?
- Hoeveel vergelijkingen doet binair zoeken tussen 1023 gesorteerde sleutels hoogstens?
- Lineair zoeken over 15 sleutels: wat is het gemiddelde aantal vergelijkingen over alle 15 sleutels?
- Een BST met 127 sleutels in gesorteerde volgorde ingevoegd: hoeveel vergelijkingen voor de grootste sleutel?
- Een teksteditor heeft Ongedaan maken nodig. Welke structuur past?
- Wachtrij
- Stapel
- Hashtabel
- Gesorteerde array
- Een printserver moet taken op aankomstvolgorde verwerken. Welke structuur past?
- Wachtrij
- Stapel
- BST
- Gelinkte lijst gebruikt als stapel
- Je moet vele malen per seconde een gebruikersrecord op id opzoeken. Wat is de gebruikelijke keuze in JavaScript?
- Een array doorzocht met een lus
- Een Map met id als sleutel
- Een stapel
- Een gelinkte lijst
- Je moet sleutels gesorteerd houden tijdens invoegen en verwijderen en vraagt vaak de volgende grotere sleutel. Wat past het best?
- Hashtabel
- Gebalanceerde BST
- Wachtrij
- Ongesorteerde array
- Hoe heet in MIT 6.006 een verzameling zonder volgordebewerkingen?
- een reeks
- een woordenboek
- een stapel
- een wachtrij
- Waarom kan een gewoon object volgens MDN riskant zijn als woordenboek voor sleutels uit gegevens?
- Objecten kunnen geen strings bevatten
- Het prototype brengt standaardsleutels mee die met de jouwe kunnen botsen
- Objecten zijn altijd trager dan arrays
- Objecten vergeten waarden na een seconde
- Kies op basis van de bewerkingen die je het vaakst doet.
- Reeks: array, gelinkte lijst, stapel, wachtrij. Verzameling: hashtabel, BST.
- Voor 1023 sleutels: lineair zoeken tot 1023 vergelijkingen, binair zoeken en een gebalanceerde boom tot 10.
- Map is het gebruikelijke woordenboek in JavaScript; gebruik een gebalanceerde boom als je ook volgorde nodig hebt.
Bronnen van deze cursus (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Geraadpleegd: 2026-10-18