Nein nicht HaSch, sondern Hash :)
Kurze Frage, (vielleicht) lange Antwort :

Was ist ein Hash ?

Ich hab irgendwo gelesen, dass das irgendein Wert ist mit dem man einen Index machen kann, aber verstanden hab ich das nicht :).

afaik ist eine hash ein array, bei dem die einzelnen elemente name haben, statt nur index nummern.

guten rutsch übrigens

sccar

...das is zwar der uebelst gehackteste kleine bastard, den ich je gesehen habe, aber dafuer sauschnell. {Tron}

@Sccar: ziemlich weit daneben

@thinktank:
ein hashtabelle ist eine datenstruktur, die es ermoeglicht elemente anhand eines schluessels (hash) in durchschnittlich O(1) zuzugreifen

also angenommen du hast eine liste mit namen und telefonnummern
n = anzahl der eintraege in der liste

jetzt hast du eine telefonnummer und willst rausfinden, zu wem die gehoert
wenn deine liste eine unsortierte liste ist dauert das O(n)

wenn es eine (nach tel-nummern) sortierte liste ist dauert es mit binaerer suche O(ld(n)) ld = logarithmus dualis, logartithmus zur basis 2
bei einem binaerbaum ebenfalls O(ld(n)) [ist ja quasi das gleiche]

fuer eine hashtabelle brauchst du erstmal etwas vorarbeit...
dazu machst du aus jeder tel-nummer einen hash, das ist die sog. hashfunktion
diese kann alles moegliche sein, sollte jedoch gut gewaehlt werden
z.b. quersumme oder summe aus vorwahl + eigenliche nummer
der hash wird noch mit der anzahl der eintraege in der hashtabelle modulot
diese anzahl sollte eine primzahl sein (ist effektiver)
also dann: hash = hashfunktion(tel_nummer) % 1023

jetzt baust du die eigentliche hashtabelle:
jeden eintrag aus der urspruenglichen liste traegst du an dem index ein, den die hashfunktion fuer diesen eintrag angibt

es kann auch vorkommen, dass 2 tel-nummern den selben hash erzeugen, dann muss 'sondiert' werden, das heisst nach einem bestimmten schema vershoben, aber das waere jetzt zu kompliziert...

fertig!
wenn du jetzt einen namen zu einer tel-nummer suchst, berechnest du einfach den hash fuer diese nummer und schaust bei dem index nach und voila! mit einem versuch hast du das geschuchte gefunden

ich hoffe das war einigermasen verstaendlich und hilfreich...

'KEINE PANIK' - aus der Triologie in fuenf Baenden von Douglas Adams

'FÜR DEINN FERD' - aus 'Gevatter Tod' von Terry Pratchett

Bei hash sucht man halt nicht, sondern findet. (Wie mein info lehrer sagen würde)

because our freedom sits at the end of a gun
we're all here getting beat up and held back
we're all here digging knives from our backs

hmm... keine schlechte definition (;

'KEINE PANIK' - aus der Triologie in fuenf Baenden von Douglas Adams

'FÜR DEINN FERD' - aus 'Gevatter Tod' von Terry Pratchett

mkay , soweit einigermaßen verstanden, aber was ist O ( ) ?
Was ist binäres Suchen ?
Wieso Primzahlen ? ( Sind die selten beim "hashmaking" ? )

Jedenfalls ist das ziemlich praktisch :). Nur um zu checken, ob ichs kapiert hab :

Also wir nehmen mal an, dass die gesuchte Tel.-Nummer = 112 ist.

die Hashfunktion :

int Telefonnummern[32];
vector<char*> Namen;

char* hasharray[32];

int hash(int nummer)
{
// Quersumme berechnen
return quersumme % 32;
}

void CreateHashTable( void )
{
for (int i; i < Namen.size();i++)
{
hasharray[hash(Telefonnummern[i])] = Namen[i];
}
}

char* GetNameByTelNumber(int number)
{
return hasharray[hash(number)];
}

void main()
{
CreateHashTable();
cout << GetNameByTelNumber(112) << endl;
getchar();
}

Ausgabe :

