Diskussion:Hashtabelle

linear hashing

dieser begriff und algorithmus fehlem im deutschen wiki komplett, sind aber eine entscheidend neuerung (nicht signierter Beitrag von 87.155.74.7 (Diskussion | Beiträge) 20:44, 14. Apr. 2009 (CEST))

Nachteile

Habe die ersten zwei Punkte entfernt. Meiner Ansicht nach sind sie so wie sie da standen unsinnig. Ich würde vorschlagen die Trennung zwischen Vor- und Nachteilen aufzuheben. Letztendlich beschreibt man Eigenschaften einer Datenstruktur. Was nachteilig für eine Anwendung ist, ist für eine andere einfach nur unwichtig oder sogar Vorteilhaft. Auch der letzte Punkt bei Nachteilen erscheint mir recht Zweifelhaft. Die Darstellung von Extremfällen (z.B. Überfüllung der Datenstruktur) ist recht schwer Pauschal zu beschreiben, weil das Verhalten stark von der Implementierung abhängt. Mocy 02:11, 5. Mär. 2008 (CET)

Reviewdiskussion

Hallo zusammen. Ich bin zwar schon relativ lange dabei, aber bisher habe ich nur kleine Verbesserungen an verschiedenen Artikeln vorgenommen und ein paar Bilder hochgeladen. Dies hier ist mein erster Artikel an dem ich maßgeblich beteiligt bin. Ich wollte euch hiermit fragen, was ihr zu meiner umfassenden Überarbeitung des Artikels meint. Kommentare in Form von konstruktiver Kritik und Verbesserungen sind sehr willkommen. Gruß -- Meph666 ^{→ post} 15:41, 28. Mai 2005 (CEST)

PS: Ich wollte noch ein oder anderes Schaubild zu diesem Artikel erstellen, bin bisher aber noch nicht dazu gekommen, ich wäre auch nicht "böse" wenn mir jemand zuvorkommen würde ;) -- Meph666 ^{→ post}

Hallo Meph666, der Artikel sieht recht gut aus. Ein paar Punkte:

• in Hash-Funktion stehen viele Informationen drin, die eigentlich nach Hashtabelle gehören. Evtl. könnte man die Artikel auch zu einem gemeinsamen Artikel Hashing vereinigen, isoliert sind die Informationen eh uninteressant.
• der Begriff "Streuwerttabelle" ist mir neu, wird der auch verwendet oder hat den nur irgendein "Sprachbewahrer" erfunden?
• das Javabuch von Ullenboom ist etwas fehl am Platz.
• Gliederung: "weitere Nachteile" ohne einen Punkt "Nachteile"? "Vorteile" erg. "gegenüber einfachen Arrays"
• Beispiele: wie sieht eine Hashfunktion üblicherweise aus und warum macht man sie nicht so, dass keine Kollisionen auftreten? ;-)

--Kurt seebauer 23:12, 30. Mai 2005 (CEST)

Hallo Kurt, danke erst einmal für den Lob :) und noch mehr Dank für die Kritik.

• Erst einmal zu dem Begriff "Streuwerttabelle", diesen habe ich aus der Vorversion des Artikels übernommen, kannte ihn allerdings bis dato auch nicht. Er hat für mich aber irgendwie plausibel und sinnvoll angehört, daher liess ich ihn da stehen. Werde mich mal informieren wie üblich dieser Ausdruck ist.
• Bezüglich eines gemeinsamen Artikels Hashing bin ich nicht ganz deiner Meinung besonders in Hinsicht der Verwendung der Hashfunktionen in der Kryptographie. Besonders wenn man den Artikel im Kontext von verschiedenen Datentypen betrachtet, verdient er seine Eigenständigkeit. Aber du hast Recht, dass man etwas mehr Informationen über Hashfunktionen in diesem Artikel benötigt. Werde mich darum auch kümmern.
• Aus dem Javabuch habe ich eine Definition für die Hashtabelle entnommen und diese mit der von Cormen kombiniert.
• "Weitere" aus "Weitere Nachteile" bezieht sich auf Kollisionen dass man als einen der gravierendsten Nachteile betrachten kann. Die Überschrift könnte auf den ersten Blick zwar falsch wirken, weckt aber evtl. die Neugier!?
• Vorteile gegenüber einfachen Arrays müssten noch erwähnt werden.
• Die Kollisionsfreiheit sollte in dem Kapitel über die Hashfunktionen erwähnt werden.

Werde mich demnächst mal dransetzen und die "Probleme" beseitigen. Gruß -- Meph666 ^{→ post} 08:29, 31. Mai 2005 (CEST)

Definition

Im Augenblick wird eine Hashtabelle als Implementierung eines "assoziativen Array" definiert. Ich halte diese Defintion fuer einseitig. Meiner Ansicht ist eine Hashtabelle eine Datenstruktur, die mehere Anwendungen und zu jeder Anwendung nochmal mehrere Implementierungen haben kann. Allein beim Einsatz als Indexstruktur im Hauptspeicher gibt es zahlreiche Implementierungen. Bei Datenbanken wird es dann noch komplizierter, weil die Daten nicht mehr im Hauptspeicher gehalten werden koennen.

Ausserdem Frage ich mich, warum Indexstruktur nur im Datenbank bereich ueblich sein soll. Einen Index benutzt man bewusst oder unbewusst bei der Implementierung jeder Software?

-- Sparti 08:56, 21. Jun 2005 (CEST)

Sparti:
"Im Augenblick wird eine Hashtabelle als Implementierung eines 'assoziativen Array' definiert."

Hallo Sparti. Die Hastabelle wird an erster Stelle als Datenstruktur definiert. Die Umsetzung des assoziativen Array ist nur ein weiteres Detail.

Sparti:
"Im Augenblick wird eine Hashtabelle als Implementierung eines 'assoziativen Array' definiert. Ich halte diese Defintion fuer einseitig. Meiner Ansicht ist eine Hashtabelle eine Datenstruktur, die mehere Anwendungen und zu jeder Anwendung nochmal mehrere Implementierungen haben kann."

Dass die Hashtabelle als Implementierung von "assoziativen Arrays" definiert ist steht doch nicht im Widerspruch zu dem was du danach schreibst. Wenn man allerdings der Definition aus Wikipedia folgt, dann finde ich es aber auch etwas verwirrend. Aus meiner Sicht ist die Erklärung der Implementierung hier etwas zu eingeschränkt. Sie kann wie ich denke auf mehreren Ebenen stattfinden, und man sollte sie nicht ausschließlich auf die Überführung von einem Algorithums oder eines Entwurfes in Programmcode mithilfe einer Programmiersprache einschränken. Im Allgemeinen würde ich sogar soweit gehen, jede gröbere Reduzierung des Abstraktionsnieveaus als Implementierung zu bezeichnen. In diesem Falle stellt die Hashtabelle tatsächlich eine Spezialform, oder einen weniger abstrakten Konstrukt des "assoziativen Arrays" dar, diesen Umstand als "implementieren" zu bezeichnen halte ich durchaus für legitim, besonders wenn man sich an dem englischen Begriff "to implement" orientiert (-> realisieren, verwirklichen, umsetzen). Aber da ich als Informatiker bestimmt eine Begriffswelt habe, die nicht unbelastet ist, wäre ich auch mit dem deutschen Wort "umsetzen" statt "implementieren" einverstanden.

So wie ich es bisher deinem Kommentar entnehmen konnte, würdest du den Zusammenhang zwischen assoziativen Arrays und Hashtabellen aus diesem Artikel ganz streichen. Ich bin damit nicht einverstanden. In meinen Augen stellt er einen wesentlichen Aspekt des Begriffs Hastabelle dar. Viele Grüße Meph666 ^{→ post} 08:39, 22. Jun 2005 (CEST)

Nein, ich moechte den Teil nicht streichen. Ich habe nur kritisiert, dass eine Hashtabelle mehr als nur ein assoziativer Array ist. Eine Hashtabelle ist eigentlich eine Indexstruktur, mit dem sich ein assoziativer Array effizient implementieren lässt. Sprich eine Hashtabelle ist kein(!) Assoziativer Array, aber diese kann mit einer Hashtabelle implementiert werden.

Ich glaube der wesentlich Unterschied bei uns ist die Vorstellung darüber, was das allgemeinere Konstrukt ist: der Assozitive Array oder die Hashtabelle. Ich denke es ist die Hashtabelle. Und der Assoziative Array ist der Spezialfall.

