Diskussion:Perfekte Hash-Funktion

Ist das Ganze nicht offensichtlicher Blödsinn

Wenn es mehr Nachrichten als Hashwerte gibt, sind Kollisionen unvermeidlich. Die perfekte Hashfunktion ist das Zufallsorakel. 109.90.224.162 12:11, 7. Sep. 2016 (CEST)

Prinzipiell hast du Recht (Schubfachprinzip). Perfekte Hashfunktionen werden für ganz konkrete Schlüssel "aus einer endlichen und festen Schlüsselmenge" konstruiert. Die Beschreibung ist so, wie sie da steht, sehr kompakt. --77.47.102.29 13:07, 16. Jun. 2017 (CEST)

Unterschied perfekt und minimal perfekt

Auch nach Lektüre des Artikels versteh ich den Uterschied zw. Perfekt und Minimal Perfekt nicht. So, wie es sich liest, gibt es keinen, denn es gibt In jeder Maschine nur endlich viele Ganzzahlen. --Richardigel 16:03, 21. Mär 2006 (CET)

Zumindest in der aktuellen Versionen liest es sich korrekt.

Denn $T=\{0,...,|S|-1\}\subseteq \mathbb {N} \,$ bezeichnet genau die Zahlenreihe 0,1,2,...,|S|-1, also ordnet die minimal perfekte Hash-Funktion jedem Schlüssel einen unterschiedlichen Wert zu und es gibt keine 'Lücken' in der Zielmenge $T$ der Hash-Funktion, d.h. der Zielmenge ist minimal und ist gleich der Bildmenge. Ein Hash-Funktion ist 'nur' perfekt wenn nur Kollisionsfreiheit und $T=\{0,...,n\}\subseteq \mathbb {N}$ für ein $n>|S|-2$ zugesagt wird. --Gms 14:34, 15. Jun. 2008 (CEST)

Lesbarkeit des Artikels

Entschuldigung, aber könnte vielleicht mal jemand, der sich mit dem Thema auskennt, den Artikel etwas in verständliche Sprache umschreiben oder wenigstens eine verständliche Einleitung schreiben? Im Moment ist dieser Artikel für Nicht-Kryptographen wirklich unverständlich. --Mor‣gil 20:50, 26. Dez. 2008 (CET)

Gerne. Hierbei wäre allerdings noch interessant, für welche Zielgruppe der Artikel bzw. die Einleitung gedacht ist? Anregungen sind willkommen! --109.125.93.56 23:16, 17. Okt. 2015 (CEST)

Ja, das haette ich mir in meinem Informatikstudium auch oefter gewuenscht ;) 156.62.3.26 02:44, 13. Jan. 2011 (CET)

Im Artikel sind einige Dinge sehr eigenartig: Nicht perfektes Hashing habe armortisiert O(1) für den Zugriff. Das so allgemein zu behaupten empfinde ich zumindest als sehr gewagt. Außerdem heißt es, derzeitige perfekte Hashfunktionen benötigen 0,3 mal so viel Speicher, wie die Schlüsselmenge. Wie soll das denn überhaupt gehen, wenn das Hash alle Schlüssel aufnehmen muß? (nicht signierter Beitrag von 79.232.93.58 (Diskussion) 01:38, 27. Jul 2015 (CEST))

Ich verstehe auch nicht ganz, wieso die Komplexität amortisiert O(1) betragen soll. Vielleicht sind Hashtabellen mit einem Füllgrad kleiner 1 gemeint. Wenn ich so viele Eimer aufmache, dass ein Eimer erwartungsgemäß weniger als ein Element enthält, kann ich tatsächlich von einer durchschnittlich konstanten Zugriffszeit ausgehen. Für den Leser dieses Artikels wird das jedoch sehr verwirrend sein. Die Datenstruktur Hashtable hat gemäß verbreiteter Lehrmeinung die Zugriffszeit O(log n). Ich würde empfehlen, die u.U. richtige und gut gemeinte Anmerkung lieber zu entfernen.

Dass die Hashfunktion selbst weniger Speicher als die Schlüsselmenge benötigt, ist allerdings genau richtig so. Trick ist, einen Eintrag in der Hashfunktion für das Mapping mehrerer Schlüssel zu verwenden; bei einem Faktor von 0,3 mappt jeder Eintrag erwartungsgemäß drei Schlüssel in die Zielmenge {0, ..., n-1}. --109.125.93.56 23:16, 17. Okt. 2015 (CEST)

Bitte beachten, dass die Komplexität eben nicht amotisiert O(1) beträgt, sondern einfach O(1). Dafür kommt sie mit den erläuterten Einschränkungen für die klassische Hashtabelle als ein Lehrbeispiel für "dynamische" Datenstrukturen eben nicht in Frage.