Hashtabell

Inom datavetenskap är hashtabell en datastruktur där data sparas tillsammans med en nyckel. Positionen i strukturen beräknas med en hashfunktion. Ofta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor, detta eftersom:

• Sökning i en osorterad vektor tar linjär tid;
• i en sorterad vektor kan man använda binärsökning som är mycket effektiv, men då tar istället insättningarna linjär tid;
• i en länkad lista kan man göra insättningar på konstant tid, men sökningen blir linjär.