Programmering för språkteknologer II. HT 2008.

Hashtabeller, stödpunkter

• Nycklar: de värden vi går in med.
• Mängd vs mappning
• Bas: ett fält (array). Storleken en viktig parameter.
• Hashfunktion: nycklar avbildas på heltal inom det intervall fältet täcker, 0,..., n-1 om fältet är av längden n.
• Hashfunktionen bör:
  • sprida ut nycklarna så jämnt som möjligt (detta är en klurig fråga)
  • gå snabbt att beräkna
• Kollisioner/krockar måste hanteras:
  • Öppen hashning (separate chaining): Varje cell i fältet knyts till en (lämplig sorts) lista med värden. Varje plats i hashtabellen kan därmed husera godtyckligt antal värden. Pris: En listhanteringskostnad tillkommer.
  • Sluten hashning: Vid insättning, då kollision uppstår, väljer man ett annat index t.ex. genom att räkna framåt (på ett eller annat sätt) tills man hittar ett ledigt index, använda en andra hashfunktion, etc. Pris: Kräver en serie av hashfunktioner. Sökning måste titta på första platsen, andra platsen, etc. tills man hittar det man letar efter eller en tom plats. Detta leder till ytterligare behov av klurigheter om man skall hantera borttagning av element. Man måste kunna sätta in ett värde med betydelsen "f.d. upptagen plats".
• Fyllnadsgrad (load factor): anger hur många av fältets platser som är utnyttjade. För Java's hashstrukturer anger man en maximal fyllnadsgrad.
• Omhashning (rehashing) innebär att man bygger om en hashtabell, typiskt genom att bygga upp den utifrån ett fält med fler platser. Detta måste göras t.ex. om tabellen överskrider den maximala fyllnadsgraden. (Tar tid!)
• Användning: Hashtabeller används typiskt när uppslagning skall gå snabbt och vi har stora mängder nycklar. Ett språkteknologiskt lexikon är en typisk tillämpning.
• I Java: Färdiga generiska klasser i Java Collection Framework: HashSet‹E› och HashMap‹K,V›. Konstruktorerna tillåter oss att ange antalet platser och maximal fyllnadsgrad.