Interessanterweise gibts auf der englishen Seite eine Ähnliche Diskussion :-)

Gruss Sparti 10:05, 22. Jun 2005 (CEST)

Warum steht der Begriff Hashverfahren unter Hashtabelle?

Hashtabellen sind komplexe Datenstrukturen nicht nur lineare Arrays oder verkettete Listen. Bei dynamischen Verfahren kann die Datenstruktur ziemich kompliziert werden. Die Hashtabelle wie auch die Hashfunktion wird durch das Hashverfahren beschrieben. Von daher ist der Oberbegriff "Hashverfahren" oder kurz Hashen und nicht Hashtabellen. Das findet man in keinem Lehrbuch so.

Zudem werden auf der Seite keine Datenstrukturen für Hashtabellen besprochen!!

Einfach hinschreiben.

Rechtschreibung

Divisionsrestmethode, Hashfunktion, Hashtabelle, Hashverfahren schreibt man im Deuschen nicht mit Bindestrich sondern zusammen! Mittelquadmethode schreibt ihr ja auch zusammen. Schwierig wird es bei Hash-Algorithmus, weil Hash eine englisches Wort ist. Aber wenn man Hashverfahren zusammen schreibt, sollt man Hashalgorithmus auch zusammen schrieben. Wenn man das sieht dreht sich wohl einem der Magen um.

Hashwert, ....

So strikt ist das nicht geregelt. Da "Hash" englisch ist, jedes andere Wort, mit dem du es zusammensetzt, aber deutsch, ist es durchaus statthaft, durch einen Bindestrich den "Sprachwechsel" zu kennzeichnen. Was aber wichtig ist, wenn man sich für eine Schreibung enschieden hat, dass man die dann auch konsequent verwendet. --Sixot 13:53, 31. Jan. 2007 (CET)

Verständnisprobleme im Lemmabereich

Also ich verstehe bei den ersten Zeilen nur Bahnhof. Vielleicht sollte wenigstens mal auf Hashfunktion verlinkt werden, um das Verständnis etwas zu verbessern. Bei den ganzen Begriffen, die als Lemmata markiert wurden, habe ich außerdem das Gefühl, dass man die Thematik lieber in mehrere Artikel aufspalten sollte... --Trainspotter 17:03, 10. Apr 2006 (CEST)

Habe den Quatsch aufgeraeumt. Die verbliebenen Begriffe sind synonyme, bzw Hashverfahren ist die Art und Weise eine Hashtablle zu verwalten und somit nicht vom Lemma zu trennen. Gruss -- sparti 19:56, 10. Apr 2006 (CEST)

kleine Ungenauigkeit

Unter Kollisionen steht Da Hash-Funktionen im Allgemeinen nicht eindeutig (injektiv) sind. Müsste es nicht genauer heißen ... nicht eineindeutig (injektiv) ...? Denn eindeutig sind sie ja sehr wohl (sonst wären es keine Funktionen)? Schlage vor, das entweder zu ersetzen oder das Wort eindeutig ganz zu entfernen und nur zu schreiben ... nicht injektiv sind .... Mag kleinkariert klingen, wäre dann aber korrekt. --Matzedi 10:57, 14. Apr 2006 (CEST)

injektiv = eineindeutig --Quelokee ? talk ! 04:16, 16. Apr 2006 (CEST)

Also, wenn ich mir das hier durchlese: Injektivität, dann heisst eineindeutig auch surjektiv. Das ist aber hier nicht gemeint. Insbesondere scheint das eineindeutig auch nicht einheitlich verwendet zu werden (siehe Diskussion). Ausser, dass der Text jetzt unverstaendlicher geworden ist, hat das also nicht wirklich zur Klaerung beigetragen. Gruss -- sparti 23:49, 25. Jun 2006 (CEST)

große Ungenauigkeit offen/geschlossen

Im Deutschen heißt eine HT, in der an jedem Tabellenplatz eine Liste oder ein anderer (unbegrenzter) Container steht, "offene Hashtabelle".

Eine HT, in der an jedem Tabellenplatz Nutzdaten liegen, heißt "geschlossene Hashtabelle". Hier treten die Kollisionen auf, die durch lineares Sondieren oder ähnliche Verfahren (im Englischen "open addressing") aufgelöst werden müssen.

Im Artikel dagegen sind die beiden Begriffe "offene..." und "geschlossene..." vertauscht.

Siehe auch einschlägige Doku wie http://www.et-inf.fho-emden.de/~swtlab/ad/ad09.pdf

mfgkw

Habe es mal versucht zu präzisieren. In der Einleitung darüber, wird im letzten Satz ja schon darauf higewiesen. --Revvar (D RT) 17:02, 22. Jun 2006 (CEST)

Es ist nach wie vor falsch, z.B.:

"Eine Möglichkeit wird offenes Hashing genannt. Wenn dabei ein Eintrag an eine schon belegte Stelle in der Tabelle gelegt werden soll, wird stattdessen eine andere freie Stelle genommen"

Genau das ist "geschlossenes Hashing" und nicht offenes.

Das "offen" und "geschlossen" bezieht sich im Deutschen auf die gesamte Tabelle (offen: es können über das Linking theoretisch beeliebig viele Werte stehen, geschlossen: die Werte stehen nicht in Listen, sondern in der Tabelle und deshalb die Tabelle geschlossen und kann nie mehr Elemente aufnehmen als die Tabelle Plätze hat).

Das "open addressing" bezieht sich dagegen nicht auf die Tabelle, sondern auf die Adresse eines Elements, das ggf. offen ist in der Hinsicht, daß vom Hashwert abgewichen wird, um Kollisionen aus dem Weg zu gehen.

Also ist die geschlossene Hashtabelle die mit offener Adressierung (alle Elemente in der Tabelle, und Ausweichen durch lineares Sondieren etc.), und die offene HT ist die mit Linking, also Speichern der Elemente nicht in der Tabelle, sondern beispielsweise in Listen.

Entsprechend ist dein "Kollisionsauflösung durch Verkettung" gerade offenes Hashing; im Artikel steht es als Gegensatz zu offenenm H.

Es gehört also zusammen: offene HT, Linking/Verkettung einerseits und geschlossene HT, offene Adressierung, lin./quadr. Sondieren/doppeltes Hashing andererseits.

Ggf. kann ich den Text auch auf Vordermann bringen, aber ich will dir nicht ungebeten in die Quere kommen, zuviele Köche verderben den Brei.

-- Mfgkw 14:01, 23. Jun 2006 (CEST)

Es gibt nun mal leider zwei Bezeichnungsvarianten, was auch im Artikel steht und welche auch im deutschsprachigen Raum so unterschiedlich vorkommen. Man könnte dies vieleicht noch weiter hervorheben, und versuchen die Verwendung der Begriffe "offenes Hashing" und "geschlossenes Hasching" zu vermeiden und durch etwas Eindeutiges zu ersetzen (z.B. "Hashing mit offener Adressierung"). --Revvar (D RT) 19:25, 27. Jul 2006 (CEST)

nichtsdestotrotz, höre ich auch hier fast nur Stimmen, die es nun Mal anderherum kennen(wie auch ich in meiner diessemestrigen Vorlesung) - ein Appell an die Informatiker: Bitte einen passenden Präfix, Suffix finden, den man vorstellen kann, der diese Sache präzisiert, da ich den Artikel recht aufmerksam bis zu dem kritisierbaren Bereich gelesen habe, werden mindestens 50%(angedeutet durch diese Diskussion wohl mehr) zu dem Punkt es einfach andersrum lesen, als sie gelernt haben. Etwaige Klarstellungen sollten in meinen Augen einleitend erfolgen (nicht signierter Beitrag von 92.227.196.33 (Diskussion | Beiträge) 14:07, 10. Aug. 2009 (CEST))

Geschwindigkeitsvorteil

> Der Geschwindigkeitsvorteil bleibt eigentlich immer gleich unabhängig vom Füllgrad.

Bleibt er jetzt gleich oder nicht? Kann also das "eigentlich immer" gelöscht werden?

Ich habe die IP-Zusätze wieder entfernt. Sie sind viel zu unpräzise und stimmen nicht bei allen Varianten. Auch Ratschläge, zumal ohne Kontext, geben wir nicht. --Revvar (D RT) 19:40, 27. Jul 2006 (CEST)

Einleitung

