mikrocontroller.net

Forum: PC-Programmierung Hashing mit offener Adressierung


Autor: ahnungsloser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

warum muss beim Hashing mit offener Adressierung die Tabellengröße eine 
Primzahl sein?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das muß sie nicht unbedingt sein, aber es reduziert etwas
Kollisionen (oft) und verbessert damit etwas die Effizienz.

Je nach Berechnung der Positionen im Einzelfall kann es vorkommen,
daß bestimmte Teiler gehäuft vorkommen, also z.B. jeder zweite, oder
jeder dritte oder jeder soundsovielte.
Oft auch kombiniert, z.B. könnte die Wahrscheinlichkeit
sowohl für Vielfache von 2 als auch 7 etwas höher sein als andere
Werte. Hat in einem solchen Fall meine Tabelle eine Länge eines
Vielfachen von 14, sind einige Stellen überfüllt, während andere
leer laufen. Das ist natürlich ungünstig.
Mit einer Tabellenlänge, die eine Primzahl ist, werden solche
Schlüssel besser verteilt.

Hat man eine ideale Schlüsselberechnung, ist die genaue
Tabellenlänge egal; auch eine nicht-Primzahl wäre ok.
Das weiß man aber oft nicht so genau, und eine Primzahl schadet
auch nicht und hilft halt oft etwas; deshalb nimmt man sie.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wobei das eine Abwägung sein kann. Mit Primzahl hat man eine Division an 
der Backe, andernfalls vielleicht nicht. Jetzt kommt es drauf an, was 
teurer ist: die Kollisionen oder die Divisionen. 
Datenstruktur-Theoretiker sind da gnadenlos, für sind alle skalaren 
Operation gleich teuer.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.