faecher:informatik:oberstufe:adt:set:implementationen:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:adt:set:implementationen:start [14.11.2021 18:17] – [Variante 3: Hashtable] sbelfaecher:informatik:oberstufe:adt:set:implementationen:start [14.11.2021 18:42] (aktuell) – [Ist eine Zahl in der Menge enthalten?] sbel
Zeile 37: Zeile 37:
 </code> </code>
  
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_091.png |}}+{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_091.png500 |}}
  
 Der binäre UND-Operator verknüpft zwei ''int''-Zahlen (nach Umwandlung in die Binärdarstellung) und setzt im Ergebnis ein Bit auf 1, wenn die entsprechenden Bits in beiden Operanden auf 1 gesetzt sind. Der binäre UND-Operator verknüpft zwei ''int''-Zahlen (nach Umwandlung in die Binärdarstellung) und setzt im Ergebnis ein Bit auf 1, wenn die entsprechenden Bits in beiden Operanden auf 1 gesetzt sind.
Zeile 52: Zeile 52:
  bitvektor = bitvektor | 64; // neuer Wert 89  bitvektor = bitvektor | 64; // neuer Wert 89
 </code> </code>
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_092.png |}}+{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_092.png?500 |}}
  
 Der binäre ODER-Operator verknüpft zwei ''int''-Zahlen und setzt im Ergebnis ein Bit auf 1, wenn mindestens eines der entsprechenden Bits in den beiden Operanden auf 1 gesetzt ist. Der binäre ODER-Operator verknüpft zwei ''int''-Zahlen und setzt im Ergebnis ein Bit auf 1, wenn mindestens eines der entsprechenden Bits in den beiden Operanden auf 1 gesetzt ist.
Zeile 76: Zeile 76:
 </code>  </code> 
  
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_093.png |}}+{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_093.png?500 |}}
  
 ==== Zahlbereichserweiterung ==== ==== Zahlbereichserweiterung ====
Zeile 84: Zeile 84:
 Die k-te Zahl der ArrayList repräsentiert damit die Elemente mit den Werten 32·k bis 32·k+31. Die k-te Zahl der ArrayList repräsentiert damit die Elemente mit den Werten 32·k bis 32·k+31.
  
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_094.png |}}+{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_094.png?600 |}}
  
 Das Element ''n'' wird also durch das Bit ''n%32'' in der Zahl ''daten[n/32]'' repräsentiert. Das Element ''n'' wird also durch das Bit ''n%32'' in der Zahl ''daten[n/32]'' repräsentiert.
Zeile 157: Zeile 157:
 </WRAP> </WRAP>
  
 +==== Kollisionen ====
 +
 +"Aber was macht man, wenn zwei Zahlen den gleichen Hashwert erhalten?"
 +
 +Wenn zwei unterschiedliche Zahlen den gleichen Hashwert bekommen, spricht man von einer **Kollision**. Kollisionen sind bei Hashfunktionen unvermeidlich, da die Menge der Eingabewerte um ein Vielfaches größer ist als die Menge der möglichen Ausgabewerte. 
 +
 +Im Beispiel würde die Zahl ''22'' ebenfalls am Index ''2'' abgelegt werden. Man benötigt also eine Strategie, wie man mit diesen Situationen umgeht. 
 +
 +Eine Möglichkeit ist, dass man an einer Stelle im Array nicht nur eine einzelne Zahl speichert, sondern mehrere (einen "Behälter", englisch "Bucket"):
 +
 +{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_097.png?400 |}}
 +
 +Wenn man bestimmen will, ob ein Wert ''x'' vorhanden ist, geht man so vor:
 +
 +  * Bestimme den Index von x (z.B. ''h(22) = 2'')
 +  * Untersuche alle Werte in diesem Behälter. Wenn einer davon gleich ''x'' ist, gib ''true'' zurück, sonst ''false''
 +
 +Ein Behälter kann z.B. mit einer ''ArrayList'' implementiert werden. Anstelle eines Arrays von int-Werten benötigt man jetzt also ein Array von ''ArrayList<Integer>''-Objekten.
 +
 +Der Speicheraufwand ist etwas höher und auch das Durchsuchen der Behälter dauert etwas länger.
 +
 +"Aber was haben wir damit jetzt gewonnen? Wir müssen immer noch die Behälter komplett durchsuchen!"
 +
 +Das stimmt, allerdings ist es sehr unwahrscheinlich, dass alle Werte im gleichen Behälter landen. Wahrscheinlicher ist eine grobe Gleichverteilung.
 +
 +{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_098.png?400 |}}
 +
 +Zudem kann man mit **Rehashing** die Elemente neu verteilen, wenn die Auslastung einen bestimmten Grenzwert (z.B. 75%) überschreitet.
 +
 +Die Auslastung bezeichnet das Verhältnis der gespeicherten Werte zur Länge des Arrays. \\ Im Beispiel: 8 Elemente, 10 Plätze → Auslastung = 80%
 +
 +{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_099.png?600 |}}
 +
 +Man legt ein neues Array der Länge z.B. 21 an und sortiert die bestehenden Werte neu ein. Viele der Kollisionen treten jetzt nicht mehr auf, es können aber neue Kollisionen entstehen, die Behälter enthalten jetzt im Durchschnitt weniger als einen Wert.
 +
 +Die Rehashing-Operation ist sehr zeitaufwendig, muss aber nur relativ selten ausgeführt werden.
 +Im Durchschnitt ist der lesende und schreibende Zugriff auf die Werte in konstanter Zeit möglich, also unabhängig von der Anzahl der Elemente im Set.
 +
 +Wenn man im Vorfeld bereits weiß, wie viele Elemente vermutlich gespeichert werden sollen, kann man bereits beim Erzeugen das Array entsprechend anlegen.
 +
 +==== Bewertung ====
 +
 +
 +=== Vorteile: ===
 +
 +  * Im Durchschnitt sehr schnell
 +  * Auf beliebige Datentypen anwendbar (in Java: Methode ''hashCode()'' der ''Object''-Klasse)
 +
 +=== Nachteile: ===
 +
 +  * Hoher Speicherbedarf
 +  * Kann in seltenen (konstruierten) Fällen langsam arbeiten
  • faecher/informatik/oberstufe/adt/set/implementationen/start.1636913876.txt.gz
  • Zuletzt geändert: 14.11.2021 18:17
  • von sbel