"Dieser Index stellt im Idealfall die genaue Position des gesuchten Elementes in der Tabelle dar. Dieser Idealfall ist nicht immer gegeben, darum kann es auch zu Kollisionen kommen." Diese Formulierung ist nicht ganz klar, oder? JaK 13:18, 20. Mär. 2007 (CET)

Ich habe es etwas erweitert. Ist es so besser? -- sparti 13:34, 20. Mär. 2007 (CET)

Hashverfahren

"Eine Hash-Funktion berechnet aus einem Suchschlüssel einen Index in der Hashtabelle, der im Idealfall auf die genaue Position des gesuchten Elementes in der Tabelle zeigt. Es besteht aber auch die Möglichkeit, dass zwei Elemente den gleichen Hashwert besitzen, also auf die gleiche Position in der Tabelle zeigen. Diesen Fall nennt man Kollision, er muss separat behandelt werden."

das ist unverständlich und wahrscheinlich nicht ganz richtig. 1.) es können (in datenbanken zb. sehr oft) für einen schlüssel mehrere werte existieren, "idealfall" ist subjektiv. 2) was sind "elemente"? 3) kollision ist, wenn zwei schlüssel auf den selben wert zeigen. das hat aber mit 1) nichts zu tun. bitte mal prüfen. ekuah 15:25, 31. Mai 2007 (CEST)

Also der Idealfall ist, dass es zu einer Anfrage genau eine Antwort gibt. Das ist nicht subjektiv, sondern der einfachste Fall, den man beim Hashverfahren abdecken muss.

Weitherhin sind Datenbankschluessel immer eindeutig. Trotzdem muss der Hashkey nicht eindeutig sein. Aber hier wurde ja noch nichtmal behauptet, dass wir über Datenbankschlüssel reden, sondern über Suchschlüssel (habe den link mal korrigiert). Es gibt also zwei Gruende, die den Idealfall verhindern.

Zu 2) Elemente sind Elemente. Wer damit nichts anfangen kann, braucht kein Hashverfahren und interessiert sich auch nicht dafuer. Hast Du einen besseren Vorschlag?

Ich weiss auch nicht, warum 3) etwas mit 1) zu tun hat. Was meinst Du damit? -- sparti 16:03, 31. Mai 2007 (CEST)

tut mir leid, aber das muss noch geklärt werden. ich habe schon mehrere programmiersprachen gelernt, bin also nicht ganz unbeleckt, so dass ich mich zumindest für kompetent genug halte, diese erläuterung für unverständlich zu halten. ich zweifle nicht mal so sehr, dass das richtige gemeint ist, es wird aber nicht in vernünftigem deutsch gesagt. "elemente sind elemente" ist allerdings eine diskussionsform, die niemanden weiterhilft, besonders nicht denen, die hier was lernen wollen. wenn du auch so denkst, ist so ein kauderwelsch kein wunder.

man sollte hier erstmal die begriffe klären: was ist ein element und was ein hashwert, was ist hier ein schlüssel und besonders, was davon ist hier dasselbe? ist hier "position in der tabelle" und "index" dasselebe? kann es alternativ zum idealfall auch den fall geben, dass ein schlüssel oder hashwert nirgendwo hin zeigt?

wenn ich annehme, dass dieser satz in korrektem deutsch verfasst ist, ist er falsch : Es besteht aber auch die Möglichkeit, dass zwei Elemente den gleichen Hashwert besitzen, also auf die gleiche Position in der Tabelle zeigen., da nämlich elemente nirgendwo hinzeigen, sondern der schlüssel, es sei denn mit elementen sind hier die schlüssel gemeint, dann ist aber der erste satz falsch Eine Hash-Funktion berechnet aus einem Suchschlüssel einen Index in der Hashtabelle, der im Idealfall auf die genaue Position des gesuchten Elementes in der Tabelle zeigt.

..usw. also, erstmal sortieren ... .;-) ekuah 19:42, 31. Mai 2007 (CEST)

Also, der Satz oben ist nicht falsch, wenn auch etwas ungenau. Was ein Index und eine Hashfunktion ist, kann man nachlesen, in dem man auf die Links klickt. Ich denke das ist zumutbar :)

Trotzdem habe ich den Text jetzt nochmal überarbeitet und den Aufbau etwas sinnvoller gestaltet. Ich hoffe, dass er jetzt insgesamt etwas leichter zu lesen ist.

Dann noch zu Deiner Frage: Nein, ein Hashwert kann nicht ins leere zeigen. Die Hashfunktion liefert Zahlen in der Größenordnung, die genau Anzahl Buckets entspricht. Also jedes Ergebnis hat genau einen Bucket. Darin liegt auch eines der Probleme, wenn die Tabelle vergrößert wird. Dann muß nämlich die Hashfunktion verändert werden, so dass die alten Hashwerte nicht mehr gültig sind. Je nach Verfahren muß dann die Tablle vollständig neu erzeugt werden. Ich werde dazu auchnochmal was schreiben, aber jetzt nicht. -- sparti 09:48, 1. Jun. 2007 (CEST)

Ach noch ein Nachtrag: Meine Behauptung, dass ein Suchschlüssel ausreichend ist, um in einer Hashtabelle zu suchen ist so nicht ganz richtig. Wenn man Wert darauf legt, dass man genau ein Objekt gefunden wird, dann benötigt man einen Eindeutigen Schlüssel. Dazu werde ich auch noch was schreiben müssen. -- sparti 09:51, 1. Jun. 2007 (CEST)

hi sparti, danke für deine geduld. ich erwarte nicht, dass du alles alleine machst. im gegenteil, ich würde gerne die fragen klären und dann mitarbeiten, ich kann recht gut erklären. gelegentlich hab ich mit informatikern zu tun, die dies allesamt nicht können. sie labern immer nur in wertlosen tautologien rum und fühlen sich noch gebauchmietzelt, wenn man nichts versteht, es sind halt keine wikipedianer mit einem herz für ihre leser. u.u. mach ich auch eine grafik, wenn es hilft.

auch deine letzten änderungen entbehren leider jeglicher anschaulichkeit, es ist schlimmer geworden. ich habs noch nicht verstanden, und so dürfte es dann wohl vielen gehen, die sich hier kundig machen wollen.

beim klassische perl-hash wird ein "datensatz" über einen schlüssel ermittelt, was hat das mit berrechnen zu tun? "Zum Berechnen dieses Hashwertes wird ein Schlüssel benötigt, der dieses Objekt eindeutig identifiziert." -- ist nicht ein hashwert der schlüssel? wenn nicht, was dann? "Das Datenobjekt wird an dieser Stelle (die Bucket genannt wird) in der Tabelle gespeichert." an welcher stelle? der bucket-link ist auch sch. und außerdem ist es kontraproduktiv, den text mit fachchinesisch zu überfrachten, was soll das bringen? "Buckets können nun selbst wiederum so organisiert sein" -- wie "so"? usw.usw. ekuah 13:36, 1. Jun. 2007 (CEST)

Hallo Ekuah,

also das Hashverfahren ist der Algorithmus, der dem Perl Hashes zu Grunde liegt. Das heisst, der beschriebene Vorgang ist in Perl implementiert, ohne dass es der Perlprogrammierer mitbekommt, denn der will ja das Rad nicht immerwieder aufs neue erfinden. Dennoch geht es hier um das Verfahren selbst und das ist eben doch ein wenig komplizierter.

Ich finde auch nicht, dass man auf Fachchinesisch verzichten sollte, denn schließlich gibt es die Begriffe und sie müssen verstanden werden. Auch finde ich, dass ein gewisses Grundwissen vorausgesetzt werden darf. In Auto wird ja auch nicht erklärt, was ein Rad ist. Ich glaube allerdings, dass ein Beispiel und eine Skizze der Anschaulichkeit schon sehr helfen wird. Das alles verstaendlich zu machen.

Jetzt nochmal zu Deinen Fragen. Der Hashwert ist nicht der Schluessel. Aber aus dem Schluessel wird der Hashwert berechnet. Dieser ist ein Index, also ein Zeiger auf die Stelle in der Tabelle, wo das Zielobjekt gespeichert ist. Man kann auch sagen, dass es die Zeile in der Tabelle ist. Dabei kann der Schluessel alles moegliche sein. Eine Zeichenkette oder eine Menge von Zahlen. Wichtig ist nur, dass er fuer das Objekt eindeutig ist und dass es eine Hashfunktion gibt, die daraus einen Hashwert berechnen kann. Oftmals ist der Schlüssel ein Teil des Datenobjektes selbst, muss er aber nicht.

