Definition:
Beim Chaining ist die Hashtabelle ein Array von Listen. Jede Liste nimmt Elemente mit gleichem Hashwert auf.
Definition:
Einzelne Kollisionen entstehen, wenn eine Liste bereits ein Element enthält. Dann wird das Element am Ende der Liste angehängt.
Komplexität:
Die Zugriffskosten auf ein Element mit entsprechen natürlich der Länge der Liste :
- Worst Case: wenn eine Liste alle Elemente enthält,
- Average Case: