Problem beim Hashen

Charlie.

Hallo allerseits,

ich habe versucht, mit einfachsten Mitteln (auch wenn es erfahrene Programmierer wsl zum Weinen bringt) eine Hashtabelle anzulegen und zu füllen. Das Problem ist jetzt, dass der Wert 4 nicht auf seinen Platz gehasht wird und auch die 25 nicht (ich weiß, die Kollisionsbehandlung ist mies, aber ich wollte es nur mal für diese 4 Werte ausprobieren, ob es so mal funktionieren würde).

Hättet ihr einen Tipp, warum die 4 und die 25 nicht auf "ihre Plätze" kommen? Wahrscheinlich ist der Fehler offensichtlich, aber ich komme einfach nicht darauf

Wäre also sehr dankbar für einen Tipp, wo der Fehler sein könnte

MfG,
Charlie

#include <iostream>
using namespace std;

int main(){

	int keyarray[4]={1,4,17,25};
	int stelle=0;
	int hashtable[8]={0};
    	int letztestelle;

	cout<<"Keyarray"<<endl;

	for (int i=0; i<=3; i++) {
		cout<<keyarray[i]<<" ";
	}

	cout<<endl;

	cout<<"Unbefuellte Hashtabelle"<<endl;

	for (int i=0; i<7; i++) {
		cout<<hashtable[i]<<" ";
	}

	cout<<endl;

	for (int i=0; i<7; i++){

		if ((hashtable[i]==0)){

			stelle=(keyarray[i]) % 7; 
			hashtable[stelle]=keyarray[i];

		}

		if (i>=10) {
			letztestelle=keyarray[i] % 10;
		}

		if (i<10) {
			letztestelle=keyarray[i] % 1;
		}

		if (hashtable[i]!=0) {
			stelle=keyarray[i] % 7+letztestelle*3 % 7;
		}

	}

	cout<<"Befuellte Hashtabelle"<<endl;

	for (int i=0; i<=7; i++){
		cout<<i<<"  "<<hashtable[i]<<endl;
	}

	return 0;
}

314159265358979

Ich hab nen Tipp für dich: Benutze einen der std::unordered_ Container.

XSpille

Hallo Charlie.,

ich nehme mal Bezug auf diesen Teil:

for (int i=0; i<7; i++){

        if ((hashtable[i]==0)){ 

            stelle=(keyarray[i]) % 7; 
            hashtable[stelle]=keyarray[i]; 

        } 

        ...
    }

Ich glaube nicht, dass du von 0 bis 6 iterieren willst, oder?
Du möchtest doch wahrscheinlich nur von 0 bis 3 iterieren (Anzahl der Elemente, die du einordnen möchtest)

Nun zu deiner Frage, warum 4 und 25 nicht eingeordnet werden.

Du fügst als erstes eine 1 ein, die an Position 1 landet. Im zweiten Schleifendurchlauf, überprüfst du , ob Position 1 belegt ist und die Bedingung ist nicht erfüllt.

Analog dazu landet die 17 auf Position 3 und für 25 ist die Bedingung nicht erfüllt.

Du möchtest wohl eher etwas wie:

for (int i=0; i<4; i++){

        if ((hashtable[keyarray[i] % 7]==0)){ 

            stelle=(keyarray[i]) % 7; 
            hashtable[stelle]=keyarray[i]; 

        } 

    }

Die 25 wir hier auch nicht eingefügt, da der Platz belegt ist und dann müsste eine Kollisionsbehandlung greifen.

Gruß,
XSpille

Charlie.

Vielen Dank!

Ja ich hatte die Schleife ursprünglich von 0 bis 3, habe das dann aber geändert, da ich dachte, das wäre das Problem..

Und danke, wegen den Plätzen, jetzt, wo du es erklärt hast, ist es logisch Aber alleine komme ich auf solche Fehler fast nie drauf
Also, vielen vielen Dank!!