Der Begriff Bucket ist halt in diesem Zusammenhang gebraeuchlich und bedeutet im englischen nichts anderes als Eimer. Daher der Link. -- sparti 18:52, 1. Jun. 2007 (CEST)

...man erklärt aber nicht ein fremdwort durch ein anderes.

...also ist "hashwert" ein anderes wort für "index" bzw für "eindeutiger datensatzidentifizierer"? richtig? was versteht man aber unter "berechnet"? wäre nicht "ermittelt" passender? ich gehe davon aus, dass die ermittlung nichts weiter als ein vergeichsverfahren ist, bis "hab dich" eintritt. oder gibts ein beispiel, wo wirklich "gerechnet" wird?

ich weiß, ich nerve, aber leider komme ich nicht umhin, das wort "fachchinesisch" zu erklären. es bedeuted, dass man einfache sachverhalte durch zirkelinterne terminologie verdunkelt, die in normaler sprache ganz leicht zu verstehen wären. hier muss doch ziel sein, die sache verständlich zu machen, oder? ich hab -wie gesagt- schon einiges auf der programmierstrecke gelernt, aber das wort "bucket" ist mir noch nie begegnet. wenn ich ein auto erkläre, fang ich ja acuh nicht an, vom "steering wheel" zu reden, oder?

was auch völlig im dunkeln bleibt ist die bedeutung des wortes "streuwerttabelle". das wort muss einen sinn haben, was wird gestreut? ekuah 23:33, 1. Jun. 2007 (CEST)

Also, wir reden hier ueber ein Verfahren der Informatik. Damit darf man schon etwas Wissen der Informatik voraussetzen. Oder hast Du schon mal probiert deiner Oma zu erklaren, was ein Perl-Hash ist? Und wenn Du Wert darauf legst, darfst Du Bucket gerne mit Eimer übersetzen. Ich jedenfalls bevorzuge das englische Fachwort.

Auch, in Punkto Fachjargon muss dir klar widersprechen. Das sprengt zwar das Thema hier, aber trotzdem ganz kurz: Ein Terminus Technicus ist ein klar definierter Begriff. Man koennte das gleiche umgangssprachlich erlaeutern, die Folge wäre aber, dass eine Tabelle zahllose Bedeutungen haben kann. Ein Hashtabelle hat aber genau eine Bedeutung. Ebenso weiss jeder Informatiker sofort, was ein Bucket ist. Was eine Stelle in einer Tabelle ist, ist hingegen schwammig und mehrdeutig. Ich muss dich entaeuschen, der Fachjargon dient nicht als Nebelkerze für Uneingeweihte, sondern umgekehrt der Klarheit. Er setzt aber voraus, dass man die Begriffe zunächst versucht hat zu verstehen.

Somit kann man in Hashfunktion nachlesen, dass ein Hashwert das Ergebnis der Berechnung einer mathematischen Funktion ist. Doch offensichtlich ist ein Hashwert kein Index. Aber warum kann er wohl als Index verwendet werden? Und ja, was wird wohl gestreut? Ich denke die Lösung dieser Aufgabe, darf man Leser gerne selbst überlassen, denn wenn er das Verfahren verstanden hat, ergibt sich der Name von selbst.

Am Ende bleibt es dabei, wir brauchen Beispiel und Skizzen. Dann können wir uns alle diese Worte hier sparen. -- sparti 00:39, 2. Jun. 2007 (CEST)

...hab schon vermutet ,dass deine denke so ist. du hast leider nicht verstanden, was ich sagen wollte. das ist hier eine enzyklopädie, wo leute reinschauen, die etwas lernen wollen. es ist didaktisch nicht nur schwierig, sondern ganz und gar unmöglich, einen fremden begriff durch einen anderen fremden begriff zu erklären. das wort "erklären", bedeutet, das mir etwas klar wird und noch lange nicht, dass ich etwas erzähle, was nicht falsch ist oder von fachleuten als richtig berurteilt wird. es ist eine transformation vom unverständnis zum verständnis. alles andere ist für einen, der was lernen will, wertlos. es scheint mir aber einmal mehr, dass dies informatiker-typen intelektuell unzugänglich ist. ich versichere dir, das deine gedanken, so logisch sie dir auch erscheinen, nichts mit der praxis der lernpsychologie zu tun haben. deine haltung ist vollkommen untauglich, wissen zu vermitteln, die musst du ändern. tipp: folgerichtigkeit ist nicht wahrheit, grüble nicht so viel, sondern probier aus, ob dich einer versteht. ich bin sicher, das ein hashverfahren tatsächlich so banal funktioniert, dass es meine oma verstehen kann. und zuguter letzt verkneife ich mir auch den verdacht nicht, dass gewisse leute, die undurchsichtig rumschwafeln, selber nicht wissen wovon sie reden. wünsche alles gute! ekuah 09:57, 2. Jun. 2007 (CEST)

Also Dann schlag ich vor, du besorgst Dir einfach mal ein gutes Handbuch zum Thema und liesst dich dort ein. Dann kannst Du ja mal selbst ueberlegen, wie man das hier besser beschreiben kann. Bis dahin arbeite ich an einem Beispiel und Skizzen und wenn Du dann nicht mehr schmollst, waere ich sehr dankbar, wenn Du nochmal einen Blick drauf wirfst. -- sparti 11:44, 2. Jun. 2007 (CEST)

ach, wo ich schmolle nicht. lass mich mal machen, das kannst du nich! ;-)

wir könnten vorankommen, wenn du mal endlich auf meine fragen eingehen würdest:

Beim Hashverfahren werden die Zieldaten in einer Hashtabelle gespeichert. -- was ist mit "zieldaten" und "hashtabelle" gemeint? entweder die daten die ich suche und die tabelle in der sie stehen oder sozusagen die adressen der daten die ich suche, in deiner tabelle organisiert, die jedem schlüssel eine adresse (auch eimerweise) zuordent? ekuah 18:11, 2. Jun. 2007 (CEST)

Die Tabelle ist eine Tabelle, typischerweise als Array implementiert. Die Zieldaten, sind die die man sucht. Die koennen im einfachsten Fall direkt im Hashtable stehen.

So aus dem Schluessel wird eine Nummer berechnet, diese Nummer ist eine Zeile in der Tabelle. Dort befinden sich dann die Adressen zu den Zieldaten - eimerweise. -- sparti 18:54, 2. Jun. 2007 (CEST)

das geht begrifflich durcheinander, wenn man es nicht sauber ausformuliert. die hash-tabelle ist etwas anderes als die tabelle mit den gesuchten daten. die hash-tabelle enthält im einfachen fall zwei spalten: spalte1 die schlüssel, spalte2 die hashwerte (=indizes). die hashwerte sind zeiger auf die gesuchten daten, genauer gesagt, auf ihre position im daten-pool, was meist eine tabelle ist. optimalerweise sind beide spalten der hashtabelle "unique-felder". die hashtabelle kann aber (logischerweise) zwei abweichungen haben:1) mehrere schlüssel stehen einem gleichen hashwert gegenüber, dh. mehrere schlüssel führen zum selben ergebnis 2) einem schlüssel stehen mehrere haswerte gegenüber, dh. ein schlüssel führt zu mehreren ergebnissen. nach dem Hashtabelle#Kollisionen hier ist 1) eine kollision. 2) bietet bringt den vorteil, dass bereits in der hashtabelle feststeht, wieviele ergebnisse vorliegen. ein bucket ist sozusagen eine zelle in der tabelle, die mehrere werte enthält, in diesem fall mehrere hashwerte. (man könnte die hashtabelle aber auch so organisieren, das spalte1 den selben schlüssel mehrmals enthalten kann, so dass in jeder zelle jeweils nur ein wert steht. dann darf das hashverfahren nicht bei der ersten übereinstimmung mit einem schlüssel die "berechnung" (besser "ermittlung") abbrechen). richtig? (meine oma würde das so sehen, aber nicht durch zuhilfenahme dieses artikels).

noch eine kritik: Zieldaten ,Datenobjekt,Objekt, Daten, Datensätze, Datenmengen, Zielobjekte -- diese wörter sind im prinzip synonyme für "etwas", also zeimlich nichtssagend. auch ein wohlwollender leser ist damit überfordert, sie in diesem artikel inhaltlich auseinander zu halten. er weiß ja auch nicht, dass das, was er lernen soll, gar nicht ausgesprochen wird. "im auto befindet sich ein bereich der zu handlungen vorgesehen ist die ergebnisse bringen. er ist durch auffallende gestaltung gestaltet und hebt sich dadurch von anderen bereichen deutlich ab" ;-) ekuah 20:14, 2. Jun. 2007 (CEST)

Sorry, aber so stimmts immer noch nicht. Es gibt nur eine Tabelle: Die Hashtabelle. Diese kann die Daten enhalten, aber eben auch Pointer auf die Daten. Haengt von der Implementierung ab. In der Hashtabelle sind beide Felder eindeutig, immer! Sie uebersetzen aber den Hashwert auf einen Zeiger/Zieldaten.

Zu deinem Punkt 2) das kann man so machen, im Allgemeinen muss es aber nicht stimmen. Du beschreibst einen Sonderfall, der auch eine spezielle Hashfunktion benoetigt, die die Bedeutung eines Buckets kennt.

Die Hashwerte der Daten in einem Bucket sind immer gleich!

Die erste Spalte enthaelt niemals Schluessel, sondern den Index des Arrays und ist damit eigentlich ueberfluessig.

Und nein, der Index darf auf gar keinen Fall mehrfach vorkommen. Genau das ist der Clou. Mit einem einzigen mathematischen Rechenschritt grenze ich sofort das Suchgebiet auf einen Bucket ein. Der Bucket selbst ist in der Regel eine Liste oder ein Suchbaum.

Beispiel:

Ich habe eine Adressliste mit 10.000 Adressen von Personen. Ich baue einen Hashtable mit 100 Zeilen. Der Suchschluessel ist der Name der Personen. Die Hashfunktion definieren ich wie folgt: h( Person ) = Summe aller ASCII Zeichen Modulo 100. Mal davon abgesehen, dass diese Hashfunktion nicht optimal ist (schlechte Streuung der Werte), wird also ein Name auf eine Zahl zwischen 0 und 99 abgebildet. Diese Zahl entspricht der Zeile in der diese Person gespeichter ist. Im Mittel werden aber pro Bucket 10.000/100 = 100 Personen gespeichter sein. Das heisst ich muss nur noch 100 Personen statt 10000 durchsuchen. -- sparti 20:52, 2. Jun. 2007 (CEST)

Bucket-Senf

Ich gebe jetzt doch mal meinen Senf dazu. Ich habe nichts gegen die Verwendung des Worts "Bucket", nur erklärt sollte es doch mal werden. Ja, auch Nachschauen bei einem anderen Artikel wäre zumutbar, wenn es denn einen guten gäbe und er auch verlinkt wäre. Ist er aber seit dem 2. Juni nicht mehr: [1] Also bitte wenigstens einen kurzen Satz zur Erläuterung :-) --Rubik-wuerfel 17:45, 16. Jul. 2007 (CEST)

Implementierungslink?

Guten Tag

Der Link auf die konkrete Implementation in C++ ist zwar eine feine Sache, aber vielleicht sollte man drüber nachdenken aus Höflichkeit erstmal auf die Website des Besitzers anstatt direkt auf das File zu linken.

Auf der Webseite gibt es keinen Link auf die Datei. Ich habe den Link daher entfernt. -- sparti 14:40, 3. Dez. 2007 (CET)

Hashmap

3 Dinge von mir (sorry, wenn ich das falsch mache, bin Wikineuling):

• ich fände es sinnvoll, wenn man gleich im Einleitungssatz erwähnt, dass der englische Begriff hier auch Hashmap wäre
• außerdem wird erst bei Kollisionen erwähnt, was genau ein Bucket ist und wozu es benutzt wird. Aber schon vorher wird auf Buckets im Text eingegangen, was verwirrend sein kann.
• vor allem im Datenbankbereich ist ein großer Nachteil von Hashmaps, dass keine Bereichsanfragen möglich sind. Bei Bereichsanfragen sind daher bspw. B-Bäume klar vorzuziehen, wogegen Hashmaps riesige Vorteile bei Anfragen einzelner Werte haben. (Der vorstehende, nicht signierte Beitrag stammt von 92.229.211.111 (Diskussion • Beiträge) 18:24, 26. Jul. 2008) (Diskussionsbeiträge bitte mit vier Tilden unterschreiben ~~~~)

Hallo, danke für deine Vorschläg zur Verbesserung des Artikels. Meine Meinung dazu:

• Erwähnung von Hashmap finde ich nicht so arg sinnvoll, wenn es jemanden interessiert, wie der Begriff im Englischen heisst, so kann er ja auch über den interwikilink auf der linken Seite zum englischen Artikel gelangen, wo er die üblichen englischen Begriffe nachschlagen kann. Sinnvoll fände ich allerdings eine Weiterleitung von Hashmap zu diesen Artikel, so dass bei der Eingabe von Hashmap in das Suchfeld hierher geleitet wird (werds gleich mal erledigen). Bei den anderen zwei Punkten, gebe ich dir recht.
• dort, wo die Buckets das erste mal auftauchen, werden sie eigentlich auch gleich implizit erklärt: als Stellen in der Tabelle, welche die Datenobjekte aufnehmen. Man könnte den Klammerzusatz "(Bucket genannt)" auch etwas abändern bspw. in "(Bucket genannt, englisch für ‘Eimer’, siehe auch Bucketsort)" oder gar aus dem Klammerzusatz einen weiteren ganzen Satz machen: "Diese Speicherorte werden Buckets genannt ..."
• im dritten Punkt, stimme ich dir natürlich zu, die Erwähnung der Nachteile bei den Datenbanken kann im Abschnitt Anwendung erfolgen. Ansonsten kann ich nur sagen: sei mutig :-) Viele Grüße -- Meph666 ^{→ post} 20:15, 26. Jul. 2008 (CEST)

Wenn Hashmap hierhin weiterleitet, dann muss das Wort „Hashmap“ auch im Text definiert werden. Anderenfalls erzeugst du nichts als Verwirrung bei unseren Lesern. --j ?! 20:41, 30. Jul. 2008 (CEST)

Grammatik

Hallo Jpp, wenn mich mein Sprachgefuehl nicht voellig taeuscht, dann ist

... durch den Hashwert festgelegte Stelle ...

die korrekte Schreibweise. Gruss -- sparti 17:21, 30. Nov. 2008 (CET)

Schau dir mal mehr Text an: „wird an einer durch den Hashwert festgelegten Stelle … in der Tabelle gespeichert“. Ich denke also, dass dein Sprachgefühl dich hier völlig täuscht. :-) --j ?! 21:46, 30. Nov. 2008 (CET)

Ja, da hast du wohl doch recht :) -- sparti 00:04, 1. Dez. 2008 (CET)

Suchbegriff - Weiterleitung

Hallo,

mein Professor verwendet statt den Begriff "Hashverfahren" den Begriff "Hashingverfahren". Bei der Suche habe ich den zweiten Begriff verwendet und hatte somit keine erfolgreiche Suche. Könnt ihr vielleicht eine Weiterleitung für den zweiten Begriff "Hashingverfahren" einrichten? Wenn das nicht geht, dann bitte zumindest einen Verweis auf den richtigen Artikel der in der Suchanfrage erscheinen soll.

Vielen Dank im Voraus.

Gruß Alex

--Alex Kuhn 20:09, 26. Nov. 2009 (CET)

Quadratische Sondierung

Aktuell wird die Sondierung so definiert: $h_{i}(x)=\left(h(x)+(-1)^{i+1}\cdot \left\lceil {\frac {i}{2}}\right\rceil ^{2}\right){\bmod {~}}m$ Einfacher könnte man dieses i+1 aber auch weglassen, ist imho etwas verwirrend, oder hab ich den Sinn dahinter übersehen? Zumindest liefert folgende Definition die gleichen Ergebnisse afaik: $h_{i}(x)=\left(h(x)+(-1)^{i}\cdot \left\lceil {\frac {i}{2}}\right\rceil ^{2}\right){\bmod {~}}m$ -- DustyDingo 14:50, 13. Jan. 2010 (CET)

der unterschied ist, dass es zurzeit ab i=1 mit nem positiven sprung anfängt... das dürfte performance-mäßig ohne belang aber didaktisch klüger sein... --Heimschützenzentrum (?) 09:41, 8. Mär. 2010 (CET)

Primär- vs. Sekundärkollision

Wann spricht man genau von einer Primär- und wann von einer Sekundärkollision? Wenn ich das richtig verstanden habe, ist es auf jeden Fall eine primäre, wenn ich zwei Werte mit dem gleichen Schlüssel an eine Position einfügen will. Also z.b. einen Wert an Position 4, wenn dort bereits ein Wert der auch dort hingehört sitzt. Sekundär ist es, wenn ich den Wert an Position 4 einfügen wöllte, dort aber einer sitzt, der eigentlich nach 3 gehört, aber aufgrund der Sondierung verschoben wurde? Wenn ich jetzt den neuen Wert (bei linearer Sondierung) auf 5 setzen will, dort aber einer sitzt, was ist das dann für eine Kollision? Sekundär (weil der neue dort nicht hingehört), primär (weil der, der dort sitzt da richtig ist)? Um das zu veranschaulichen:

Der Hashwert wird hier jetzt einfach mal aus der ersten Ziffer "berechnet", lineare Sondierung und in die Tabelle wird in Reihenfolge 0123 und dann 0454 eingefügt. Dadurch entsteht bei 0 (beide Werte beginnen mit 0) eine Primärkollision und 0454 landet bei 1.

P	Schlüssel	Kollision
0	0123	Primär
1	0454
2
3

Wenn ich jetzt 0666 einfügen will, habe ich eine Primärkollission bei 0. Durch die Sondierung komme ich auf Position 1 wo bereits 0454 sitzt. Ist das dort dann eine Sekundärkollision? Beide Werte gehören eigentlich nicht dort hin. Reihenfolge 0123 und dann 0454 eingefügt. Dadurch entsteht bei 0 eine Primärkollision und 0454 landet bei 1.

P	Schlüssel	Kollision
0	0123	Primär
1	0454	?
2	0666
3

Wenn ich statt 0666 1111 einfügen wöllte, wäre das dann eine Sekundärkollision bei 1, weil 0454 dort nicht hingehört? Reihenfolge 0123 und dann 0454 eingefügt. Dadurch entsteht bei 0 eine Primärkollision und 0454 landet bei 1.

P	Schlüssel	Kollision
0	0123
1	0454	?
2	1111
3

Und wie ist bei folgendem Szenario, wenn gerade 0777 eingefügt wurde:

P	Schlüssel	Kollision
0	0123	Primär
1	1234	?
2	0777
3

1234 gehört nach 1, 0777 eigentlich nach 0. Dort ist allerdings belegt (Primärkollision) und beim sondieren kam man auf P=1, an dessen Stelle 1234 an seinem "rechtmäßigen" Platz sitzt. Sekundärkollision bei 1 somit? Habe da teils widersprüchliches ergoogelt. Manchmal wurde es abhängig vom Versuch erklärt (wenn der erste Speicherversuch fehlschlägt hat man eine primäre, sonst sekundär), manchmal wurde es damit erklärt, wer den Platz "weggenommen" hat (sekundär auch beim ersten Versuch, wenn dort Schlüssel sitzt, der dort durch Sondieren hinkam). --StYxXx ⊗ 08:18, 6. Mär. 2010 (CET)

guter punkt... da die einteilung in sekundär und primär nicht ordentlich motiviert ist und auch noch widersprüchlich definiert ist, sieht es nach WP:TF verstoß aus... ich verstehe auch nicht ganz, wieso es zu clusterbildung kommen sollte (hört sich an, als wären bestimmte nebeneinander liegende buckets besonders beliebte ziele der hashfunktion, was ja eher auf eine schlechte hashfunktion hindeutet...)... --Heimschützenzentrum (?) 11:03, 7. Mär. 2010 (CET)

Ein Verstoß gegen WP:TF kann doch nur vorliegen, wenn das entsprechende im Artikel steht und ich finde dort nichts über Primäre oder Sekundäre Kollisionen :-). Das Beispiel von StYxXx zeigt aber schön die Clusterbildung; wenn z.B. dreimal was bei der 0 eingefügt wurde, dann sind 0,1 und 2 besetzt; es bilden sich zusammenhängende besetzte Bereiche (=Cluster). Jedes Einfügen bei 0, 1 oder 2 vergrößert den Cluster. Das hat nichts mit schlechter Hashfunktion zu tun, es muß ja gerade nicht mehr an der 0 eingefügt werden. Das ist genau das Problem beim Linearen Sondieren (und das steht im Artikel). MfG --LungFalang 11:39, 7. Mär. 2010 (CET)

dann such mal nach "primä"... wenn dreimal auf die 0 abgebildet wurde, halte ich das für merkwürdig... außerdem hilft da das quadratische trallala auch nix (im gegenteil: es dauert länger)... --Heimschützenzentrum (?) 12:41, 7. Mär. 2010 (CET)

Hab' mal die Brille geputzt und ... äh ... nix gesagt :-) --LungFalang 19:22, 7. Mär. 2010 (CET)

'kay 'kay (= ok ok)... :-) und was machen wir nun mit dem absatz? --Heimschützenzentrum (?) 20:20, 7. Mär. 2010 (CET)

<----- Wieder nach links

Der Artikel definiert Sekundärkollision als $h_{0}(x)=h_{k}(y)$, d.h. das erste Ziel für Wert x ist das gleiche Ziel, das beim k-ten Versuch für den Wert y gefunden wurde Hab ich noch was übersehen? Wieso widersprüchl. Definition?.

Da sich langsam aber sicher mein Hirn verknotet schreibe ich mir mal ein Beispiel auf Nein, das soll kein Beweis sein!

Annahme: $h_{0}(x)=1;h_{0}(x)=5$; H0(y) = 5

Fügen wir sechsmal x und zweimal y ein nur, damit ich Kollisionen bekomme, dann erhalten wir folgende Besetzung

Lineare Sondierung

Resultat: Das zu x gehörende Datum steht in den Feldern 1,2,3,4,5,6

Erstes Einfügen von y, Versuche 5, Versuche 6, Setze 7

Zweites Einfügen von y, Versuche 5, Versuche 6, Versuche 7, Setze 8

Drittes Einfügen von y, Versuche 5 ... Setze 9

Ergebnis:

Feld	Datum
1	x
2	x
3	x
4	x
5	x
6	x
7	y
8	y
9	y

Wir haben eine Kette (=Cluster)

Jetzt quadratische Sondierung (ohne Alternieren und ohne Berücksichtigung des modulo)

Kandidaten: für x: 1, 2 (=1+2), 5(=1+4), 10(=1+9), 17(1+16), 26(=1+25) für y: 5, 6, 9, 14, 21, 30

Das zu x gehörende Datum steht in den Feldern 1, 2, 5, 10, 17, 26

Erstes Einfügen von y, Versuche 5, Setze 6,

Zweites Einfügen von y, Versuche 5, Versuche 6, Setze 9

Drittes Einfügen von y, Versuche 5, versuche 6, versuche 9, setze 14

Ergebnis:

Feld	Datum
1	x
2	x
5	x
6	y
9	y
10	x
14	y
17	x
26	x

Wie gesagt: Soll kein Beweis sein - aber ein Cluster ist das nicht :-)

Für die Quadrat. Sondierung gilt:

• Mit der gegebenen Definition sind ab dem dritten (vierten bei Alternieren) Versuch bei identischem Resultat der Hashfunktion die Buckets nicht benachbart.
• Da die Schrittweite der Kandidaten sich für unterschiedliche Werte $x\neq y$ verändert, werden bei Kollisionen unterschiedliche (nicht benachbarte) Bucket-Adressen im n-ten Versuch ermittelt.

Fazit: Ich glaube die im Artikel stehende Aussage ist (so wie sie dasteht) korrekt. Aber ... äh ... Knoten ... Hirn ...usw....

Kann mal jemand den Meister befragen (Donald Knuth: The Art of Computer Programming)

Und wenn ich jetzt totalen Müll verzepft haben sollte, dann dehe man mir das nah

(nicht signierter Beitrag von LungFalang (Diskussion | Beiträge) 8. März 2010, 01:08 Uhr )

also soll der artikel behaupten, dass durch den quadrat-kram mängel in der hash-funktion beseitigt werden? was ist denn, wenn die hash funktion nicht den linear entstandenen cluster sondern gerade den quadratisch entstandenen cluster bevorzugt? im englischen artikel steht, dass das quadrat-verfahren nicht immun ist gegen clusterbildung: en:Quadratic probing... --Heimschützenzentrum (?) 07:54, 8. Mär. 2010 (CET)

