Lecture overview -- Keyboard shortcut: 'u'  Previous page: Klassiske mængedeoperationer -- Keyboard shortcut: 'p'  Next page: Et eksempel på anvendelse af Set -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Play sound for this page -- Keyboard shortcut: 'y'  Page 7 : 35
Forelæsningsnoter i Objekt-orienteret Programmering
Collections og streams
Klasserne HashSet og TreeSet

Vi ser nu på konkrete klasser i Java biblioteket, som implementerer interfacet Set.

Klasserne HashSet og TreeSet implementerer interfacet Set

HashSet garanterer ingen bestemt ordning på elementerne.

TreeSet garanterer at elementerne er ordnet i stigende orden.

TreeSet implementer faktisk et subinterface af Set, nemlig SortedSet. SortedSet kræver at elementerne i mængden implementerer Comparable grænsefladen. Vi ser på Comparable, element ordning og sortering senere i denne lektion. Bemærk at Comparable, som omtalt her, ikke er det samme som den abstrakte klasse Comparable, vi diskuterede i lektionen om klassedesign.

Ordningerne, som der er tale om, kommer til udtryk når vi returnerer en iterator på mængden via operationen iterator().

  • HashSet

    • Mængden er implementeret ved brug af en hashtabel

    • Add, remove og contains operationerne forventes at have konstant tidskompleksitet

    • Den mest effektive Set implementation i praksis

Når vi skriver, at HashSet operationerne har forventet konstant tidskompleksitet, betyder det, at vi ikke kan garantere konstante køretider i worstcase. Den faktiske tidskompleksitet afhænger bl.a. af hashtabellens opfyldningsgrad.

  • TreeSet

    • Mængden er implementeret som en træstruktur

    • Add, remove og contains operationerne garanteres at have logaritmisk tidskompleksitet