• Hauptseite
• Artikel
• Bearbeiten
• Versionen
• Spezialseiten
• Hochladen

C-sharp-gestreute-Speicherung

Problembeschreibung

• datenobjekte sollen in einer Menge gespeichert werden
• Jedes Datenobjekt ist durch einen Schlüsselwert eindeutig zu identifizieren
• Die Speicher- und Suchoptionen sollen möglichst schnell ausgeführt werden.

Modell

Operationen

• insert(4711)
• find(4711)
• delete(4711)

Neben dem Schlüssel enthalten die Objekte ggf. auch andere Daten!

Beispiel

Studentendatensätze

Objekt1: 123456, Hans Meier, 24943,... Objekt2: 654321, Karl Otto, ... Objekt3: 996633, Donald Duck,...

Versuch

Implementation mit einer linearen Liste

• insert(Objekt mit Schlüssel) -> vorn einfügen (schnell, Ordnung ist eh egal)
• find(Objektt mit Schlüssel) -> linear suchen f(n)
• löschen(Objekt mit Schlüssel) -> linear suchen und löschen.

=> ist bei langen Listen zu langsam.

Hashverfahren

• Die Daten werden in einemFeld der Länge (n) indiziert gespeichert.
• der eigentliche Datenwert wird als Index verwendet.
• es gibt eine hashfunktion h, die für jeden Schlüssel einen Index liefert

index = h(Schlüssel)

• für C, C++, C#, Java

Beispiel

• aus dem Schlüssel wird mit der Funktion h ein sog Hashcode errechnet, der dann der Index für die Speicherzelle im Feld ist.
• Das Objekt wird dann (mit seinem Schlüssel) in dem entsprechend indizierten Feld gepseichert.

Wenn das Verfahren, wie beschrieben, arbeitet, so ist die Komplexität der insert, find und delet Operation von der Ordnung 1 O(1) d.h. != f(n)

Probleme

• Anzahl möglicher Schlüssel ist möglicherweise erheblich größer als die Anzahl der Indizes ( es sollen i.A. auch strings als Schlüssel verwendet werden!
• es gibt i.A. keine ideale Hashfunktion, die für jeden Schlüssel einen separarten Index liefert -> Kollision

Forderungen

1. Die Hashfunktion muss effizient berechenbar sein
2. Die Hashfunktion soll Indizes erzeugen, die möglichst Gleichmäßig im Bereich 0..n-1 verteilt sind.
3. Kollisionen müssen erkannt und aufgelöst werden

Beispiel

Hashfunkton für String-Schlüssel

a

• ASCII- / UNICODE- Werte der einzelnen Stringzeichen addieren
• mit der Modulofunktion (%) den Indexbereich begrenzen

aus Labor 5

 
virtual public uint getHashCode(uint hashTableLaenge)
{
   uint hashCode = 0;
   for(int i = 0; i < info.length; i++) //info ist der Schlüssel
   {
      hashCode=hashCode + info[i];
   }
   return hashCode %hashTableLaenge; //% ist der Modulo operator, liefert den Rest
}
 

• Verteilung mit starken Häufungen -> je ein Berg pro Stringlänge (4-10 Zeichen ergibt 7 Berge)

// hier Bild einfügen

• die Lücke wird niemals aufgefüllt
• Wertebereich der char-Summanden :
  • kleinster Wert : "Aaaa" -> 356
  • größter Wert : "Zzzzzzzzzz" -> 1188
• Für Tabellen > 1189 Elemente völlig ungeeignet
• Die Summation ist kommutativ, d.h. h(Abc) == h(Acb) etc. -> die Position eines Zeichens im String wird nicht berücksichtigt

b

verbesserte Hashfunktion

Idee

Die Bits des gesamten String als Zahl interpretieren.

=> Zeichen der Strings werden entsprechend Ihrer Position bewertet.

dezimal

hier

• es entstehen sehr große Werte, insbes. bei langen Strings
• Wertebereich wird überschritten
• ev. aufwändige Berechnung der Potenzen

also

• kleineren Faktor wählen: z.B. 37
• Horner-Schema verwenden

Seien die UNICODE Werte der einzelnen Zeichen eines Schlüsselstrings der Länge 4, so ist: mit dem Horner Schema:

Ergebnis

• Verteilung ist brauchbar
• für sehr lange Strings zu langsam
• evtl. nur Teilstrings verwenden

zur Implementation

• Schema: nur die Schleife erweitern
• mit C#: uint verwenden (größerer Wertebereich, bei Überlauf fängt der Wert wieder von vorne an, keine negativen Zahlen) (uint.Max + 1 -> 0)

Labor

• Vergleich mit String.GetHashCode() -> modulo nicht vergessen.

Kollisionsauflösung

a) seperate chaining (eigenständige Verkettung)