durch Monte-Carlo-Simulation habe ich rausgefunden, dass (H+i) (1170‰) etwa 1,34 mal mehr kollisionen hat als (H + (i%2?-1:1) * sqr((i+1)/2)) und dass (H+i) etwa 1,4 mal mehr als (H + i + i*i) hat. jeweils mit einem füllgrad von 0% auf 70% ansteigend und optimaler hash-funktion... ich verstehe nur nich warum... die zahl der primärkollisionen (also die hash-funktion zeigt auf einen belegten bucket) ist bei allen drei sondierungs-methoden gleich (350‰)... --Heimschützenzentrum (?) 08:45, 8. Mär. 2010 (CET)

Also mich hat u.a. nur irritiert: Was für eine Kollision hat man, wenn man beim sondieren einen Schritt weiter geht und dort etwas sitzt? Also im Grunde: Was für Kollisionen traten bei meinen Fragezeichen in den Beispieltabellen auf? Kann ja jemand eintragen, der es weiß. Oder bei dem letzten beispiel mit x und y immer immer nach "Versuche .." hinschreiben. Widersprüchlich war das, was ich bei google fand, nicht der Artikel selbst. Der nur unklar bzw. zu wenig anschaulich diesbezüglich (was ist zB bei $h_{2}(x)=h_{2}(y)$, falls ich das korrekt formuliert habe?). Ich merke, das Thema ist interessant ;) --StYxXx ⊗ 09:51, 8. Mär. 2010 (CET)

primärkollisionen = die hash-funktion zeigt auf einen belegten bucket; sekundärkollisionen = alle anderen kollisionen... gäbe sinn, würd ich mal sagen... andere definitionen vllt auch... also habe ich die beiden begriffe mal aus dem artikel mangels relevanz und wegen unklarheit/umstrittenheit beseitigt... --Heimschützenzentrum (?) 10:00, 8. Mär. 2010 (CET)

