carlos1976
Grünschnabel
Hallo zusammen,
kennt sich jemand HashMaps und Sondierungsverfahren aus?
Versteh nur Bahnhof.. Vielen Dank im Voraus und ein schönes Wochenende!
Hier der Code. (Beschreibung s. unten)
Die Klasse NewHashMap soll vervollständigt werden, in der zur Vermeidung von Kollisionen Sondierungsverfahren verwendet werden.
Implementiert werden sollen der Konstruktor, den Destruktor und die folgenden Sondierungsvarianten:
1. Lineares Sondieren (LINEAR):
s(i, key) = (key + i) mod m_size, i: Sondierungsschritt
2. Quadratisches Sondieren (QUADRATIC):
s(i, key) = (key + i2) mod m_size, i: Sondierungsschritt
3. Doppeltes Hashing (DOUBLE):
s(i, key) = (key + i * key) mod m_size, i: Sondierungsschritt
Die Verfahren werden über einen Konstruktorparameter übergeben.
Hierfür sollen die definierten Enum-Typen LINEAR, QUADRATIC und DOUBLE benutzt werden.
Wenn kein Platz mehr im Array gefunden werden kann, soll eine entsprechende
Fehlermeldung ausgegeben werden. Das Sondieren soll nach 100 Schritten abgebrochen werden, wenn noch immer keine freie Stelle im Array gefunden wurde.
Es sollte reichen, die Instanziierung des HashMap- Objektes anzupassen. Array-Größe= 25.
kennt sich jemand HashMaps und Sondierungsverfahren aus?
Versteh nur Bahnhof.. Vielen Dank im Voraus und ein schönes Wochenende!
Hier der Code. (Beschreibung s. unten)
Code:
//Enumeration zur Unterscheidung zwischen den Sondierungsverfahren
enum Method {LINEAR, QUADRATIC, DOUBLE};
/** Die Klasse bildet eine Struktur, die integer-Schlüssel auf string-Objekte abbildet und
dazu verschiedene Sondierungsverfahren benutzt. */
class NewHashMap
{
public:
/** Der Konstruktor
n ist die Größe des Arrays, das von der Hashfunktion benutzt wird.
method ist das Sondierungsverfahren. */
NewHashMap(int n, Method method)
{
//Membervariablen initialisieren
//Speicherplatz allokieren etc.
//...
}
/** Der Destruktor */
~NewHashMap()
{
//Speicherplatz freigeben etc.
//...
}
/** Gibt die HashMap aus. */
void print()
{
for (int i = 0; i < m_size; i++)
if (m_array[i] != NULL)
cout << "(" << m_array[i]->key << ", "
<< m_array[i]->value << ")\n";
else
cout << "(-, -)\n";
}
/** Liefert den Wert zum angegebenen Key zurück */
string get(int key)
{
//Element suchen
//solange nicht gefunden, je nach Sondierungsmethode weitersuchen.
//...
return "Value?!"; //Muss geändert werden.
}
/** Fügt den Schlüssel key mit der Zeichenkette value zur HashMap hinzu */
void put(int key, string value)
{
//Index berechnen
//Wenn Kollision, dann je nach Sondierungsmethode weiter springen.
//Wenn freier Platz gefunden: Einordnen.
}
private:
/** Array, welches DataElems speichert */
DataElem** m_array;
/** Die Größe des Arrays */
int m_size;
/** Die gewählte Sondierungsmethode */
Method m_method;
};
int main(int argc, char* argv[])
{
// Anzahl der Elemente, die gespeichert werden sollen
const int n = 16;
// Array mit irgendwelchen keys...
int keys[n] = {17, 8, 23, 3, 2,
128, 256, 16, 9, 10,
4, 0, 99, 5, 7, 1};
// Array mit irgendwelchen Wörtern...
string values[n] = {"Baum", "Hase", "Wurzel", "Schnee", "Flasche",
"Gold", "Beamer", "Papier", "Schere", "Kreide",
"Buch", "Apfel", "Zahl", "Heft", "CD", "Kabel"};
/************************************************************************/
/* Aufruf */
/************************************************************************/
//NewHashMap map(25, DOUBLE);
// Hier werden die Elemente in die HashMap gesteckt (key/value - Paare).
for (int i = 0; i < n; i++)
map.put(keys[i], values[i]);
// Print array to terminal;
cout << "Map content: \n";
map.print();
return 0;
}Die Klasse NewHashMap soll vervollständigt werden, in der zur Vermeidung von Kollisionen Sondierungsverfahren verwendet werden.
Implementiert werden sollen der Konstruktor, den Destruktor und die folgenden Sondierungsvarianten:
1. Lineares Sondieren (LINEAR):
s(i, key) = (key + i) mod m_size, i: Sondierungsschritt
2. Quadratisches Sondieren (QUADRATIC):
s(i, key) = (key + i2) mod m_size, i: Sondierungsschritt
3. Doppeltes Hashing (DOUBLE):
s(i, key) = (key + i * key) mod m_size, i: Sondierungsschritt
Die Verfahren werden über einen Konstruktorparameter übergeben.
Hierfür sollen die definierten Enum-Typen LINEAR, QUADRATIC und DOUBLE benutzt werden.
Wenn kein Platz mehr im Array gefunden werden kann, soll eine entsprechende
Fehlermeldung ausgegeben werden. Das Sondieren soll nach 100 Schritten abgebrochen werden, wenn noch immer keine freie Stelle im Array gefunden wurde.
Es sollte reichen, die Instanziierung des HashMap- Objektes anzupassen. Array-Größe= 25.