• pro Index eine lineare Liste anlegen
• bei Kollision
  • Element der Liste zufügen oder
  • Element linear suchen oder
  • Element linear suchen und löschen
• lange Liste bei hoher Belegung / hohe Kollisionsdichte, d. h. lineares Suchen

// hier Bild einfügen (Array erweitert durch lineare Liste)

b) probing (lineares Sondieren)

• bei einer Kollision wird im Array
  • linear ab Hashcode ein nächster freier Platz gesucht und dort eingefügt
  • linear ab Hashcode der Platz des gesuchten Elements gesucht
  • linear ab Hashcode der Platz des gesuchten Elements gesucht und gelöscht

Einfügeoperation

// hier Bild einfügen

Die Suchfunktion

• Testet ob Element belegt ist
• muss beim Erreichen des Tabellenendes vorn weitermachen
• muss terminieren falls alle Felder durchsucht wurden

Suchen

• ähnlich dem Einfügen, aber es wird getestet, ob das Element den gesuchten Schlüssel enthält
• es wird maximal bis zum nächsten freien Platz gesucht

Löschen

• erst suchen
• falls gefunden, Element nicht löschen, sondern nur als gelöscht markieren, da sonst der Suchalgorithmus nicht mehr functioniert

Ergebnis:

• ok, wenn die Belegung nicht zu hoch ist
• Suchzeiten steigen, wenn sich sog. Cluster bilden (zusammenhängende Bereiche)
• echtes Löshen ist nicht möglich -> bei zu hoher Belegung, die Tabelle neu aufbauen

c) quadratisches Sondieren

um die Clusterbildung zu reduzieren, wird beim Einfügen, Suchen und Löschen nicht linear, sondern quadratisch vorgegangen.

Sei die ursprüngliche Hashposition, so werden statt der Indices: H_0, H_0 + 1, H_0 +2, H_0 + 3... sondern H_0, H_0 + 1, H_0 +4 usw. betrachtet

allgemein

Die i-te Position ergibt sich durch H_i = [H_0 + i] mod n

Probleme

1) aufwändige Berechnung (Quadrat + Modulo in der Suchschleife)

2) wann terminiert die Suche, wann ruden alle Feldelemente komplett besucht? oder werden überhaupt alle Feldelemente durchsucht?

zu 1)

• Modulo Funkton ersetzen.
  • Falls Tebellenende erreicht -> Tabellenlänge abziehen
• Quadrat ersetzen

H_i = H_0 + i^2

H_(i-1) = H_0 + (i-1)12

H_i - H_(i-1) = i^2 -(i-1)^2

             = i^2  (i^2 - 2i + 1
             = 2i - 1

H^(i) = H_i-1 + 2i -1

zu 2)

Behauptung Wenn die belegung der Tabelle < 50% und die Tabellenlänge eine Primzahl ist, wird beimquadratischen Sondieren immer ein Platz zum Eintragen gefunden(Beweis siehe Proki)

Rehashing

• Erreicht die Belegung 50%, so wird die Tabellengröße angepasst z.B.

N_neu = nächste Primzahl(2 * N_alt)

• es entstehen durch N_neu neue Hachcodes => ungbedingt neue Tabelle anlegen und alle vorhandenen Elemente mit insert einfügen. (nicht Index-to-index copy)
• "Tabelle voll" Test wird durch den ersten Schritt ersetzt

Ergebnis

linares und quadratisches sortieren: Belegung Komplexität

 10%                        O(1)
 50%                        O(1)
 80%                        O(log_2N)
 98%                        O(N)