(Nach BK, bezieht sich den Eintrag mit also soll der Artikel behaupten...') Es geht doch um die Aussage Quadratisches Sondieren ergibt keine Verbesserung bei Primärkollisionen $h_{0}(x)=h_{0}(y)$, kann aber die Wahrscheinlichkeit der Bildung von längeren Ketten bei Sekundärkollisionen $h_{0}(x)=h_{k}(y)$ herabsetzen, d. h. Clusterbildung wird vermieden.

Das ist unabhängig von der Hashfunktion. Im Falle der schlechtesten aller Hashfunktion (h(x) = const) stehen bei Linearem Sondieren alle Werte hintereinander, beim Quadrat. Sondieren sind sie über das ganze Feld verteilt. Und das gilt mMn auch für sinnvollere Hash-Funktionen. Mängel der Hash-Funktion werden durch die Wahl der Sondierung sicher nicht beseitigt.

Mit Monte-Carlo (und dem Zählen der Kollisionen) erhält man eher eine Aussage über die "Kosten des Verfahrens". --LungFalang 10:40, 8. Mär. 2010 (CET)

gerade im fall "h(x) = const" ist quadratisch so schlecht wie linear... durch Monte-Carlo sieht man die neigung zur cluster-bildung... --Heimschützenzentrum (?) 10:50, 8. Mär. 2010 (CET)

Klar sind beide Verfahren dann gleich schlecht iss ja auch ne Sch...-Hashfunktion aber 1,2,5,10,17,26 ist doch kein Cluster.--LungFalang 11:02, 8. Mär. 2010 (CET)

für die sondierungs-funktion aber schon... da kommt eine kollision nach der andern... oder ist das falsch gedacht? --Heimschützenzentrum (?) 12:15, 8. Mär. 2010 (CET)

Die Werte aus der Sondierungsfunktion liefern immer dieselbe Folge - sind aber (bei quad. Sond.) nicht benachbart. Man landet immer bei denselben Eimerchen (=Kollision), aber die gefüllten stehen hinterher nicht nebeneinander (=Cluster). --LungFalang 13:31, 8. Mär. 2010 (CET)

Der Artikel definiert die Sekundärkollision (hatte es definiert; ist jetzt besser) nur als die Erste Kollision ($h_{0}(x)=h_{k}(y)$). Und da hast Du völlig recht, das ist zu wenig. Aber das ist ja schon verbessert. --LungFalang 10:47, 8. Mär. 2010 (CET)

*wag tail* --Heimschützenzentrum (?) 10:50, 8. Mär. 2010 (CET)

Also, in einem Script steht

Sei f: S → {0, 1, ..., p-1} eine Hashfunktion.
Gilt f(s) = f(s') für zwei einzufügende Schlüssel s und s', so
spricht man von einer Primärkollision. In diesem Fall muss der
zweite Schlüssel s' an einer Stelle A(i) gespeichert werden, für
die i ≠ f(s') gilt.
Ist f(s') = i und befindet sich an der Stelle A(i) ein Schlüssel s"
mit f(s") ≠ i, so spricht man von einer Sekundärkollision, d.h.,
die erste Kollision beim Eintragen von s' wird durch einen
Schlüssel s" verursacht, der vom Hashwert her nicht an die
Position i gehört und selbst durch Kollision hierhin gelangt ist.

Und dann Beispiel

Drei Schlüssel werden in der Reihenfolge JANUAR, FEBRUAR,
OKTOBER eingegeben. Es gilt:
f(JANUAR) = 11, f(FEBRUAR) = 11, f(OKTOBER) = 12.
Wir tragen JANUAR in der Komponente A(11) ein.
Der Schlüssel FEBRUAR führt zu einer Primärkollision. Die
Strategie sei: Gehe von der Stelle j zur nächsten Stelle j+1.
Dann wird FEBRUAR an der Stelle A(12) gespeichert.
Der Schlüssel OKTOBER gehört in die Stelle A(12), doch hier
steht ein Schlüssel, der dort nicht hingehört, sondern durch eine
Kollision hierhin verschoben wurde. Folglich führt OKTOBER
zu einer Sekundärkollision. (OKTOBER wird dann an der Stelle
A(13) eingetragen.)

Somit wäre ein Primärkollision, wenn man zwei Hashwerte gleich sind. Und Sekundär alles andere? Unklar war ich mir noch, was es ist, wenn ich sondiere. Dort spricht das Script auch jedesmal von einer Kollision, wenn die zu testende Stelle belegt ist, sagte aber nicht, ob primär oder sekundär. Woanders fand ich jetzt

Auch beim Sondieren kann es natürlich zu weiteren Kollisionen (Sekundärkollisionen) kommen. 
Es ist daher vorteilhaft, beim Sondieren für verschiedene Schlüssel unterschiedliche Schrittweiten zu wählen.

Zwar sagten manche Googlequellen was anderes, als ich hier die erste Frage stellte, aber ich vermute dann jetzt nach allem mal, dass grundsätzlich alles eine sekundäre Kollision ist, wenn sie nicht durch gleiche Hashwerte verursacht wird. Ist also nach dem Sondieren ein Bucket belegt worden und die Hashfunktion des nächsten einzufügenden Schlüssels zeigt dort hin, wäre es eine sekundäre, da die beiden kollidierenden eigentlich nicht die selben Hashwerte haben. Genauso wäre es eine sekundäre, wenn ich erst eine primäre habe und dann während des Sondierens auf einen weiteren belegten Bucket stoße - diesmal egal, ob das dort stehende auch da rein gehört. Der Schlüssel für den gerade sondiert wird gehört da ja nicht hin. Kann man das nachvollziehen? --StYxXx ⊗ 06:56, 9. Mär. 2010 (CET)

wegen der unterschiedlichen definitionen ist die frage nicht zu beantworten... hängt vom dozenten ab... bei uns wurden hash-methoden nur mal in ner übung angerissen, wenn ich mich recht entsinne... --Heimschützenzentrum (?) 09:25, 9. Mär. 2010 (CET)

Unpassendes Beispiel (Telefonbuch)

Ich habe dieses Beispiel auskommentiert. Ein Telefonbuch ist das Paradebeispiel einer geordneten Liste. Das zu intepretieren als Hashtable mit 26 (+ einige Sonderzeichen) Werten in der Hasfunktion Left(Name,1) und erst danach einer Linear Geordneten Liste zur Kollisionsauflösung innerhalb des Anfangsbuchstabens ist mMn völlig unrealistisch und verwirrt den Leser nur. Insbesondere, da innerhalb des Artikels mehrfach auf den Nachteil der Hashtable (keine Ordnungsrelation auf den Daten) hingewiesen wird (und genau diese ist beim Telefonbuch gegeben). Wenn ein Beispiel gewünscht ist, wie wäre es dann mit "Liste von Absolventen nach Abschlussjahr". --LungFalang 07:08, 7. Mär. 2010 (CET)

Ordnungserhaltendes Hashing

Es gibt ja auch Verfahren zum ordnungserhaltenden hashing. z.B. MOLPHE (Multidimensional order preserving linear hashing with partial expansions) {{DOI:10.1007/3-540-17187-8}}. Ich glaube die ursprüngliche Publikation ist "A Dynamic Hash File for Random and Sequential Accessing", Jack A. Orenstein, [2] Diese Verfahren würden ja einen der größten Nachteile von Hashtabellen aufheben. Natürlich haben sie auch Nachteile, ich glaube sie erwarten dass man eben vorher weiß in welchem Wertebereich die Daten liegen, und dass sie dort wirklich etwa gleich verteilt sind. Dadurch sind sie halt für viele typische Anwendungen (z.B. Objekt IDs die durchnummeriert werden) letztlich doch nicht praktisch sinnvoll? Oder sind sie nur als on-disk-hashtables sinnvoll? Irgend so eine Einschränkung gibt es da schon, sonst würde man sie ja immer hernehmen ... --Chire 20:39, 7. Mai 2010 (CEST)

wenn man die ordnung erhalten will, nimmt man da nich lieber b-trees, so dass die "ordnungserhaltenden Hash maps" vllt nicht so relevant oder nur theoretisch interessant sind? die b-trees sind im aufwand wohl auch nich schlimmer als "Ordnungserhaltendes Hashing"... <-- nur geraten... :-) // ansonsten mal in der WP:AU fragen? oder im Portal:informatik? --Heimschützenzentrum (?) 21:12, 7. Mai 2010 (CEST)

Weil suche in einem B-Baum halt trotzdem O(log n) ist, und nicht O(1) wie in einem Hash? Das gilt auch für ordnungserhaltende hashes - zumindest wenn entsprechende Voraussetzungen erfüllt sind. Sprich: wenn man diese Voraussetzungen schaffen kann (z.B. auf statischen Daten durch Anwendung eines Quantilverfahrens), ist das durchaus attraktiv. --Chire 23:41, 7. Mai 2010 (CEST)

ja schon... aber wenn diese Voraussetzungen nicht erfüllt sind, dann wirds wohl recht schlimm mit der komplexitätsklasse (linear oder schlimmer, könnte ich mir denken)... vom speicheraufwand gar nicht zu reden... --Heimschützenzentrum (?) 00:42, 8. Mai 2010 (CEST)

ich verstehe noch nicht ganz den sinn dieses abschnitts... soll das "ordnungserhaltende Hashen" also im artikel erwähnt werden? (dann: abwarten, dass jmd ne quelle findet... angesprochen ist es ja nun...) oder sind eher arbeiten zum thema gesucht? (dann: WP:AU oder Portal:informatik bitte...) --Heimschützenzentrum (?) 00:42, 8. Mai 2010 (CEST)

Naja, es wird als Nachteil aufgeführt das Hashtabellen nicht ordnungserhaltend sind. Aber offenbar gibt es halt auch ordnungserhaltende. Der Artikel sollte in der Richtung ergänz werden. Aber ich bin selbst gerade nicht in dem Thema so weit drin, dass ich das gut machen könnte. --Chire 01:43, 8. Mai 2010 (CEST)

ich habs mal kurz erwähnt... --Heimschützenzentrum (?) 13:54, 8. Mai 2010 (CEST)

hab es aber noch mal angepasst, das war etwas zu persönlich/wertend IMHO: "wenn man keinen B-Baum mag" bei Hashfunktion ist eine nicht gerade in Wikipedia passende Formulierung ... P.S. in Datenbanken verwendet man auch keinen B-Baum, sondern eben meist eher einen B+-Baum, und siehe da, was er im Wesentlichen verbessert ist der sortierte Zugriff. Und ich vermute fast, dass du eigentlich einen Binärer Suchbaum gemeint hattest. Das wäre für in-memory durchaus eine passende Alternative (mit eben O(log n) statt O(1) bei lookups) --Chire 18:56, 8. Mai 2010 (CEST)

Sonstiges

Vielleicht als kleine Inspiration:

Anmerkungen zum Abschnitt "Hashverfahren" Bisschen irreführend. Es ist nicht sofort klar, dass mit Objekt, Datenobjekt und Zielobjekt das Gleiche gemeint ist. Und später wird nur noch von Zieldaten gesprochen. Vielleicht kann man das etwas vereinheitlichen?

Anmerkungen zum Abschnitt "Der Algorithmus" Da steht: Beim Hashverfahren werden die Zieldaten (Was sind Zieldaten? Objekte, Datenobjekte oder ist damit das Zielobjekt gemeint?) in einer Hashtabelle (Wie sieht das aus?) gespeichert. Eine Hashfunktion berechnet zu jedem Datenobjekt einen Hashwert, der als Index in der Tabelle verwendet wird (und somit die Position des Objektes innerhalb der Tabelle angibt). Zum Berechnen dieses Hashwertes wird ein Schlüssel benötigt (Was für ein Schlüssel? Wo kommt der her? Wird der extra erstellt?), der dieses Objekt eindeutig identifiziert. Dieser Schlüssel wird von der Hashfunktion zum Berechnen des Hashwertes verwendet. Das Datenobjekt wird an einer durch den Hashwert festgelegten Stelle (Bucket genannt) in der Tabelle gespeichert. (Den Teil "(Bucket genannt)" würde ich hinter das Wort "Tabelle" setzen) vg (nicht signierter Beitrag von 95.116.183.58 (Diskussion) 07:34, 7. Jan. 2011 (CET))

Belege

Habe den Baustein 'Belege fehlen' entfernt, da inzwischen ja ordentlich Literatur angegeben ist und ich keine Stellen finden konnten, die Einzelnachweise benötigen. Falls jemand noch etwas finden sollte, bitte den Baustein nur wieder reinsetzen, wenn er hier konkret begründet wird. Oder am besten direkt nachtragen ... --Gms 14:17, 22. Jan. 2012 (CET)

Geschwindigkeitsvorteil II

In dem Artikel wird zwar mehrfach erwähnt daß, aber nicht erklärt, warum ein Objekt einer Hashtabelle schneller zu finden ist, als in einer Tabelle mit gleichförmit aufsteigenden Werten/Zahlen. --Katzili (Diskussion) 01:04, 6. Okt. 2012 (CEST)

ziemlich am Anfang: Hashtabelle#Hashverfahren („Dadurch erübrigt sich das Durchsuchen vieler Datenobjekte [...].“)... reicht doch, oda? --Heimschützenzentrum (?) 07:48, 6. Okt. 2012 (CEST)

Sondieren

Was versteht man genau unter sondieren? Der Begriff wird benutzt, ohne ihn zu definieren. Die Wikipedia Seite zu Sondieren sagt nur "in der Informatik: Funktion im Zusammenhang mit Hashtabellen" --Bomberzocker (Diskussion) 22:17, 9. Okt. 2017 (CEST)

Der eigentliche Algorithmus ist garnicht genannt!

Im Abschnitt „Algorithmus” wird aktuell nur ein Teil davon ganz grob beschrieben, bevors dann direkt zur Problematik der Kollisionen geht.
Ich denke hier ist beim Bearbeiten über die Zeit etwas verloren gegangen. ;)
Ich kam eigentlich her, um genau das zu erfahren: Wie funktioniert der generelle Algorithmus eigentlich? Also ich generiere einen Streuwert aus den Daten (konstante Zeit, aber nicht unbedingt schnelle Zeit!)… und dann? … Einfach eine Anordnung mit den Streuwerten als Schlüssel? Eine lückenhafte Anordnung? Das wär ja nicht sehr effizient… Oder eine die dann immer erweitert werden muss?
Das sind die Fragen, auf die ich mir in dem Abschnitt Antworten gewünscht hätte. :)
Wenn sich also ein Informatiker hier findet, wäre eine Bearbeitung höchst willkommen! :)
— 2A0A:A546:59D2:1:BCC2:1:7DB2:1540 11:16, 10. Nov. 2024 (CET)