Uppgift 4 våren 2011
Uppgiften ska lämnas till din övningsledare på övningen den 11/2.
För godkänt måste du ha gjort samtliga deluppgifter.
Det är tillåtet att göra enstaka fel och misstag men det
är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med
någon uppgift så finns det som vanligt hjälp att få på labbarna.
Hashtabell
Hashtabeller finns inbyggda i Java i form
av klasserna HashMap
och HashSet
samt metoderna equals
och hashCode
i klassen Object
.
För att kunna använda dessa effektivt behöver man
förstå hur en hashtabell fungerar.
Det ska vi lära oss i den här uppgiften.
Börja med att läsa den här texten om hashtabeller.
Implementationsuppgift
Du ska implementera följande gränssnitt med hjälp av en hashtabell.
/**
* An interface describing a dictionary of strings.
* The dictionary cannot contain duplicate strings.
*
* @author Stefan Nilsson
* @version 2008-01-13
*/
public interface StringDictionary {
/**
* Adds the given string to this table.
* Returns <code>true</code> if the dictionary
* did not already contain the given string.
*
* Complexity: O(1) expected time.
*/
public boolean add(String s);
/**
* Removes the given string from this dictionary
* if it is present. Returns <code>true</code> if
* the dictionay contained the specified element.
*
* Complexity: O(1) expected time.
*/
public boolean remove(String s);
/**
* Returns <code>true</code> if the string is
* in this dictionary.
*
* Complexity: O(1) expected time.
*/
public boolean contains(String s);
}
Hashtabellens storlek (antalet listor) ska anges när
man skapar en ny tabell. Använd gärna din implementation av
länkade listor från föregående uppgift och använd gärna metoden
hashCode()
som finns i alla Javaklasser
(den deklareras i java.lang.Object
)
för att implementera din hashfunktion.
Som vanligt ska du skriva och lämna in testkod.
Den här uppgiften bjuder på oväntade problem eftersom vektorer
och generiska typer fungerar dåligt tillsammans i Java. Det finns
två (någorlunda bra) lösningar på problemet. Antingen undviker
man vektorer och använder en ArrayList
i stället.
Då kan man deklarera och skapa hashtabellen på följande sätt:
ArrayList<List<String>> table = new ArrayList<List<String>>();
Om man hellre vill använda vektorer, till exempel av
effektivitetsskäl, så dyker det upp oväntade problem.
Man kan nämligen inte skapa en vektor av stränglistor
i Java på ett typsäkert sätt. Följande, till synes
naturliga, kod new LinkedList<String>[size]
fungerar inte.
StringHash.java är en mall
som visar hur man gör för att komma runt problemet.
Skriftlig uppgift
Beräkna tidskomplexiteten i medelfall för sökning,
insättning och borttagning i en
- osorterad vektor,
- sorterad vektor,
- osorterad enkellänkad lista,
- sorterad enkellänkad lista,
- hashtabell (du kan anta att antalet element är lika med
hashtabellens storlek).
Låt n vara antalet element i datastrukturen och
presentera lösningen i en tabell med tre rader och fem kolumner.
Som vanligt ska du också motivera dina svar.