next up previous contents
Nächste Seite: Sondieren Aufwärts: Hashing Vorherige Seite: Hashing   Inhalt

Chaining

Definition:
Beim Chaining ist die Hashtabelle ein Array von Listen. Jede Liste $ i$ nimmt Elemente mit gleichem Hashwert $ h(k)=i$ 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 $ h(k)=i$ entsprechen natürlich der Länge der Liste $ i$:
- Worst Case: wenn eine Liste alle Elemente enthält, $ O(n)$
- Average Case: $ O(1+\beta/2)$



2003-10-08