Lärare: Hans Jernberg
, Pär Eriksson
Olika typer av datastruktur introduceras, som länkadelistor, köer, hashtabeller och träd. För- och nackdelar diskuteras med avseende till snabbhet, minnesresurser och komplexitet som grund för kvalificerade val av datastruktur för att lösa ett specifikt problem.
|
Fö1 Hashtabell (Pär) |
Här lär du dig skapa en egen klass för hashtabell implementation för att hantera bla bilobjekt. Som bucket används en array av länkad lista i vilken vi kan lägga Key_Value par där Key är regnummer och value är bil objektet. Add metoden gås igenom för att kunna lägg till ett bil objekt där key är regnummer och value är bil objektet. I Add används: Hash funktionalitet samt kollisionteknik. Kollisioner hanteras med chaining tekniken där jag använder en länkad lista för att lägg till flera bilar på samma index position. I HashFunctions metod skapas med en DBJ2 algoritmen. Baserat på en sträng får jag via HashFunction en index position där bil objekt ska läggas till eller hämtas ifrån.
|
|
Fö2 Hashtabell -Get Metoden(Pär) |
Här lär du dig att skapa Get metoden där man hämtar ut data baserat på en nyckel, regnummer, och får tillbaka ett value, ett bilobjekt. I Get hanteras den chaining som ev uppstod vid kollision där olika nyckelvärden,regnummer, fick samma index position. Då loopas den länkade listan igenom för att finna matching nyckelvärden,regnummer och då returneras det objekt dvs det matchande bilobjektet
|
|
Fö3 Hashtabell - Remove metoden (Pär) |
Här lär du dig att skapa remove metoden.
|
|
Fö4 Hashtabell - Openadressing (Pär) |
Här lär du dig hur du hantera kollsion med öppenaddresseringsteknik. Exemplet visar att lägga till data där man gör en linjär sökning efter nästa lediga index postion att lägg bil objektet i.
|
|
Fö5 Hashtabell - Openadressing (Pär) |
Här lär du dig hur du hantera kollsion med öppenaddresserings teknik. Exemplet visar att hämta till bildata på regnummer där man gör en linjär sökning för att kolla om bilen finns på nästa lediga indexpositon.
|
|
Fö6 Hashtabell (Hans Edy) |
Hans Edy föreläning om hash tabeller
|
|
Fö7 Öppen adressering (Hans Edy) |
Hans Edy's föreläsning om bla öppenadressering i hashtabeller
|