Opgaver - Modul 13

Opgave 1 - HashTable på papir

Denne opgave handler om indsættelse af tal i forskellige former for hashtabeller. I denne opgave skal du ikke programmere, men selv udregne hvordan hashtabellerne kommer til at se ud – anvend papir og blyant!

Følgende tal skal indsættes i en hashtabel i den angivne rækkefølge:

4371   1323   6173   4199   4344   9679   1989   

Hashtabellen har plads til 10 elementer, og hash-funktionen er givet ved

hash(x) = x mod 10.

Bemærk at mod betyder modulu.

Hvorledes ser hashtabellen ud efter indsættelsen af ovenstående tal, når der anvendes

1. Kædereglen (chaining)?
2. Lineær probing?
3. Kvadratisk probing?
4. Dobbelt hashing? Den anden hashfunktion er givet ved hash’(x) = 7 - (x mod 7)

Opgave 2 - HashSet

Et HashSet er et Set baseret på hashing. I et Set må der kun forekomme unikke værdier.

Som tidligere, er der en skabelon der kan bruges, til at løse opgaven. Den findes under / modul13 / Hashing /. Man kan bruge kommandoerne dotnet run og dotnet test - også som tidligere.

Opgaven går ud på at færdiggøre de to implementationer af et HashSet. Interfacet er det samme, men der findes to konkrete implementationer, der skal gøres færdige:

• HashSetChaining.cs: Her mangler remove-metoden.
• HashSetLinearProbing.cs: Her mangler de fleste metoder. Bemærk, at der er en Enum der skal anvendes ved sletning.

Opgave 3 - Rehashing

Lav en forbedret udgave af HashSetChaining der håndterer når arrayet bliver fyldt. Lav en rehash-metode der anvendes fra add-metoden, så antallet af pladser fordobles, når load-faktoren bliver større end 0.75 (dvs. mindst 75% af arrayet er fyldt op). Skriv nogle nye tests der tester, at settet kan fyldes op og stadig fungerer efter hensigten.

Opgave 4 - Udfordring - Lav et HashMap

Lav et HashMap baseret på følgende skabelon. Kollision skal håndteres med kædereglen. Lad hash-funktionen være givet ved hash(x) = x mod N hvor N er længden på arrayet.

Koden herunder indeholder følgende:

• Et interface der beskriver hvilke metoder man skal have med.
• En klasse, som implementererer interface - men implementationen mangler!

using Hashing;

public interface Map<K,V> {
    public V Get(K key);
    public V Put(K key, V value);
    public V Remove(K key);
    public bool IsEmpty();
    public int Size();
}

public class HashMap<K,V> : Map<K,V> {
    // TODO!!
}

Bemærk, at <K,V> er såkaldte type-parametre. Dvs. de sættes til konkrete typer når man laver nye objekter. Klasser og interfaces der har type-parametre kaldes for generics.

Her et et eksempel på hvordan det kunne se ud i praksis:

HashMap<int,string> map = new HashMap<int,string>();