Die Mathe-Redaktion - 20.09.2018 11:21 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 455 Gäste und 18 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Hashing: statt Kollisionen leere Felder berechnen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Hashing: statt Kollisionen leere Felder berechnen
NicoBeck
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.04.2018
Mitteilungen: 13
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-05-16


Hi,

ich habe folgende Aufgabe:

ich habe n Schlüssel, die mit einer Hash-Funktion h in ein Array T der Größe m umgerechnet werden.

Zu berechnen ist die erwartete Anzahl der leeren Einträge.

Meine Annahme dazu ist: Die Anzahl der Kollisionen = Anzahl der leeren Einträge, da mit jeder Kollision ja ein Feld frei wird. (Ist diese Annahme erstmal richtig)

Weil dann lässt sich relativ leicht auf die Wahrscheinlichkeit einer Kollision schließen, undzwar in dem Fall:

fed-Code einblenden

Soweit so gut. Doch wie kann ich aus dieser Wahrscheinlichkeit jetzt auf die Anzahl der Kollisionen schließen, damit ich sagen kann, dass diese gleich der Anzahl der leeren Felder ist?

Da fehlt mir gerade Ansatz, hat jemand einen Tipp?

LG,
Nico



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1264
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-05-17


Hallo Nico!

Eine Anmerkung:
nach einer Kollision kann man den Eintrag woanders im Array speichern oder in einem extra Array oder ähnlichem. Dies hat unmittelbar Auswirkungen auf die Anzahl der leeren Felder.

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
NicoBeck
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.04.2018
Mitteilungen: 13
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-05-17


Hallo Delastelle,

danke, dass du mich drauf aufmerksam machst, das muss mir entgangen sein:

in meinem Fall wird eine Kollision über die Linked List abgefangen.

Nach meinem Verständnis bedeutet das, sobald ich eine Kollision habe, wird diese an das bereits im Array stehende Element "angehängt". Damit wäre dann automatisch mit jeder Kollision ein neues freies Feld geschaffen oder?

LG,
Nico



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26472
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-05-17


Hi NicoBeck

Die Anzahl der freien Slots ist doch im Idealfall einer perfekten Hashfunktion m-n.
Da es diese perfekte Funktion aber nicht gibt hängt die Anzahl der zusätzlichen freien Einträge von der Güte das Hashs ab (dämlich wäre z.B. <math>h(key)=1</math> biggrin ).

Wie soll man etwas berechnen, wenn man nichts über die Hashfunktion weiß?

Gruß vom ¼


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5464
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-05-18

\(\begingroup\)
Die Aufgabe könnte so gemeint sein:

Jeder der n Schlüssel wird zufällig (unabhängig, gleichverteilt) auf eines von m möglichen Bilder abgebildet. Wie viele der m möglichen Bilder werden im Durchschnitt von keinem der n Urbilder getroffen?

Der Ansatz wäre hier, die Wahrscheinlichkeit zu berechnen, mit der ein bestimmtes Bild nicht getroffen wird. Diese ist $\left(\frac{m-1}{m}\right)^n$.  (Das ist übrigens $\approx e^{n/m}$.)
Mit der Wahrscheinlichkeit lässt sich der Erwartungswert der Zufallsgröße Xi berechnen, wobei Xi=1 ist, wenn Bild i nicht getroffen wird und 0 sonst.
Über die Linearität lässt sich dann auch der Erwartungswert von X1+...+Xm berechnen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]