ich habe gerade eine C++ Übung vor mir und verstehe dieses
nicht ganz.
Ich kenne aus PHP den Umgang mit Hash (assoz. Array).
Aber ich weiss nicht recht ob die in C++ damit das gleiche
meinen.
Eine Hashtabelle stellt eine mögliche Implementierung eines „assoziativen Arrays“ dar. Dabei handelt es sich um eine Datenstruktur, in der man Schlüssel (und evtl. damit verknüpfte Objekte) effizient ablegen und wiederfinden kann.
[…]
Aber in der Aufgabe steht auch was von
h(key) = key mod p.
Das wiederum versteh ich gar nicht. Was soll das denn mit
einem assoz. Array zu tun haben ?
Mit einem assoz. Array erst mal nichts, mit einer Hashtabelle aber sehr viel.
h ist eine Hash-Funktion, also eine Funktion die einen großen Wertebereich auf einen kleineren (in diesem fall 0 bis p-1) abbildet. Sie verleiht der „Hash“-Tabelle ihren Namen.
Die Hashfunktion ermittelt zu einem gegebenen Schlüsselwert dessen Hashwert. Im Fall der Hashtabelle bestimmt der Hashwert, in welcher Tabellenzelle ein Schlüssel abgelegt wird. Da es sich nicht vermeiden lässt, dass verschiedene Schlüssel auf denselben Hashwert abgebildet werden, braucht man eine Strategie zur Kollisionsbehandlung. Diese kann zum Beispiel so aussehen, dass eine Tabellenzelle nicht ein einzelnes Element enthält, sondern einen Zeiger auf eine Liste von Schlüsseln, die alle denselben Hashwert haben.
Servus
Tom