Feuerwehr :D

Geht das so ? :) Ok, ich werde den Standard Container hash_map beim nächsten Mal benutzen :).

@Tron: Nicht immer mit wilden Begriffen um sich schmeißen, die die anderen nicht auf Anhieb kapieren. Das ist dann nämlich ein sehr schlechter Erklärstil =)

@Thinktank: Das O() ist eine - sagen wir mal - fiktive Funktion, mit der man besonders in der Informatik den Aufwand eines Algorithmus berechnet. Mit Aufwand meint man hier meistens die theoretische Dauer eines Algorithmus, ehe das gewünschte Ergebnis verfügbar ist. Theoretisch daher, weil der Algorithmus auf einer 8068er CPU erheblich länger dauern könnte als auf einem Pentium IV.

Wenn man also anhand eines Algorithmus den Aufwand O(2n) rausbekommt - infolge der mathematischen Grundlage des Algorithmus - dann beträgt der Aufwand genau 2*n, wobei n die Anzahl der auszuführbaren Schritte darstellt. Man strebt eigentlich immer einen Aufwand von O(1) an (O(0) ist eigentlich unmöglich, da ja selbst eine simple Addition in seiner Gesamtheit genau 1 Schritt ist). Ungünstig sind exponentielle Aufwände wie O(n²) oder noch schlimmer wie O(2^n) usw. Dann wird bei zunehmender Dauer des Algorithmus der Aufwand zur Berechnung des Ergebnisses naehzu unwirtschaftlich, wenn nicht gar unmöglich. Das betrifft vor allem den Zeitaufwand und die Kapazität der verfügbaren Ressourcen der Hardware (wie RAM oder HD-Platz).

Ein simples Beispiel wäre hier die RSA-Verschlüsselung, die auf Primzahlen basiert (den Algorithmus will hier jetzt nicht aufführen). Zum Knacken eines RSA-Schlüssels mit maximaler Schlüsselgröße müßten zum heutigen Zeitpunkt alle Computer der Welt ihre Rechenleistung zusammenlegen und dann viele Millarden Jahre rechnen, was einen Aufwand darstellt, der nicht vertretbar ist.

Zum HASH-Problem noch ein paar Worte:

Es gibt eigentlich 2 grundlegende Probleme bei Hash-Algorithmen:

- Wie behandelt man Kollisionen?
- Wie findet man überhaupt gute Hashfunktionen?

Bei der ersten Frage gibt es drei Möglichkeiten:

- Die externe Verkettung (Separate Chaining)
- Die interne Verkettung (Coalesced Hashing)
- ohne Verkettung (Offene Addressierung -> Linear Probing)

Bei der zweiten eigentlich nur zwei zu erreichende Ziele:

- Schnelle Berechenbarkeit
- Wenige Kollisionen

Du solltest Dir ein schlaues Algorithmenbuch für deine Sprache zulegen (z.B. die Bücherreihe vom Papst der Algorithmen, Prof. Sedgewick) und mal die Suchmaschinen zu den obigen Begriffen quälen, denn wenn ich jetzt anfangen würde, die ganzen Methoden des Hashings darzulegen... nee nee =)

Cu

K:R-I)Z++
"CSS ist cascading style sheets. Und nicht so'n Ranzspiel." - dp
In memory of Voice († 2005/03/30)

@Kriz:
tschuldige, da ist wohl der ex-info-schuelerstudi mit mir durchgegangen (;

'KEINE PANIK' - aus der Triologie in fuenf Baenden von Douglas Adams

'FÜR DEINN FERD' - aus 'Gevatter Tod' von Terry Pratchett

Hrhr. Kriz beschuldigt andere dessen, was er selbst tut. Was bitte ist externe / interne Verkettung?

Ich hab jetzt aber keine Lust danach zu suchen. Womöglich hab ich das alles selber schon verwendet, ohne es zu wissen ;)

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

öhm.... hilfö?

Hmmm , kommt mir irgendwie bekannt vor :) . Ist fast so was wie der Wirkungsgrad in der Physik. Muss mich dann halt durch die Suchmaschine quälen :).