Uppgift 4 våren 2012

Uppgiften ska lämnas till din övningsledare på övningen den 10/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, StringDictionary.java, 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 metoden hashCode() i Javas String-klass för att implementera din hashfunktion. Som vanligt ska du skriva och lämna in testkod.

Alternativ 1

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>>();

Alternativ 2

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.

Alternativ 3

Man kan också strunta i att använda generiska typer och färdig listkod och istället göra en enkel och minneseffektiv implementation från grunden. Det kanske är det bästa alternativet. Följande kodskiss kan då vara en bra utgångspunkt.

public class StringHash implements StringDictionary { 
    private ListElement[] table;

    private static class ListElement {
    	String value;
    	ListElement next;
    }

    // TODO
}

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.